Source code for tryalgo.bellman_ford
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Single source shortest paths by Bellman-Ford
jill-jenn vie et christoph durr - 2014-2018
"""
# snip{
# pylint: disable=unused-variable
[docs]
def bellman_ford(graph, weight, source=0):
""" Single source shortest paths by Bellman-Ford
:param graph: directed graph in listlist or listdict format
:param weight: can be negative.
in matrix format or same listdict graph
:returns: distance table, precedence table, bool
:explanation: bool is True if a negative circuit is
reachable from the source, circuits
can have length 2.
:complexity: `O(|V|*|E|)`
"""
n = len(graph)
dist = [float('inf')] * n
prec = [None] * n
dist[source] = 0
for nb_iterations in range(n):
changed = False
for node in range(n):
for neighbor in graph[node]:
alt = dist[node] + weight[node][neighbor]
if alt < dist[neighbor]:
dist[neighbor] = alt
prec[neighbor] = node
changed = True
if not changed: # fixed point
return dist, prec, False
return dist, prec, True
# snip}
[docs]
def bellman_ford2(graph, weight, source):
""" Single source shortest paths by Bellman-Ford
:param graph: directed graph in listlist or listdict format
:param weight: can be negative.
in matrix format or same listdict graph
:returns: distance table, precedence table, bool
:explanation: bool is true if there is a negative cycle
reachable from the source.
distance[v] is +inf if vertex v is not reachable
from source and -inf if there are paths from the
source to v of arbitrary small weight.
:complexity: `O(|V|*|E|)`
"""
n = len(graph)
dist = [float('inf')] * n
prec = [None] * n
dist[source] = 0
def relax():
for nb_iterations in range(n-1):
for node in range(n):
for neighbor in graph[node]:
alt = dist[node] + weight[node][neighbor]
if alt < dist[neighbor]:
dist[neighbor] = alt
prec[neighbor] = node
relax()
intermediate = dist[:] # is fixpoint in absence of neg cycles
relax()
for node in range(n):
if dist[node] < intermediate[node]:
dist[node] = float('-inf')
return dist, prec, min(dist) == float('-inf')