Understanding Dijkstra's Algorithm

Dijkstra's algorithm solves the single-source sohrtest path problem in graphs where all edge weights are non-negative. Given a source node s, it computes the shortest distance from s to every other reachable node in the graph.

Core Intuition

• Initially, only the distance from the source to itself is known (0), while all others are set to infinity.
• In each step, select the unvisited node with the smallest known distance and finalize its shortest path.
• Use this node to relax its neighbors: if a shorter path is found through this node, update the neighbor’s distance.
• Repeat until all nodes are processed.

Why does it work?
Since edge weights are non-negative, once we pick the closest unvisited node, no future path can yield a shorter distance to that node—this allows the greedy choice to be globally optimal.

Data Structures and Setup

Assume a graph with n nodes labeled from 1 to n, stored using an adjacency list:

• graph[u]: List of outgoing edges from node u, each represented as (v, weight).
• dist[u]: Current shortest known distance from source to u. Initialize to ∞ except for the source.
• prev[u]: Predecessor of node u on the shortest path (used to reconstruct paths).
• done[u]: Boolean flag indicating whether the shortest path to u has been finalized.
• minHeap: A priority queue storing pairs (distance, node), ordered by distance (smallest first).

Heap-Optimized Dijkstra: Pseudocode

// Constants
INFINITY = ∞

// Graph representation
List<List<Pair>> graph[1..n]   // Each element: (neighbor, edge_weight)

// State arrays
dist[1..n]     // Shortest distances
prev[1..n]     // Path predecessors
done[1..n]     // Finalized nodes

// Priority queue: (distance, node)
PriorityQueue<Pair> heap;

Algorithm Procedure

function dijkstra(source):
    // Initialization
    for i = 1 to n:
        dist[i] = INFINITY
        prev[i] = -1
        done[i] = false

    dist[source] = 0
    heap.push( (0, source) )

    while not heap.isEmpty():
        (curDist, u) = heap.popMin()

        // Skip outdated entries in heap
        if done[u]:
            continue

        done[u] = true   // Lock in shortest distance

        // Relax all outgoing edges from u
        for each (v, weight) in graph[u]:
            if not done[v]:
                newDist = curDist + weight
                if newDist < dist[v]:
                    dist[v] = newDist
                    prev[v] = u
                    heap.push( (newDist, v) )

Key Notes

• The same node may appear multiple times in the heap due to updates. We skip any popped entry whose node was already finalized (done[u] == true).
• This lazy deletion approach avoids complex heap modifications and works efficiently in practice.
• Time complexity: O((n + m) log n), where m is the number of edges.

Main Program: Input and Execution

A complete example handling input and calling Dijkstra:

function main():
    read n, m   // Number of nodes and edges

    // Initialize graph
    for i = 1 to n:
        graph[i] = empty list

    // Read m directed edges: u → v with positive weight w
    for i = 1 to m:
        read u, v, w
        graph[u].append( (v, w) )

    read src   // Source node
    dijkstra(src)

    // Output shortest distances
    for i = 1 to n:
        if dist[i] == INFINITY:
            print "No path from", src, "to", i
        else:
            print "Distance from", src, "to", i, "=", dist[i]

Reconstructing Paths

To retrieve the actual path from source to target t:

function printPath(src, t):
    if dist[t] == INFINITY:
        print "No path exists"
        return

    path = []
    current = t
    while current != -1:
        path.append(current)
        current = prev[current]

    reverse(path)  // Now path goes from src to t
    print path

Applicability and Alternatives

Dijkstra requires non-negative edge weights. If negative weights exist:

• The greedy assumption fails—shorter paths might emerge later via negative edges.
• In such cases, use Bellman-Ford or SPFA.

When to Use Which Algorithm?