Learn
Dijkstra's Algorithm
Dijkstra's Algorithm is a shortest path algorithm that finds the minimum distance from a source vertex to all other vertices in a graph with non-negative edge weights. It uses a greedy approach with a priority queue.
You greedily select the unvisited vertex with minimum distance and relax its edges. You use a min-heap to efficiently find the minimum distance vertex.
function dijkstra(graph, n, source):
dist = array of size n, initialized to infinity
dist[source] = 0
pq = min-priority queue
pq.push((0, source))
while pq is not empty:
(d, u) = pq.pop()
if d > dist[u]:
continue
for each edge (u, v, weight) from u:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
pq.push((dist[v], v))
return dist
Skip optimization: When you pop a vertex, skip it if its distance doesn't match the current known distance.
Why non-negative weights: The algorithm assumes processed vertices have final distances. Negative edges can invalidate this.
Applications: You use Dijkstra for GPS navigation, network routing protocols (OSPF), robot path planning, and game AI pathfinding.
Time complexity: with a binary heap.