I've implemented Floyd-Warshall to return the distance of the shortest path between every pair of nodes/vertices and a single shortest path between each of these pairs.
Is there any way to get it to return every shortest path, even when there are multiple paths that are tied for shortest, for every pair of nodes? (I just want to know if I'm wasting my time trying)
The 'counting' function in the current approved answer flails in some cases. A more complete solution would be:
The reason for this is that for any three vertices i, j, and k, there may be multiple shortest paths that run from i through k to j. For instance in the graph:
Where there are two paths from i to j through k.
count[i][k] * count[k][j]
finds the number of paths from i to k, and the number of paths from k to j, and multiplies them to find the number of paths i -> k -> j.If you just need the count of how many different shortest path exist, you can keep a
count
array in addition to theshortestPath
array. Here's is a quick modification of the pseudocode from wiki.If you need a way to find all the paths, you can store a
vector/arraylist
like structure for each pair to expand and collapse. Here is a modification of the pseudocode from the same wiki.Note: if
k==j
ork==i
, that means, you're checking eitherpath[i][i]+path[i][j]
orpath[i][j]+path[j][j]
, both should be equal topath[i][j]
and that does not get pushed intonext[i][j]
.Path reconstruction should be modified to handle the
vector
. The count in this case would be eachvector
's size. Here is a modification of the pseudocode (python) from the same wiki.Note:
path[i][j]
is an adjacency list. While initializingpath[i][j]
, you can also initializenext[i][j]
by adding a-1
to the array. For instance an initialization ofnext[i][j]
would beThis takes care of an edge being the shortest path itself. You'll have to handle this special case in the path reconstruction, which is what i'm doing in
GetPath
.Edit: "MAX_VALUE" is the initialized value in the array of distances.