Dijkstra's Shortest Path Algorithm

You are given as input a directed graph G=(V,E) where m=|E| and n=|V|. Each edge also has a nonnegative length. For each v in V, compute L(V) where L is the length of the shortest path from the source node s to v.

One might as why use Dijkstra's Algorithm if you can already find the shortest path via Breadth First Search. However, BFS actually only works when all the edge length are one. It only tells you how many edges it takes to get from s to v.

But then you can replace each edge e with with a directed path of length(e) edges. This will make the graph way too big. It is too wasteful and it won't be in linear time anymore.

Thirdly, you could always just add a large constant to each edge length so that there are no negative edge lengths. This seems plausible but then it will skew the shortest path results. If we add 5 to every edge length, a path with 10 edges will be increased by 50 while a path with only 5 edges would only be increased by 25.

Initialize:
X = {S} (vertices processed so far)
A[S] = 0 (computed shortest path distances)
B[S] = empty path [completed shortest paths]
Main Loop:
while (X != V) [when not all vertices have been processed]
     - among all edges (v, w) in E, with v in X and w not in X, pick one that minimizes A[v] + l(vw) [Dijkstra's greedy criterion]
     - call this edge (v*, w*)
     - add w* to X
     - set A[w*] := A[v*] + l(v*w*)
     - set B[w*] := B[v*] U (v*, w*)