Dijkstra's Algorithm

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

Cannot be used on negative edge weights

Dijkstra’s algorithm assumes all edge weights to be positive to properly function. During the initialisation of the source node’s dist value, 0 is assigned as the minimum value, which is no longer the case if negative edge weights exist.

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

	source.dist <- 0

	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

Manual Analysis §

One method of applying Prim’s algorithm manually is as follows:

#todo

1. Construct a table with the columns being nodes.
2. At each row, every entry has a value of $(\infty ,\text{nil})$, which specifies (distance,parent).
3. At row 1, set the lexicographical first node to have a distance of 0, i.e. $(0,nil)$
4. At row 2, add the lexicographical first node as the row name (specifying the nodes belonging to the final MST) and update the distance and parent values of any connecting edges.
5. Circle the edge with the minimum distance. If there is a tie, select with lexicographical order.
6. Add the node (looking at column name) to the tree in the next row.
7. Repeat steps 4-6, remembering to update nodes and only selecting minimum edges not belonging to the Tree.

%%🖋 Edit in Excalidraw, and the dark exported image%%

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 §