Dijkstra Algorithm Tutorial

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: $O((V + E) \log V)$ with a binary heap.

Space complexity: $O(V + E)$ for the graph and priority queue.