Name: Anonymous 2013-10-26 23:05
Hi /prog/. I'm having some issues with the way I implemented dijkstra's algorithm. Can you guys see if you can spot any errors or anything weird? I tried to comment as best as I can.
Here is the .cpp file
Here is the .cpp file
// ---------------------------------------------------------------------------
// findShortestPath
// Finds the shortest path between each node using Dijkstra's algorithm. Implemented
// using private arrays: T for the shortest distance between nodes, pathing, and
// marking for being visited; and C to record the nodes and the distances between
// them.
void GraphM::findShortestPath()
{
int V;
for(int source = 1; source <= size; source++) //loop for each node
{
T[source][source].dist = 0;
T[source][source].visited = true;
T[source][source].path = source;
V = source;
for(int numRuns = 1; numRuns < size ; numRuns++) //Main loop for for 'V'
{
for(int W = 1; W <= size; W++) //Loop for the 'W' component
{
if(C[V][W] == INFINITY || T[source][W].visited == true)
continue; //Skips this 'W' if the node is visited or distance is infinite
else if(T[source][W].dist > T[source][V].dist + C[V][W]) //Sets shortest distance
{
T[source][W].dist = T[source][V].dist + C[V][W];
T[source][W].path = V;
}
}
T[source][V].visited = true;
V = findShortestPathHelper(source);
}
T[source][V].visited = true; //Set last node to visited
}
//cout << "Distance from 1 to 2: " << T[1][2].dist << endl;
}
// findShortestPathHelper
// **Helper Method for findShortestPath**
// Finds the unvisited node with the lowest distance for the V component of
// Dijkstra's algorithm.
int GraphM::findShortestPathHelper(int source)
{
int min = 0;
for(int i = 1; i <= size; i++)
{
if(T[source][i].dist < T[source][min].dist && T[source][i].visited == false)
min = i;
}
return min;
}