寻找加权图G中src点到图中其他可抵达点的最短路径。我们用适应性强的优先队列去实现最小值提取，队列的选择有两种选择:
1.堆O((n+m)logn)
2.未排序的序列O(n^2)
当边的数量很少（m<n^2/logn)用堆，反之序列。
下面的代码中我们用堆实现。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#python3
def shortest_path_lengths(g, src):
d = {} #save the smallest weight from v to u
cloud = {} #map reachable v to its d[v] value
pq = AdaptableHeapPriorityQueue() #vertex v will have key d[v]
pqlocator = {} # map from vertex to its pq locator
#the source having distance 0 and the rest have infinite
for v in g.vertices():
if v is scr:
d[v] = 0
else:
d[v] = float(inf)
pqlocator[v]=pq.add(d[v], v) #save locator for future update
while not pq.is_empty():
key, u = pq.remove_min()
cloud[u] = key
del pqlocator[u]
for e in g.incident_edges(u): #incident_edges return a set of u's edges
v = e.opposite(u) #return the other side of the edge
if v not in cloud:
wgt = e.element() #return the weight
if d[u]+wgt < d[v]:
d[v] = d[u]+wgt #update the distance make sure it only gets smaller
pq.update(pqlocator[v], d[v], v)
return cloud # only include reachable vertices with shortest distance from src
下面代码输出这个以src为源顶点的最小路径树。1
2
3
4
5
6
7
8
9
10
11#python3
def shortest_path_tree(g, s, cloud):
tree = {}
for u in cloud:
if u is not s:
for e in g.incident_edges(u, False): ###!!!!the set of INCOMING edges！！！
v = e.opposite(u)
wgt = e.element()
if wgt+cloud[v] == cloud[u]: ###important step
tree[u] = e
return tree # a dict(graph) of shortest edges
