Dijkstra's Algorithm

Dijkstra's algorithm is a solution to the shortest path problem for graphs with positively-weighted edges.

Approach: Greedy

Dijkstra's algorithm centers around this property: of all the edges leaving the source, the shortest edge must be in the shortest path.

To reach the shortest path, Dijkstra always picks the shortest edge leaving the known nodes.

Implementation

Dijkstra(G, w, s) {
    // initialize
    for all v in V:
        d[v] = infty
        pi[v] = null
    d[s] = 0
    while Q is not empty:
        u = Q.extractMin()
        for all v in adj[u]:
            if d[v] > d[u] + w(u,v):
                d[v] = d[u] + w(u,v)
                pi[v] = u