SSP: Dijkstra's Algorithm

!(Dijkstra)[https://upload.wikimedia.org/wikipedia/commons/e/e4/DijkstraDemo.gif]

This algorithm solves the (single-source shortest-path problem) s-ss-p problem on a weighted, directed graph for the case in which all edge weights are non negative. A good implementation of this algorithm is faster than BF.

This algorithm maintains a set S of vertices whose final s-p weights from the source s have already been determined. The algorithm repeatedly selects the vertex u $\in$ V-S with the minimum shortest-path estimate, adds u to S, and relaxes all edges leaving u.

DIJKSTRA (G,w,s)
    initializeSingleSource(G,s)
    S = {}
    Q = G.V // priority queue keyed by d values
    while Q is not empty
        u = Q.getMin()
        S = S U {u}
        for v in G.Adj[u]
            relax (u,v,w)

We say that it uses a greedy strategy because it chooses the lightest (or closest) vertex in V-S to add to set S. While greedy algorithm often do not yield optimal result due to their greedy strategies, this does because each time we add a vertex u to S we have that the u.d = $\delta(s,u)$

Finally. note that if we run this algorithm on a weighted directed graph G with a non-negative weight function w and source s, then at termination, the predecessor subgraph $G_p$ is a shortest-path tree rooted at s.