Print all minimum paths between 2 nodes in an undirected weighted graph

Question

Given an undirected weighted graph, the lengths between 2 nodes are integers.

How can one print the pair of nodes that have the minimum distance in the graph. If there are multiple pairs, print all of them

Answer 1

Let's agree that we are looking for simple paths (no repeated vertices) on a undirected weighted graph G.

The amount of minimum distance paths between two vertices u and v could be up to (n-2)! (complete graph with zero weight edges, every permutation that starts at u and ends at v is a valid minimum distance path).

Nevertheless, you can figure out the amount of such paths or do backtrack to find each of them if you manage to create a new graph G' with the same vertices as G and whose edges are those that belongs to some minimum distance path between u and v in G.

An easy way to build G' is:

1. Calculate single source shortest paths that begin at u and keep distance array (du).
2. Calculate single source shortest paths that begin at v and keep distance array (dv).
3. Create G' with all nodes from G and zero edges.
4. For each edge <x, y> in G (weight of <x, y> is w), if du[x] + w + dv[y] == du[v] or du[y] + w + dv[x] == du[v] then <x, y> belongs to G'.

If you force edge direction at step 4 and there are no zero weight loops then G' is DAG (directed acyclic graph). You can use DAG property to calculate amount of minimum distance path between u and v in G' and as sidequest prove such answer is equal to the answer of original problem. Also, if backtracking from u whenever it find v then you obtain a minimum distance path between u and v in G.

You can use dijkstra's algorithm or Bellman-Ford's algorithm to calculate single source shortest paths based on your weight constraints.