How to find 3 shortest paths in a graph?

Question

Programming

Find the 3 shortest paths in the graph. That is, display the top 3 short paths.
How to exclude the first path when searching for the second one? And the first two when looking for the third?

Answer 1

It will be difficult for you.
1. Find a way.
2. From this path you alternately delete along the edge and build a path in the graph without an edge. One of the options (or several) will be the shortest. If there are several, the problem is solved.
3. If not - well, you understand ...

Answer 2

dijkstra

Answer 3

At each vertex, store no more than three shortest paths to it. In Dijkstra, use the queue without modifying the weight. If the next path taken from the queue is better than the third path stored in the vertex in order (or no more than two paths are stored) - add this path to the vertex, and all its continuations - to the queue.
The problem is that cycles can appear in the paths. For example, for a two-vertex graph with three edges
(1,2, w=1)
(1,2, w=3)
(1,2, w=5)
paths 1-2 (on the first edge), 1 -2 (on the second edge) and 1-2-1-2 (on the first edge). If cycles are undesirable, you will have to mess around longer