Dijkstra’s algorithm

This is an algorithm to solve the shortest path problem in undirected graphs or directed graphs . It is based on Breath-first search but uses a priority queue instead of just a queue. It requires positive edge lengths .

Dijkstra(G,w,s):
	Input: graph G=(V,E) with weights w(e) and a start vertex s.
	Output: For all vertices reachable from s a shortest path length dist
1. for all u in V
	1.1 dist(u) = inf
	1.2 prev(u) = nil
2. dist(s) = 0
3. H = makequeue(V)
4. while H is not empty:
	4.1 v = deletemin(H)
	4.2 for each {v,z} in E:
		4.2.1 if dist(z) > dist(v) + w(v,z):
			4.2.1.1 dist(z) = dist(v) + w(v,z)
			4.2.1.2 prev(z) = v
			4.2.1.3 decreasekey(H,z)
5. output dist

Correctness

Run time

To initialise and takes time.

To fetch the key takes time from Priority queue data structure. This is executed times so takes .

We iterate over each edge twice and for each iteration we might have to call decreasekey which takes time from Priority queue implementation. So this takes .

All together this takes .