title: second shortest / k-th shortest path
body: <p>With the code below, I am trying to find the second shortest path / k-th shortest path.     </p>
  
  <pre><code>// Run Dijkstra's algorithm on given graph
      public static void shortestPath(GraphModel graph, int source, int destination, int numberOfVertices)
      {
          // create min heap and push source node having distance 0
          PriorityQueue&lt;NodeModel&gt; minHeap = new PriorityQueue&lt;&gt;((lhs, rhs) -&gt; lhs.weight - rhs.weight);
          minHeap.add(new NodeModel(source, 0));
  
          // set infinite distance from source to v initially
          List&lt;Integer&gt; dist = new ArrayList&lt;&gt;(Collections.nCopies(numberOfVertices, Integer.MAX_VALUE));
  
          // distance from source to itself is zero
          dist.set(source, 0);
  
          // boolean array to track vertices for which minimum
          // cost is already found
          boolean[] done = new boolean[numberOfVertices];
          done[0] = true;
  
          // stores predecessor of a vertex (to print path)
          int prev[] = new int[numberOfVertices];
          prev[0] = -1;
  
          // run till minHeap is not empty
          while (!minHeap.isEmpty())
          {
              // Remove and return best vertex
              NodeModel node = minHeap.poll();
              node = minHeap.poll();
              // get vertex number
              int u = node.vertex;
  
              // do for each neighbor v of u
              for (EdgeModel edge: graph.adjList.get(u))
              {
                  int v = edge.dest;
                  int weight = edge.weight;
                  // Relaxation step
                  if (!done[v] &amp;&amp; (dist.get(u) + weight) &lt; dist.get(v))
                  {
                      dist.set(v, dist.get(u) + weight);
                      prev[v] = u;
                      minHeap.add(new NodeModel(v, dist.get(v)));
                  }
              }
  
              // marked vertex u as done so it will not get picked up again
              done[u] = true;
          }
  </code></pre>
  
  <p>Here is the graph.</p>
  
  <pre><code>    List&lt;EdgeModel&gt; edges = Arrays.asList(
              new EdgeModel(0, 1, 10), 
              new EdgeModel(0, 4, 3),
              new EdgeModel(1, 2, 5), 
              new EdgeModel(1, 4, 1),
              new EdgeModel(2, 3, 7), 
              new EdgeModel(2, 4, 8),
              new EdgeModel(3, 4, 2), 
              new EdgeModel(4, 1, 20)
      );
  </code></pre>
  
  <blockquote>
    <p>The shortest path from 0-4 is 3</p>
    
    <p>The second shortest path from 0-4 is 11</p>
  </blockquote>
  
  <p><a href="https://i.stack.imgur.com/f7hQb.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/f7hQb.png" alt="enter image description here"></a></p>