DSA Graph: Dijkstra's Shortest Path

Dijkstra's algorithm finds the shortest path from a starting node to all other nodes in a weighted graph with non-negative edges.

Logic

Uses a Greedy approach with a Priority Queue (min-heap). We always "relax" the edges of the closest unvisited node.

// Pseudocode
pq.push({0, start});
while(!pq.empty()) {
    curr = pq.pop();
    for(neighbor : curr.edges) {
        if(dist[curr] + weight < dist[neighbor]) {
            dist[neighbor] = dist[curr] + weight;
            pq.push({dist[neighbor], neighbor});
        }
    }
}

Complexity: O((E + V) log V) with adjacency list and binary heap.