Dijkstra's Algorithm

Dijkstra’s algorithm finds the shortest path from a starting node to any other node, i.e. it generates a shortest-path tree. It can be used to solve the single source shortest path problem.

It should not be used on graphs with negative weight cycles

Pseudocode §

Algorithm Dijkstra(Graph,source):
	unexplored_nodes ← Min Priority Queue ADT
	cwn ← Node ADT
	
	For each vertex v in G do: #O(|V|)
		v.dist ← ∞
		v.parent ← None
	End do

	Enqueue source to PQueue with priority source.dist (i.e. 0)
	
	While unexplored_nodes is not empty do: #O(|V|)
		cwn ← Dequeued element from unexplored_nodes
		Remove cwn from unexplored nodes
		For each neighbour n of cwn do: #O(|V|)
			this_dist ← cwn.dist + weight(cwn-n)
			if this_dist < n.dist then:
				n.dist ← cwn.dist + weight(cwn-n)
				n.parent ← cwn
			End if
		End do
	End do
	Return nodes.dist, nodes.parent
	
End Algorithm

Complexity §

Time Complexity:

$O(|V|)$ for initialising vertices + $O(|V|\ast |V|)$ for checking every neighbour for each node = $O(|V|+|V{|}^2)=O(|V{|}^2)$

Implementation §

Dijkstra.py