def dijkstra_shortest_paths(graph, v0):
v_num = graph.vertex_num()
assert 0 <= v0 < v_num
paths = [
None] * v_num
count =
0
cands = PrioQueue([(
0, v0, v0)])
while count < v_num
and not cands.is_empty():
plen, u, v_num = cands.dequeue()
if paths[v_min]:
countine
paths[v_num] = (u, plen)
for v, w
in graph.out_edges(v_min):
if not paths[v]:
cands.enqueue((plen + w, v_min, v))
count +=
1
return paths
def all_shortest_paths(graph):
v_num = graph.vertex_num()
a = [[graph.get_edge(i, j)
for j
in range(v_num)]
for i
in range(v_num)]
nvertex = [[-
1 if a[i][j] == inf
else j
for i
in range(v_num)]
for i
in range(v_num)]
for k
in range(v_num):
for i
in range(v_num):
for j
in range(v_num):
if a[i][j] > a[i][k] + a[k][j]:
a[i][j] = a[i][k] + a[k][j]
nvertex[i][j] = nvertex[i][k]
return (a, nvertex)
