Graph Black Boxes (Implementation)

Question 1

BFS

Answer 1

input: G=(V,E), directed or undirected graph, start vertex s
output: for all vertices u reachable from s, dist(u) which is the distance from s to u.

for all u in V:
   dist(u) = infinity
dist(s) = 0
Q = [s] queue containing just s
While Q is not empty:
   u = eject(Q)
   for all edges (u,v) in E:
       if dist(v) = infinity:
           inject(Q,v)
           dist(v) = dist(u) + 1

Question 2

Dijkstra’s Algorithm

Answer 2

input: G=(V,E), directed or undirected graph, positive edge lengths = (l_e for e in E), start vertex s in V.
output: for all vertices u reachable from s, dist(u) which is the distance from s to u.

for all u in V:
dist(u) = infinity
prev(u) = nil

dist(s) = 0

H = makequeue(V) #priority queue

While H is not empty:
   u = deletemin(H)
   for all edges (u,v) in E:
       if dist(v) > dist(u) + l(u,v):
           dist(v) = dist(u) l(u,v)
           prev(v) = u
           decreasekey(H,v)