Dijkstra's Shortest Path Algorithm

How Dijkstra's Algorithm Works

Dijkstra's algorithm finds the shortest path between nodes in a graph. It picks the unvisited node with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. This process repeats until all nodes have been visited.

Color representation:

• Red node is the starting node
• Blue nodes are unvisited
• Yellow node is the current node being explored
• Green nodes have been visited

function dijkstra(graph, startVertex):
    distances = {}
    previousVertices = {}
    pq = PriorityQueue()

    for each vertex in graph:
        if vertex == startVertex:
            distances[vertex] = 0
            pq.add(vertex, 0)
        else:
            distances[vertex] = INFINITY
            pq.add(vertex, INFINITY)
        previousVertices[vertex] = null

    while not pq.isEmpty():
        currentVertex = pq.extractMin()
        visualize(currentVertex, distances, previousVertices)

        for each neighbor in graph.getNeighbors(currentVertex):
            distance = distances[currentVertex] + graph.getWeight(currentVertex, neighbor)
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previousVertices[neighbor] = currentVertex
                pq.decreaseKey(neighbor, distance)

    return distances, previousVertices

function visualize(currentVertex, distances, previousVertices):
    // Update UI to show:
    // 1. Current vertex being processed
    // 2. Known shortest distances to each vertex
    // 3. The path to each vertex (using previousVertices)
    // 4. Highlight the edges of the shortest paths found so far