How to print the paths in Dijkstra's shortest path algorithm

user_18795717 0
Viewed 510

Can anyone help me, How to print the paths in Dijkstra's Shortest Path Algorithm? I have worked on the Undirected Weighted graph and found the shortest path in int. but printing their paths is quite complicated. How to print their paths ?????

I was working on a program that prints the distance and the path. I got the distance working well, but the problem I am having comes when I try to print the path.

Vertex, Edge.

#include<iostream>
#include<queue>
#include<vector>
#include<string>
#include<map>

using namespace std;
map<char,int> m = {{'A',1}, {'B',2}, {'C',3}, {'D',4}, {'E',5}};
vector<char> vec;

int main()
{
    int Vertex,Edges;
    char Source_station;
    cout<<"Vertex and Edges : ";
    cin>>Vertex>>Edges;
    vector<pair<int,int>> graph[Vertex+1];
    
    int Distance;
    char Starting_station,Ending_station;
    cout<<"Starting_station , Ending_station , Distance:";
    for(int i=0;i<Edges;++i)
    {
        cin>>Starting_station>>Ending_station>>Distance;
        graph[m[Starting_station]].push_back(make_pair(m[Ending_station],Distance));
        graph[m[Ending_station]].push_back(make_pair(m[Starting_station],Distance));
    }

    char Passenger_destination;
    cout<<"Enter the Source_station and Passenger Destination : "<<endl;
    cin>>Source_station>>Passenger_destination;

    priority_queue< pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>>> pq;

    vector<int> distTo (Vertex+1, INT32_MAX);
    distTo[m[Source_station]]=0;
    pq.push(make_pair(0,m[Source_station]));


    while(!pq.empty())
    {
        int dist = pq.top().first;
        int prev = pq.top().second;
        pq.pop();

        vector<pair<int,int>> :: iterator it;
        for(it=graph[prev].begin(); it!=graph[prev].end(); it++)
        {
            int next = it->first;
            int nextDist = it->second;
            if(distTo[next] > distTo[prev] + nextDist)
            {
                distTo[next] = distTo[prev] + nextDist;
                pq.push(make_pair(distTo[next] , next));
            }
        }
    }

    cout<<"The distance from source, "<<Source_station <<" are : "<<endl;
    for(int i=1;i<=Vertex; i++)
    {
        if(i==m[Passenger_destination])
            cout<<distTo[i]<<" ";
    }
    cout<<endl;

    return 0;
}
shortest-path graph
1 Answers

You can update your code to store parent pointers and recover the shortest path using parent pointers. More specifically, for each node v, you can store its parent p[v], which can be initialized to nil. If the condition (distTo[next] > distTo[prev] + nextDist) is satisfied, besides updating distTo[next], you can also store that the parent of next is prev, i.e. something like p[next]=prev. In other words, you keep a record of which predecessor node gave you the current best shortest path to a node next.

After the shortest distances have been calculated, you can print the shortest path to a node x by starting from x and following parent pointers p[x], p[p[x]], etc, until you hit the source. This gives the shortest path.

It's a common practice to augment dynamic programming algorithms to store parent pointers.

user_78365590
Related