How to make a new graph consisting of shortest path edges of an original graph?

Question

I have learnt Dijkstra algorithm just some days ago and wanted to learn making a new undirected graph with shortest path edges from the original graph.

So what I did was added a simple modification to Dijkstra shortest path algorithm.

#define ll long long
vector <pair<int,long long>> adj[N]; //original graph
vector <int> adjj[N]; //new graph with shortest path edges

void dijkstra(int s)
{
    d[s]=0;  // array that stores shortest path
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    pq.push(make_pair(0,s));
    while(!pq.empty())
    {
        int v=pq.top().S;ll dist=pq.top().F;
        pq.pop();

        if(dist==((long long)(1e18)))
            return;
        if(dist>d[v])
            continue;
        if(p[v]!=0) // considering nodes' number start from 1          
            // new graph made only with shortest paths  
            adjj[parent[v]].push_back(v),adjj[v].push_back(parent[v]); 
        for(auto edge : adj[v])
        {
            int to = edge.first;
            ll len = edge.second;
            if((len+d[v])<d[to])
            {
                parent[to]=v;
                d[to]=len+d[v];
                pq.push(make_pair(d[to],to));
            }
        }
    }
}

So I tried this code on some of my custom Test Cases but I am not fully assured that this is correct... It would be great If you could tell me whether this wrong or right ?

Answer 1

It is correct. What you are doing here is, essentially, bulding a search tree that reflects the paths your algorithm found. This tree, however, is usually directed, because it is a rooted tree.

A few things worth mentioning:

• You declared a #define that you never used (ll)
• Instead of hard-coding infinity in your code, you should have a #define INF
• There's no need to test if infinity will come from the priority queue. You only push a vertex onto the queue once you've found a path into it