-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dijkstra2.py
77 lines (68 loc) · 2.3 KB
/
Dijkstra2.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
from pythonds.graphs import PriorityQueue, Graph, Vertex
from numpy import inf,nan
class Graph2(Graph):
def addEdge(self,f,t,cost=0):
if f not in self.vertices:
nv = self.addVertex(f)
if t not in self.vertices:
nv = self.addVertex(t)
self.vertices[f].addNeighbor(self.vertices[t],cost)
self.vertices[t].addNeighbor(self.vertices[f],cost)
def get_path(aGraph, source, dest):
cur_node = dest
path = list([dest.id])
while cur_node!=source:
temp = cur_node.pred
path.append(temp.id)
cur_node = temp
#path.append(source.id)
return path
def getMin(queue):
min = [nan,inf]
for i in queue:
if i.getDistance()<min[1]:
min[0] = i
min[1] = i.getDistance()
queue.remove(min[0])
return min[0]
def dijkstra2(aGraph,start):
q = set([vertex for vertex in aGraph])
start.setDistance(0)
while len(q)>0:
u = getMin(q)
for neigh in u.getConnections():
alt = u.getDistance() + u.getWeight(neigh)
if alt < neigh.getDistance():
neigh.setDistance(alt)
neigh.setPred(u)
def show_graph(aGraph):
g = aGraph
print("Source Vertex=" + str(g.vertices[0].getDistance()))
print("1st Vertex=" + str(g.vertices[1].getDistance()))
print("2nd Vertex=" + str(g.vertices[2].getDistance()))
print("3rd Vertex=" + str(g.vertices[3].getDistance()))
print("4th Vertex=" + str(g.vertices[4].getDistance()))
print("5th Vertex=" + str(g.vertices[5].getDistance()))
print("6th Vertex=" + str(g.vertices[6].getDistance()))
print("7th Vertex=" + str(g.vertices[7].getDistance()))
print("8th Vertex=" + str(g.vertices[8].getDistance()))
return
def gen_graph(cost_matrix):
g = Graph2()
length = len(cost_matrix)
for i in range(length):
for j in range(length):
if cost_matrix[i][j]!=0:
g.addEdge(i,j,cost_matrix[i][j])
return g
def test_Dijkstra():
cost_matrix = [[0,1,4],[1,0,2],[4,2,0]]
#print(cost_matrix)
g = gen_graph(cost_matrix)
#print("Before Dijkstra-------------")
#show_graph(g)
dijkstra2(g,g.vertices[0])
#print("After Dijkstra--------------")
#show_graph(g)
print(get_path(g,g.vertices[0],g.vertices[2]))
return