Shortest path problem

The shortest path problem in graph theory is the following: Given a weighted graph, (that is a set N of nodes, a set E of edges and a real-valued function f : E -> R), and given further two elements n, n' of N, find a path P from n to n', so that

-----
 
 /      f(p)
-----
p in P

is minimal among all paths connecting n to n'.

The most important algorithm for solving this problem is Dijkstra's algorithm. The algorithm only works in case that f is always greater or equal zero. Nodes in the graph will be labeled by the algorithm. length is the label containing the length of the shortest path from n to the node having this label, path is the path leading there.

Put the start node n into the set S. Label n with length=0, path="n".

While S is not empty, let s be the element of S with the lowest label:
   if s = n' :
     finished: The length is length(s), the path is path(s)
   For all neighbours m of s do:
     if m is not labeled or length(m) > length(s) + f( (s,m) ):
       label m with length(s) + f( (s,m) ) and path=path(s)+"m"
       put m into S
   Remove s from S
If you get here, then there is no path from n to n' . 

With a slight modification, this algorithm can also be used to compute shortest paths from n to every other node in one run.