Dijkstra’s Algorithm

• similar to Prim’s MST, we generate an SPT (shortest path tree) with a given source as a root
• does NOT work for graphs with negative weight edges
• works for both undirected and directed graphs

Implementation Algorithm

spt-set = []
non-spt-set = [all vertices]
for each v in non-spt-set
	v.key-value = infinity
first-vertex.key-value = 0
while non-spt-set != empty O(V)
	u = non-spt-set.extractMin() // by key-value - removes u from min-queue O(lgV)
	spt-set.add(u)
	for each v adjacent to u Θ(E) or O(E) how graph is represented
		if [(u,v).edge-weight + u.key-value] < v.key-value
			v.key-value = (u,v).edge-weight + u.key-value

Time Complexity

• If the input graph is represented with an adjacency matrix, then O(V²)
• If the input graph is represented with an adjacency list, then the time complexity of Prim’s algorithm can be reduced to O(ElogV) with the help of a binary heap