im trying to get my code to perform dijkstra's algorithm on my adjacny matrix, it works great for the inital row (0) but i cant get it working for any other value?!
void dijkstra (int a[size][size], int matSize, string CityID[size])
{
string startCity;
cout << "Enter start city : ";
cin >> startCity;
int MAX = matSize;
int startCityID = getCityID(startCity, CityID, MAX); //gets the value of the city
//Declaring a priority queue of edge - stipulating greater so it orders on a
//min-heap i.e. pq.top() will be smallest weight edge in pq.
priority_queue <edge, vector<edge>, greater<edge> >pq;
insertInfinity(a,matSize); //replaces all zeroes with 9999
// set to source
int* parent = NULL;
parent = new int[MAX];
for (int fillP = 0; fillP <= MAX; fillP++)
{
parent[fillP] = false;
}
//Creates a dynamic array to store the vertex sets, and sets the default
//boolean operator to false.
bool* inVertexSet = NULL;
inVertexSet = new bool[MAX];
for (int fillVS = 0; fillVS <= MAX; fillVS++)
{
inVertexSet[fillVS] = false;
}
//
int* weights = NULL;
weights = new int[MAX];
int store;
for (int fillW = 0; fillW <= MAX; fillW++)
{
store = a[startCityID][fillW];
weights[fillW] = store;
}
for (int col = 0; col < MAX ; col++)
{
if (a[startCityID][col] < B) // B = 9999
{
pq.push (edge( a[startCityID][col],col,0)); // edges adjacent to source
}
}
inVertexSet[startCityID] = true; // set source to be in vertex set
while (!pq.empty())
{
edge p = pq.top(); // get edge with smallest weight
int dist = p.weight;
int v = p.vertex1; // note that vertex2 is already in vertexset
pq.pop();
if (!inVertexSet[v])
{
inVertexSet[v] = true; // know least cost path to v
for (int u=startCityID; u < MAX; u++)
{
if (!inVertexSet[u])
{
if (weights[u] > weights[v]+a[v][u])
{
weights[u] = weights[v] + a[v][u];
// keep track of path here by recording u's parent as v
parent[u] = v;
pq.push(edge(weights[u],u,v));
}
}
}
}
}
for (int i=0;i<MAX;i++)
{
cout << "\nDISTANCE to "<< CityID[i] << " = " << weights[i] << endl;
cout << "PATH from " << startCity << " to vertex " << CityID[i] << endl;
printpath(i,parent, CityID);
cout << endl;
} system("pause");
}