Dijkstra’s Algorithm Pseudocode

Pseudocode Implementation

function Dijkstra(graph, source):

    create distance map
    for each node in graph:
        distance[node] = infinity
        visited[node] = false

    distance[source] = 0

    while there exists an unvisited node:

        current = node with smallest distance that is unvisited

        for each neighbor of current:
            if visited[neighbor] == false:
                
                new_distance = distance[current] + weight(current, neighbor)

                if new_distance < distance[neighbor]:
                    distance[neighbor] = new_distance

        visited[current] = true

    return distance

Optimized Version (Priority Queue)

function Dijkstra(graph, source):

    create distance map
    for each node:
        distance[node] = infinity

    distance[source] = 0

    priority_queue = min-heap
    push (0, source) into priority_queue

    while priority_queue is not empty:

        (current_distance, current_node) = pop from queue

        if current_distance > distance[current_node]:
            continue

        for each neighbor of current_node:

            new_distance = current_distance + weight(current_node, neighbor)

            if new_distance < distance[neighbor]:
                distance[neighbor] = new_distance
                push (new_distance, neighbor) into priority_queue

    return distance