Skip to content

Instantly share code, notes, and snippets.

Last active September 20, 2016 03:46
What would you like to do?
import collections
import Queue
def dijkstra(graph, source, sink):
q = Queue.PriorityQueue()
q.put((0, source, []))
visited = set([source])
while not q.empty():
length, node, path = q.get()
# Found a path return the capacity
if node == sink:
cap = None
for a, b in path:
if cap is None or graph[a][b] < cap:
cap = graph[a][b]
return cap, path
# Visit next node
for child in graph[node].keys():
if not child in visited and graph[node][child] > 0:
next_state = (length+1, child, path + [(node, child)])
# No paths remaining
return None, None
def max_flow(graph, source, sink):
flow = 0
while True:
capacity, path = dijkstra(graph, source, sink)
if not capacity: return flow
for a, b in path:
graph[a][b] = graph[a].get(b, 0) - capacity
graph[b][a] = graph[b].get(a, 0) + capacity
flow += capacity
return flow
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment