Skip to content

Instantly share code, notes, and snippets.

@yasufumy
Created February 19, 2019 05:39
Show Gist options
  • Save yasufumy/f875dbb665e8347771245d7fd0bedfe4 to your computer and use it in GitHub Desktop.
Save yasufumy/f875dbb665e8347771245d7fd0bedfe4 to your computer and use it in GitHub Desktop.
INF = float('inf')
def bellman_ford(graph, weights, s):
d = {v: INF for v in graph}
d[s] = 0
pi = {s: None}
edges = [(u, v) for u, vs in graph.items() for v in vs]
for _ in range(len(graph) - 1):
for (u, v) in edges:
d_temp = d[u] + weights[u, v]
if d_temp < d[v]:
d[v] = d_temp
pi[v] = u
return d, pi
if __name__ == '__main__':
graph = {'A': ['B', 'C'],
'B': ['C', 'D', 'E'],
'C': [],
'D': ['B', 'C'],
'E': ['D']}
weights = {('A', 'B'): -1, ('A', 'C'): 4,
('B', 'C'): 3, ('B', 'D'): 2, ('B', 'E'): 2,
('D', 'B'): 1, ('D', 'C'): 5,
('E', 'D'): -3}
print(bellman_ford(graph, weights, 'A'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment