title: Using Dijkstra to detect multiple shortest paths
body: <p>Given a weighted directed graph, how can the Dijkstra algorithm be modified to test for the presence of multiple lowest-cost paths between a given pair of nodes?</p>
  
  <p>My current algorithm is as follows: (credit to Weiss)</p>
  
  <pre><code>/**
   * Single-source weighted shortest-path algorithm. (Dijkstra) 
   * using priority queues based on the binary heap
   */
  public void dijkstra( String startName )
  {
      PriorityQueue&lt;Path&gt; pq = new PriorityQueue&lt;Path&gt;( );
  
      Vertex start = vertexMap.get( startName );
      if( start == null )
          throw new NoSuchElementException( "Start vertex not found" );
  
      clearAll( );
      pq.add( new Path( start, 0 ) ); start.dist = 0;
  
      int nodesSeen = 0;
      while( !pq.isEmpty( ) &amp;&amp; nodesSeen &lt; vertexMap.size( ) )
      {
          Path vrec = pq.remove( );
          Vertex v = vrec.dest;
          if( v.scratch != 0 )  // already processed v
              continue;
  
          v.scratch = 1;
          nodesSeen++;
  
          for( Edge e : v.adj )
          {
              Vertex w = e.dest;
              double cvw = e.cost;
  
              if( cvw &lt; 0 )
                  throw new GraphException( "Graph has negative edges" );
  
              if( w.dist &gt; v.dist + cvw )
              {
                  w.dist = v.dist +cvw;
                  w.prev = v;
                  pq.add( new Path( w, w.dist ) );
              }
          }
      }
  }
  </code></pre>