floyd-warshall algorithm

Uses dynamic programming to update all pairs’ shortest paths by considering each vertex as an intermediate point.

Steps:

• create a 2D array dist where dist[i][j] is the shortest distance from vertex i to vertex j
  • set initial distances based on given edges
  • set diagonals (distance to self) to 0
  • infinity everywhere else
• iterate through each vertex k as an intermediate point between vertices i and j, updating dist[i][j] to the minimum of dist[i][j] and dist[i][k] + dist[k][j]

def floyd_warshall(graph, V):
    dist = [[float('inf')] * V for _ in range(V)]
    
    for i in range(V):
        dist[i][i] = 0
    
    for u, v, w in graph:
        dist[u][v] = w
    
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist
 
# Example usage
graph = [
    (0, 1, 3), (0, 2, 8), (0, 3, -4),
    (1, 0, 4), (1, 2, -1), (2, 1, 4),
    (3, 2, 7), (3, 0, 6)
]
V = 4
dist_matrix = floyd_warshall(graph, V)
for row in dist_matrix:
    print(row)