 |
 |
 |
This algorithm finds the routes,by cost precedence.Let's assume that every cost is a positive number,and assume the same in the cost function c as in 5.4 paragraph.G may be a graph,a digraph,or even a combined one,which means that only some of its sides are directed.If we consider G as digraph,then every other case is fully covered as well since a no directed side can be considered a 2 directed sides of equal cost for every direction.
The idea for this algorithm is based on the fact that every m.r containing more than one side is the expansion of another m.r. containing a side less.This happens because all costs are considered as positive numbers.In this way the first route D(1) found by the algorithm will be one arc route,that is from the starting point to one of the sides directly connected to this starting point.The next route D(2) will be a one arc route itself,or a two arc route,but in this case will be an expansion of D(1).The whole procedure is a systematically, as to the numbers of sides, appliance of dynamic programming.
METHODOLOGY
Let's call D(1),D(2) the routes (found by the Dijkstra Algorithm)
for which { (cost of D(1)
) <= cost of D(2)<=...}.We
will show that every m.r. contains j
arcs maximum.
On contrary to our previous
symbolism,here we will name V(0) the starting point and V(1),...,V(n-1) the rest of
the peaks of G. We assign 2 numbers in every peak
with V(i)<>V(0) (as in the Prim Algorithm.) as follows.
e(i):=cost of
the so far known to us minimum route.
p(i):=the
pointer of the V(p(i))
peak for which the minimum route has already been found and the
direct connection of the V(i) with the V(p(i))
gives us the so far best route for the V(i)
peak,with cost e(i).
When another terminal m.r. for V(m) is found, we examine whether the direct connection of V(i) to V(m) gives us less cost,that is smaller e(i).In such a case we must set: p(i)=m.For initialization we consider p(i)=0,that means direct connection of V(i) to V(0),(obviously e(i)=infinite if the e(0i) route does not exist).
|
|
|
HTML PAGE DIRECTOR :Papaioannou Panagiotis