-
Notifications
You must be signed in to change notification settings - Fork 9
/
short_path.py
96 lines (83 loc) · 1.83 KB
/
short_path.py
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date : 2016-11-07 18:46:17
# @Author : Liu Jian (461698053@qq.com)
# @Link : ${link}
# @Version : $Id$
from heapq import heappop, heappush
from copy import deepcopy
inf = float('inf')
'''
参数说明:
G:
D:
u:
v:
k:
'''
def relax(W, u, v, D, P):
"""
松弛技术
"""
d = D.get(u, inf) + W[u][v]
if d < D.get(v, inf):
D[v], P[v] = d, u
return True
def bellman_ford(G, s):
"""
最短路径:Bellman-Ford算法
"""
D, P = {s: 0}, {}
for rnd in G:
changed = False
for u in G:
for v in G[u]:
if relax(G, u, v, D, P):
changed = True
if changed:
raise ValueError('negative cycle!')
return D, P
def dijkstra(G, s):
"""
最短路径:Dijkstra算法
"""
D, P, Q, S = {s: 0}, {}, [(0, s)], set()
while Q:
_, u = heappop(Q)
if u in S:
continue
S.add(u)
for v in G[u]:
relax(G, u, v, D, P)
heappush(Q, (D[v], v))
return D, P
def johnson(G):
"""
最短路径算法:Johnson,基于多对多的稀疏图
"""
G = deepcopy(G)
s = object()
G[s] = {v: 0 for v in G}
h, _ = bellman_ford(G, s)
del G[s]
for u in G:
for v in G:
G[u][v] += h[u] - h[v]
D, P = {}, {}
for u in G:
D[u], P[u] = dijkstra(G, u)
for v in G:
D[u][v] += h[v] - h[u]
return D, P
def floyd_warshall(G):
"""
最短路径算法:Floyd Warshall,仅考虑距离
"""
D = deepcopy(G)
for k in G:
for u in G:
for v in G:
D[u][v] = min(D[u][v], D[u][k], +D[k][v])
return D
if __name__ == '__main__':
main()