Flight planning software minimization algorithm
Ref: "Data Structures & Algorithms", Aho, Hopcroft & Ullman, 1983
(who needs the stinkin' web when you have the books next to you?!]
begin
S:= {1};
for i := 2 to n do D[i] := C[1,i]; # initialize D
for i := 1 to n-1 do begin
choose a vertex w in V-S such that D[w] is a minimum;
add w to S;
for each vertex v in V-S do
D[v] := min(D[v],D[w]+c[w,v]);
end;
end;
computes the cost (you choose what you consider to be cost) of the
shortest path from vertex 1 to every vertex of the directed graph.
S is the set of vertices, D[] is the path
Then, of course, we can also consider the All-Pairs shortest path
problem, and I quote from AHU, "suppose we have a labeled digraph that
gives the flying time on certain routes connecting cities...."
Take a look at R.W. Floyd's for weighted digraphs.
Have fun!
|