Phoenix Holmes Phoenix Holmes - 6 days ago 7
C++ Question

Shortest route modification

Is there a way to modify this to show the route of the shortest path? For example, if i had a list of numbers like (3,1),(3,0),(4,3),(2,1) the output for getting from 4 to 1 would be 4->3,3->1

// Prints shortest paths from src to all other vertices
void Graph::shortestPath(int src)
{
// Create a priority queue to store vertices that
// are being preprocessed. This is weird syntax in C++.
// Refer below link for details of this syntax
// http://geeksquiz.com/implement-min-heap-using-stl/
priority_queue< iPair, vector <iPair> , greater<iPair> > pq;


// Create a vector for distances and initialize all
// distances as infinite (INF)
vector<int> dist(V, INF);

// Insert source itself in priority queue and initialize
// its distance as 0.
pq.push(make_pair(0, src));
dist[src] = 0;

/* Looping till priority queue becomes empty (or all
distances are not finalized) */
while (!pq.empty())
{
// The first vertex in pair is the minimum distance
// vertex, extract it from priority queue.
// vertex label is stored in second of pair (it
// has to be done this way to keep the vertices
// sorted distance (distance must be first item
// in pair)
int u = pq.top().second;
pq.pop();

// 'i' is used to get all adjacent vertices of a vertex
list< pair<int, int> >::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
// Get vertex label and weight of current adjacent
// of u.
int v = (*i).first;
int weight = (*i).second;

// If there is shorted path to v through u.
if (dist[v] > dist[u] + weight)
{
// Updating distance of v
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}

// Print shortest distances stored in dist[]
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}


Putting in an array that stores the numbers of the path like 4,3,3,1 (using above example) seems like the best idea but i don't know where to insert the array in this code to do that.

Answer

Just as you save the distances for each vertex in the dist vector, save the predecessor vertex that last updated it in a vector called predecessor.

vector<int> dist(V, INF);
vector<int> predecessor(V, 0);

Then whenever you update the distance, update the predecessor:

dist[v] = dist[u] + weight;
predecessor[v] = u;

Finally, you can trace for any vertex the shortest path (Backward) to the source:

printf("Vertex   Distance from Source      shortest path from source\n");
for (int i = 0; i < V; ++i)
{
        printf("%d \t\t %d\t\t", i, dist[i]);
        int j = i;
        do
        {
             printf("%d,", j);
             j = predecessor[j];
        } while(j != src);
        printf("\n");
}
Comments