Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@nickponline
Last active September 20, 2016 03:46
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nickponline/8a25d6a393de50580dfe440693c6abc5 to your computer and use it in GitHub Desktop.
Save nickponline/8a25d6a393de50580dfe440693c6abc5 to your computer and use it in GitHub Desktop.
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)])
visited.add(child)
q.put(next_state)
# 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