4.4. Shortest paths in a graph

• We are given a directed graph G = (V,E) with a starting node S.We assume that s has a path to every other node in G.
• Each edge e has a length l_e≥ 0, which it the cost of traversing e.
• For each path P, the length of P(l(P)) = ∑ of all edges in P.
  

–>Goal of the algorithm: Determine the shortest path from S to every other node in the graph.

Dijkstra's algorithm(G,l)

Let S be the set of explored nodes

For each u in S, store the distance d(u)

Initially, S = {s} and d(s) = 0
While S ≠ V:

Select a node v ∉ S with at least one edge from S for which:
d'(v) = min_{e = (u,v):u in S} + l_e is as small as possible
The formula above for d'(v) simply means that we choose a node v ∉ S that minimizes the path through S to u followed by the edge (u,v)
Then add v to S and delete d(v) = d'(v)

EndWhile