CODEWITHSUNDEEP
c++algorithmdata-structuresbreadth-first-searchshortest-path
alex deralu
alex deralu

Reputation: 589

How to find if there is more than one shortest path in a weighted graph?

I have an undirected weighted graph.

I am using Dijkstra's algorithm to find the shortest path from the source node to the destination node.

But I also want to make a bool function that can tell me if there is more than one shortest path.

The code I have written till now

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,m,source;
    cin >> n >> m;
    vector<pair<int,int> > g[n+1];  // 1-indexed adjacency list for of graph

    int a,b,wt;
    for(int i = 0; i<m ; i++){
        cin >> a >> b >> wt;
        g[a].push_back(make_pair(b,wt));
        g[b].push_back(make_pair(a,wt));
    }   
    
    cin >> source;
    
    // Dijkstra's algorithm begins from here
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;// min-heap ; In pair => (dist,from)
    vector<int> distTo(n+1,INT_MAX);    // 1-indexed array for calculating shortest paths; 
    
    distTo[source] = 0;
    pq.push(make_pair(0,source));   // (dist,from)
    
    while( !pq.empty() ){
        int dist = pq.top().first;
        int prev = pq.top().second;
        pq.pop();
        
        vector<pair<int,int> >::iterator it;
        for( it = g[prev].begin() ; it != g[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 distances from source, " << source << ", are : \n";
    for(int i = 1 ; i<=n ; i++) cout << distTo[i] << " ";
    cout << "\n";
    
    return 0;
}

I don't need the path of the different shortest paths, just a true or false.

I read a lot of online sources regarding this, from there I got that in the algorithm there is no condition for when

if( distTo[next] == distTo[prev] + nextDist)

So when this occurs I should add that node to a list/2d vector.

I am not able to implement this idea, so when there is == condition what should I add that node to? Do I have to trace the entire path and then compare it with the shortest path?

If possible can you write the code and show me how it can be done?

Am I going about this idea wrong by doing it with Dijkstra? is there a different algorithm that helps me do this? I just need a true and false if there are one than more shortest paths between source and destination node.

Update

Example input

4,4
0,1,3
1,2,1 
2,3,2 
0,2,4

source-0

destination-3

For this the destTo vector output is 0 3 4 6

Upvotes: 1

Views: 563

Answers (1)

Beta
Beta

Reputation: 99084

You can do it with a modified Dijkstra's that keeps track of whether a node can be reached by multiple shortest paths.

The simplest way is with a container of bool:

vector<bool> multipath(n, false);

and some logic to manage these bits:

if( distTo[next] == distTo[prev] + nextDist){
  multipath[next] = true;
}

if( distTo[next] > distTo[prev] + nextDist){
  distTo[next] = distTo[prev] + nextDist;
  if(multipath[prev])
    multipath[next]=true;
  pq.push(make_pair(distTo[next], next));
}

And then some way to report the results:

for(int i = 1 ; i<n ; i++){
  cout << distTo[i];
  if(multipath[i])
    cout << "*";
  cout << " ";
}
cout << "\n";

Upvotes: 1

Related Questions