dijkstra

Posted on
Words count in article: 513 words | Reading time ≈ 3 mins

Dijstra algorithm

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
"""
python algorithm for single source shortest path
"""
from collections import defaultdict

class Graph:
	## find vertex with minium dist value, 
	## from the set of vertices still in the queue
	def min_distance(self, dist, queue):
		minimum = float('inf')
		min_index = -1

		## from dist array, pick one which has min value and still in queue
		for i in range(len(queue)):
			if dist[i] < minimum and i in queue:
				minimum = dist[i]
				min_index = i 
		return min_index

	## print shortest path from source to j using parent array
	def print_path(self, parent, j):
		## base: if j is source
		if parent[j] == -1:
			print(j)
			return 
		self.print_path(parent, parent[j])

	## print constructed distince array
	def print_solution(self, dist, parent):
		src = 0
		print('vertex \t \tdistance from source \tpath')
		for i in range(1, len(dist)):
			print('\n%d--> %d \t \t%d \t\t\t\t\t' %(src, i, dist[i]))
			self.print_path(parent, i)

	## dijstra using adjacent matrix
	def dijkstra(self, graph, src):
		row, col = len(graph), len(graph[0])

		## init all distances to infinite, parent store shortest path tree
		dist = [float['inf']] * row 
		parent = [-1] * row 

		## src vertex would be 0
		dist[src] = 0
		queue = []
		for i in range(row):
			queue.append(i)

		while queue:
			## pick minimus dist vertex from set of vertices still in queue
			u = self.min_distance(dist, queue)
			queue.remove(u)

			## update dist value and parent index of the adjacent vertices of the picked vertex
			## consider only those vertices which are still in queue
			for i in range(col):
				## update dist[i] only if it is in the queue, and there is 
				## an edge from u to i, and the total weight of path from src to i througth u
				## is smaller than current dist[i]
				if graph[u][i] and i in queue:
					if dist[u] + graph[u][i] < dist[i]:
						dist[i] = dist[u] + graph[u][i]
						parent[i] = u 

		## print constructed distance
		self.print_solution(dist, parent)

	g = Graph()

	## adjacent matrix each row represents the dist from a node to the target node
	## row 1: 0->1: 4  0->7:8
	graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], 
			[4, 0, 8, 0, 0, 0, 0, 11, 0], 
			[0, 8, 0, 7, 0, 4, 0, 0, 2], 
			[0, 0, 7, 0, 9, 14, 0, 0, 0], 
			[0, 0, 0, 9, 0, 10, 0, 0, 0], 
			[0, 0, 4, 14, 10, 0, 2, 0, 0], 
			[0, 0, 0, 0, 0, 2, 0, 1, 6], 
			[8, 11, 0, 0, 0, 0, 1, 0, 7], 
			[0, 0, 2, 0, 0, 0, 6, 7, 0] 
			]
	g.dijkstra(graph, 0)