title: How to find if there is more than one shortest path in a weighted graph?
body: <p>I have an undirected weighted graph.</p>
  <p>I am using Dijkstra's algorithm to find the shortest path from the source node to the destination node.</p>
  <p>But I also want to make a bool function that can tell me if there is more than one shortest path.</p>
  <p>The code I have written till now</p>
  <pre><code>#include&lt;bits/stdc++.h&gt;
  using namespace std;
  
  int main(){
      int n,m,source;
      cin &gt;&gt; n &gt;&gt; m;
      vector&lt;pair&lt;int,int&gt; &gt; g[n+1];  // 1-indexed adjacency list for of graph
  
      int a,b,wt;
      for(int i = 0; i&lt;m ; i++){
          cin &gt;&gt; a &gt;&gt; b &gt;&gt; wt;
          g[a].push_back(make_pair(b,wt));
          g[b].push_back(make_pair(a,wt));
      }   
      
      cin &gt;&gt; source;
      
      // Dijkstra's algorithm begins from here
      priority_queue&lt;pair&lt;int,int&gt;,vector&lt;pair&lt;int,int&gt; &gt;,greater&lt;pair&lt;int,int&gt; &gt; &gt; pq;// min-heap ; In pair =&gt; (dist,from)
      vector&lt;int&gt; 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&lt;pair&lt;int,int&gt; &gt;::iterator it;
          for( it = g[prev].begin() ; it != g[prev].end() ; it++){
              int next = it-&gt;first;
              int nextDist = it-&gt;second;
              if( distTo[next] &gt; distTo[prev] + nextDist){
                  distTo[next] = distTo[prev] + nextDist;
                  pq.push(make_pair(distTo[next], next));
              }
          }
          
      }
      
      cout &lt;&lt; &quot;The distances from source, &quot; &lt;&lt; source &lt;&lt; &quot;, are : \n&quot;;
      for(int i = 1 ; i&lt;=n ; i++) cout &lt;&lt; distTo[i] &lt;&lt; &quot; &quot;;
      cout &lt;&lt; &quot;\n&quot;;
      
      return 0;
  }
  </code></pre>
  <p>I don't need the path of the different shortest paths, just a true or false.</p>
  <p>I read a lot of online sources regarding this, from there I got that in the algorithm there is no condition for when</p>
  <pre><code>if( distTo[next] == distTo[prev] + nextDist)
  </code></pre>
  <p>So when this occurs I should add that node to a list/2d vector.</p>
  <p>I am not able to implement this idea, so when there is <code>==</code> condition what should I add that node to? Do I have to trace the entire path and then compare it with the shortest path?</p>
  <p>If possible can you write the code and show me how it can be done?</p>
  <p>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.</p>
  <p>Update</p>
  <p>Example input</p>
  <pre><code>4,4
  0,1,3
  1,2,1 
  2,3,2 
  0,2,4
  </code></pre>
  <p>source-0</p>
  <p>destination-3</p>
  <p>For this the <code>destTo</code> vector output is <code>0 3 4 6</code></p>