Dijkstra's Shortest Path

About

An algorithm to find shortest path, meaning find the edge connections with smallest weight.

Don't use negative weight.

Array Solution

This algorithm will run on $O(V² + E)$ because of the way it uses to get the next lowest unseen node.

seen array has size V, and the while loop will run for each node on the graph in worst case, making it $V*V$.

A way to make it run on $O(logV)$ would be to use a minHeap to hold the weights.

Getting the next lowest unseen would be $O(1)$, and there would be no reason for the seen array since the seen nodes would be removed from the heap.

function hasUnvisited(seen: boolean[], weights: number[]): boolean {
    return seen.some((v, nodeI) => !v && weights[nodeI] < Infinity);
}

function getLowestUnvisited(seen: boolean[], weights: number[]): number {
    let idx = -1;
    let lowestDistance = Infinity;

    for (let i = 0; i < seen.length; i++) {
        if (seen[i]) continue;
        if (lowestDistance > weights[i]) {
            lowestDistance = weights[i];
            idx = i;
        }
    }
    return idx;
}

function dijkstra(graph: WeightedAdjList, source: number, target: number): number[] {
    const seen = new Array(graph.length).fill(false);
    const weights = new Array(graph.length).fill(Infinity);
    const path = new Array(graph.length).fill(-1);

    weights[source] = 0;
    while (hasUnvisited(seen, weights)) {
        const curr = getLowestUnvisited(seen, weights);
        seen[curr] = true;

        for (let edge of graph[curr]) {
            if (seen[edge.to]) continue;
            const carriedWeight = weights[curr] + edge.weight;
            if (carriedWeight < weights[edge.to]) {
                weights[edge.to] = carriedWeight;
                path[edge.to] = curr;
            }
        }
    }

    const bestPath: number[] = [];
    let bestCurr = target;
    while (path[bestCurr] !== -1) {
        bestPath.push(bestCurr);
        bestCurr = path[bestCurr];
    }
    bestPath.push(source);
    return bestPath.reverse();
}

The way this specific algorithm works is

1. Will start from the source node (Ex.: Node 0), and check how much it costs to go to each of the unseen neighbors (Node 1 and Node 2).

   1. After this check it will save:

      1. In weights how much it costs to get to Node 1 = 1 and Node 2 = 5.

      2. In path it will have that the best way yet to get to Node 1 and Node 2 is from Node 0.

2. Then it will check the next unseen node that has the lowest weight in weights. (So it will try to stay on the best path). In this example it will check now Node 1, and its unseen neighbors.

   1. After the check:

      1. In weights it will have that to get to Node 2 = 7 and Node 3 = 1. But we already know that there is a better path for Node 2 which is from Node 0, so reaching Node 2 from Node 1 is ignored.

      2. In path we have now that reaching Node 1 & 2 should be from Node 0 and reaching Node 3 should be from Node 1.

3. Step 2 is repeated until there are no more unseen nodes. The algorithm will prioritize paths with lowest weight and will override them if a better one is found.

4. At the end it just reconstruct the path to return it.

Heap Solution