graphs.graphs_floyd_warshall

The problem is to find the shortest distance between all pairs of vertices in a weighted directed graph that can have negative edge weights.

Attributes

v

Functions

_print_dist(→ None)

floyd_warshall(graph, v)

Module Contents

graphs.graphs_floyd_warshall._print_dist(dist, v) → None
graphs.graphs_floyd_warshall.floyd_warshall(graph, v)
Parameters:

  • graph (List[List[float]]) – 2D array calculated from weight[edge[i, j]]

  • v (int) – number of vertices

Returns:

shortest distance between all vertex pairs

distance[u][v] will contain the shortest distance from vertex u to v.

1. For all edges from v to n, distance[i][j] = weight(edge(i, j)). 3. The algorithm then performs distance[i][j] = min(distance[i][j], distance[i][k] +

distance[k][j]) for each possible pair i, j of vertices.

  1. The above is repeated for each vertex k in the graph.

  2. Whenever distance[i][j] is given a new minimum value, next vertex[i][j] is

    updated to the next vertex[i][k].

>>> graph = [
...     [0, 3, float('inf')],
...     [2, 0, float('inf')],
...     [float('inf'), 7, 0]
... ]

>>> expected = [
...     [0, 3, float('inf')],
...     [2, 0, float('inf')],
...     [9, 7, 0]
... ]
>>> dist, _ = floyd_warshall(graph, 3)

The shortest path matrix using Floyd Warshall algorithm

0  3  INF
2  0  INF
9  7  0
>>> dist == expected
True
graphs.graphs_floyd_warshall.v