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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
| '''
Dijkstra 变形。
一题意：
要求数 最短路径 有多少条。
count[s] = 1
(v的加入对w点而言)
如果找到更短的路径： count[w] = count[v]
# 原有 count[w] 作废，被替代。
# 对dist[w]更新，此时v-w就在最短路径上，
# 最短路径数量就是之前v的最短路径数量。
(对w点而言)
如果找到等长的路径： count[w] += count[v]
# 这里是易错点，不是count[w] = count[v] + 1
# 因为w 和 v之间是只有一条路没错，但是count[v]可能是许多条路径，
# 所以 v 带给 w 的最短路径 数量的增加，是count[v] 条，而不是1 条。
# 所以 是在 count[w] 原有基础上 增加 count[v] 条最短路径。
二题意：
要求边数最少的最短路径。
严格说，这个问题，在之前已经被解决过了。
我们在Dijkstra的dist变化方法不变的前提下，设置count来专门计数边的数量，而不像dist一样记录边的权重。
count[s] = 0
如果找到更短的路径： count[w] = count[v] + 1 # v-w 在最短路径上。
如果找到等长路径： count[w] = count[v] + 1 老师说错了，不需要改变。
count[w] 不做改变，就可以了。
'''
'''
(v0) 2 (v1)
1 1 1 9
(v2) 2 (v3) 10 (v4) 5 (v7)
5 8 4 6
(v5) 1 (v6)
'''
class Graph():
def __init__(self,n_vertices):
self.n_vertices = n_vertices
self.G = [[float('inf') for _ in range(n_vertices)] for _ in range(n_vertices)]
def add_edge(self,pro_vertices,new_vertices,edge_weight):
self.G[pro_vertices][new_vertices] = edge_weight
self.G[new_vertices][pro_vertices] = edge_weight
def show_Graph(self):
for i in self.G:
print(i)
graph = Graph(8)
graph.add_edge(0,1,2)
graph.add_edge(0,3,1)
graph.add_edge(1,3,1)
graph.add_edge(1,4,9)
graph.add_edge(2,0,1)
graph.add_edge(2,5,5)
graph.add_edge(3,2,2)
graph.add_edge(3,4,10)
graph.add_edge(3,5,8)
graph.add_edge(3,6,4)
graph.add_edge(4,6,6)
graph.add_edge(6,5,1)
graph.add_edge(4,7,5)
graph.show_Graph()
print(' \n')
class data():
def __init__(self,Vertex_num):
self.dist = [float('inf') for _ in range(Vertex_num)]
self.path = [-1 for _ in range(Vertex_num)]
self.collected = [False for _ in range(Vertex_num)]
self.Number_of_edges = [0 for _ in range(len(graph.G))]
self.Number_of_pages = [1 for _ in range(len(graph.G))]
def Dijkstra(s,data):
while 1:
v = Find_Smallest_Dist(s,data)
if v == None:
return '最短路径构建结束',data
data.collected[v] = True
for w in near_Node(v):
if data.collected[w] == False:
dist_weight = graph.G[v][w]
if data.dist[w] > data.dist[v] + dist_weight:
data.dist[w] = data.dist[v] + dist_weight
data.path[w] = v
data.Number_of_edges[w] = data.Number_of_edges[v] + 1
data.Number_of_pages[w] = data.Number_of_pages[v]
elif data.dist[w] == data.dist[v] + dist_weight:
data.Number_of_pages[w] += data.Number_of_pages[v]
print(data.dist,'改变成的dist')
def Find_Smallest_Dist(s,data):
data.dist[s] = 0
uncollected_list = [i for i in range(len(data.dist)) if data.collected[i] == False]
print(uncollected_list,'没收集到!!!')
for i in uncollected_list:
if data.dist[i] == min([data.dist[i] for i in uncollected_list]):
print(i,' 没收集的最小dist对应位置')
print(data.dist[i],' 没有收录的最小dist值')
return i
def near_Node(v):
near_Node = [w for w in range(len(graph.G[v])) if graph.G[v][w] != float('inf') ]
return near_Node
def path_Smallest(v,data):
list_in = []
list_out = []
while v != -1:
list_in.append(v)
v = data.path[v]
for i in range(len(list_in)):
list_out.append(list_in.pop())
print(list_out)
return list_out
d = data(8)
Dijkstra(0,d)
print(d.dist)
p = path_Smallest(5,d)
print('0到5的最短路径为',p)
print('从0点到各个点的边数，做成列表是：',d.Number_of_edges)
print('从0点到各个边的路径数，做成列表是：',d.Number_of_pages)
|