What is correct path tracking in Floyd-Warshall algorithm?

Question

There are several descriptions of the Floyd-Warshall algorithm, including the one in Wikipedia where path tracking logic described like in the pseudo-code below (copy from Wikipedia https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Path_reconstruction)

procedure FloydWarshallWithPathReconstruction() is
    for each edge (u, v) do
        dist[u][v] = w(u, v)  // The weight of the edge (u, v)
        prev[u][v] = u
    for each vertex v do
        dist[v][v] = 0
        prev[v][v] = v
    for k from 1 to |V| do // standard Floyd-Warshall implementation
        for i from 1 to |V|
            for j from 1 to |V|
                if dist[i][j] > dist[i][k] + dist[k][j] then  // shouldn't it be dist[i][j] > graph[i][k] + dist[k][j]???
                    dist[i][j] = dist[i][k] + dist[k][j]  // shouldn't it be dist[i][j] = graph[i][k] + dist[k][j]???
                    prev[i][j] = prev[k][j]

procedure Path(u, v) is
    if prev[u][v] = null then
        return []
    path = [v]
    while u ≠ v do
        v = prev[u][v]
        path.prepend(v)
    return path

In Floyd-Warshall algorithm with path tracking shouldn't the update rule be 'dist[i][j] = graph[i][k] + dist[k][j]' (where graph[i][k] = w(i, k) is the weight of the edge (i, k) if any) instead of 'dist[i][j] = dist[i][k] + dist[k][j]'? I've marked with a comment the corresponding line in code above. I mean if the path from i to k is longer than one edge then path tracking logic won't work updating just one "hop". Or am I just missing something?

BTW corrected (if it's right) version would also work when we need to track the length of the path (in number of edges). Say, finding shortest path with no longer than N "hops" as we augmenting path by one edge at the iteration.

Thanks!

RomanGirin · Accepted Answer · 2025-04-23 15:28:23Z

Just in case if someone also will be curious about this theoretical aspect of Floyd-Warshall algorithm I'm posting a reply to my own question.

Again it may be counterintuitive that path tracking matrix gets updated via one iteration at each update even though path from some node i to some node k may include several intermediate nodes. (I've highlighted the part in the original question)

It may be helpful to consider it from this point of view: we always augmenting path with just one node.

Considering the following case:

  node i   ----------------------------------> node j
    |  |                                          ^
    |  -------------------------                  |
    |                          |                  |
    ----->  node t  ----->   node k   ------------|

It may be helpful to trace step by step how path from i to j gets updated.

The Python code for this case is below (in the code node k is 0, i is 1, j is 2, t is 3):

def floyd_warshall(V):
    global dis, nxt
    for k in range(V):
        for i in range(V):
            for j in range(V):
                # We cannot travel through edge that doesn't exist
                if dis[i][k] == INF or dis[k][j] == INF:
                    continue
                if dis[i][j] > dis[i][k] + dis[k][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]
                    nxt[i][j] = nxt[i][k]


def construct_path(u, v):
    global graph, nxt

    path = [u]
    while (u != v):
        u = nxt[u][v]
        path.append(u)

    return path

def print_path(path):
    n = len(path)
    for i in range(n - 1):
        print(path[i], end=" -> ")
    print(path[n - 1])


# Driver code
if __name__ == '__main__':
    INF = 10 ** 7

    V = 4
    graph = [[0, INF, 1, INF],
             [50, 0, 100, 1],
             [INF, INF, 0, INF],
             [1, INF, INF, 0]]

    dis = list(map(lambda p: list(map(lambda q: q, p)), graph))
    nxt = list(map(lambda p: list(map(lambda q: 0, p)), graph))

    for i in range(V):
        for j in range(V):
            dis[i][j] = graph[i][j]
            nxt[i][j] = j

    floyd_warshall(V)

    # Path from node 1 to 2
    print("Shortest path from 1 to 2: ", end="")
    path = construct_path(1, 2)
    print_path(path)
    print("Distance from 1 to 2: ", end="")
    print(dis[1][2])

The code output is below (but again it's most helpful to trace step by step how the path get constructed and the theoretical aspect, not the end result):

Shortest path from 1 to 2: 1 -> 3 -> 0 -> 2
Distance from 1 to 2: 3

Also order of the cycles is very important (which is helpfully discussed in this question https://stackoverflow.com/a/74508098/18031828)

Appreciate any constructive remarks in case I've missed something.

Hope it helps!

Collectives™ on Stack Overflow

What is correct path tracking in Floyd-Warshall algorithm?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related