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
| import networkx as nx
from networkx.drawing.tests.test_pylab import plt
def Dijkstra(G, start, end):
RG = G.reverse();
dist = {};
previous = {}
for v in RG.nodes():
dist[v] = float('inf')
previous[v] = 'none'
dist[end] = 0
u = end
while u != start:
u = min(dist, key=dist.get)
distu = dist[u]
del dist[u]
for u, v in RG.edges(u):
if v in dist:
alt = distu + RG[u][v]['weight']
if alt < dist[v]:
dist[v] = alt
previous[v] = u
path = (start,)
last = start
while last != end:
nxt = previous[last]
path += (nxt,)
last = nxt
return path
G = nx.Graph()
a=[('你是','E11'),('你是','因为'),('你是','36D}'),('羽','E11'),('羽','E10'),('羽','E13'),('羽','E12'),('羽','E14'),('羽','因为'),('羽','E7'),('羽','E6'),('E10','Cyz'),('E10','奝'),('E10','anweilx'),('E10','群主'),('admin','E7'),('admin','E12'),('admin','因为'),('admin','E8'),('E12','奝'),('E12','群主'),('E12','Cyz'),('E12','奝'),('E14','Cyz'),('E14','36D}'),('E14','群主'),('printf','E5'),('printf', 'E6'), ('printf', 'E8'), ('printf', '爱你'), ('frank', '因为'), ('frank', 'E8'), ('不是', '因为'),('不是', 'E8'),('不是', 'E5'), ('不是', 'E4'), ('不是', 'E6'), ('不是', 'E1'), ('不是', '爱你'),('不是','E2'),('joker','E5'),('joker','E7'),('joker','因为'),('joker','E8'),('奝','E11'),('奝','E7'),('奝','E8'),('biu','E11'),('biu','因为'),('烟雨','E5'),('烟雨','E7'),('烟雨','E6'),('烟雨','E8'),('因为','就是'),('因为', 'K'), ('因为', '群主'), ('因为', 'Cyz'), ('因为', '奝'), ('E8', '就是'), ('E8', 'K'), ('E8', '群主'), ('E8', 'Cyz'),('E8', 'imagin'), ('E8', 'P3rh4ps'), ('E8', 'yaLddel'), ('E5', '就是'), ('E5', 'imagin'),('E5','P3rh4ps'),('E5','w1nd'),('E4','w1nd'),('E4','就是'),('E4','imagin'),('E7','就是'),('E7','Cyz'),('E7','imagin'),('E7','P3rh4ps'),('E7','w1nd'),('E6','就是'),('E6','K'),('E6','imagin'),('E6','P3rh4ps'),('E1','P3rh4ps'),('E1','imagin'),('爱你','就是'),('爱你','imagin'),('爱你','P3rh4ps'),('爱你','w1nd'),('爱你','flag{'),('E2','P3rh4ps'),('E2','就是'),('群主','E13'),('E13','Cyz')]
b=[]
c=[]
for i in a:
b.append(i[0])
c.append(i[1])
for i in range(len(b)):
G.add_edge(b[i],c[i],weight=1)
print('图中所有的边', G.edges())
print("________________________________________")
print(list(nx.all_shortest_paths(G,source='flag{', target='36D}')))
|
