Dijkstra's Algorithm

Dijkstra's Algorithm finds the shortest path from a source node to all other nodes in a graph with non-negative weights. It uses a priority queue to explore nodes in order of increasing distance. This algorithm works by maintaining a set of visited nodes and, at each step, selecting the unvisited node with the smallest known distance to visit next. This process continues until all nodes have been visited, making it essential for network routing problems.

dist = map vertex -> Infinity

dist[src] = 0

heap = new MinHeap()

heap.insert(src, 0)

while heap is not empty:

    (u, d) = heap.extract()

    if u is not visited:

        relax(u, d)

function relax(u, d):

    mark u as visited

    for each neighbor v of u:

        alt = d + weight(u, v)

        if alt < dist[v]:

            dist[v] = alt

            heap.insert(v, alt)