Source code for tryalgo.floyd_warshall

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
All pairs shortest paths by Floyd-Warshall
jill-jênn vie, christoph dürr et pascal ortiz - 2014-2019
"""


# snip{
[docs]def floyd_warshall(weight): """All pairs shortest paths by Floyd-Warshall :param weight: edge weight matrix :modifies: weight matrix to contain distances in graph :returns: True if there are negative cycles :complexity: :math:`O(|V|^3)` """ V = range(len(weight)) for k in V: for u in V: for v in V: weight[u][v] = min(weight[u][v], weight[u][k] + weight[k][v]) for v in V: if weight[v][v] < 0: # negative cycle found return True return False
# snip}
[docs]def floyd_warshall2(weight): """All pairs shortest paths by Floyd-Warshall. An improved implementation by Pascal-Ortiz :param weight: edge weight matrix :modifies: weight matrix to contain distances in graph :returns: True if there are negative cycles :complexity: :math:`O(|V|^3)` """ for k, Wk in enumerate(weight): for _, Wu in enumerate(weight): for v, Wuv in enumerate(Wu): alt = Wu[k] + Wk[v] if alt < Wuv: Wu[v] = alt for v, Wv in enumerate(weight): if Wv[v] < 0: # negative cycle found return True return False