Printing shortest path b/w given nodes using modified floyd warshall
It’s much easier (and more direct) not to iterate over indices but over vertices. Furthermore, each predecessor (usually denoted π
, not next
), needs to point to its, well, predecessor, not the current temporary vertex.
Given a |V|×|V| adjacency matrix dist
for the distances, initialised to infinity, and a |V|×|V| adjacency matrix next
to with pointers to vertices,
for each vertex v
dist[v, v] ← 0
for each edge (u,v)
dist[u, v] ← w(u,v) // the weight of the edge (u,v)
next[u, v] ← u
for each vertex k
for each vertex i
for each vertex j
if dist[i, k] + dist[k, j] < dist[i, j] then
dist[i, j] ← dist[i, k] + dist[k, j]
next[i, j] ← next[k, j]
Note that I’ve changed the three nested loops to iterate over vertices not indices, and I’ve fixed the last line to refer to the previous node rather than any intermediate node.
An implementation of the above which looks almost like the pseudocode can be found, for instance, in scipy.sparse.csgraph
.
Path reconstruction starts at the end (j
in the code below) and jumps to the predecessor of j
(at next[i, j]
) until it reaches i
.
function path(i, j)
if i = j then
write(i)
else if next[i, j] = NIL then
write("no path exists")
else
path(i, next[i, j])
write(j)