dynamic_programming.floyd_warshall¶

Attributes¶

class dynamic_programming.floyd_warshall.Graph(n=0)¶

add_edge(u, v, w)¶

Adds a directed edge from node u to node v with weight w.

>>> g = Graph(3)
>>> g.add_edge(0, 1, 5)
>>> g.dp[0][1]
5

floyd_warshall()¶

Computes the shortest paths between all pairs of nodes using the Floyd-Warshall algorithm.

>>> g = Graph(3)
>>> g.add_edge(0, 1, 1)
>>> g.add_edge(1, 2, 2)
>>> g.floyd_warshall()
>>> g.show_min(0, 2)
3
>>> g.show_min(2, 0)
inf

show_min(u, v)¶

Returns the minimum distance from node u to node v.

>>> g = Graph(3)
>>> g.add_edge(0, 1, 3)
>>> g.add_edge(1, 2, 4)
>>> g.floyd_warshall()
>>> g.show_min(0, 2)
7
>>> g.show_min(1, 0)
inf