Networking Reference
In-Depth Information
if (marked[node]
0)
then Find_all_minimal_paths_from(node) ;}
5
sb[ k ][ i ]' in the k th adjacency array, is the successor ' i ' of the
node with index ' k '. A zero entry in the marked array (marked[node]
where 'node
5
0) indicates
5
that the successor with index 'node' has not been visited.
With this fragment, the initial problem of finding all minimal paths from the
source to the sink is decomposed into problems of the same type as the original
problem. Each of these sub-problems is in turn decomposed into sub-problems until
the process yields sub-problems with trivial solutions. These are handled by the
bottom of the recursive call, given in the next fragment:
if (k
n) then {
fpath[fp_cnt]
5
n;
Save_the_path();
return;}
5
This fragment is executed whenever the sink, with index ' n ', is reached.
An essential statement
0' after the return
from a recursive call. This statement effectively changes the state of node ' k '
from 'visited' to 'non-visited'. This permits the other recursive calls to explore
paths passing through node ' k ' which otherwise would be impossible. The state-
ment 'fp_cnt
is the assignment 'marked[ k ]
5
fp_cnt 1' decrements the path length counter 'fp_cnt', because
after the statement 'marked[ k ] 5 0', node ' k ' no longer belongs to the current
path.
Executing the algorithm for the network in Figure 2.2 , which possesses a cycle
(2,3,4,2), generates 18 distinct directed minimal paths: (1258, 12368, 123478,
123458, 12378, 1268, 1368, 13478, 134258, 134268, 13458, 1378, 1478, 14258,
142368, 142378, 14268, 1458).
If all minimal paths are to be generated, including non-directed minimal paths,
then the adjacency arrays nb[], containing the indices of all neighbours (not only
the successors) should be used. The number of all possible minimal non-directed
paths from the source node '1' to the sink node '8', for the network in Figure 2.2 ,
then increases to 60.
An algorithm for determining all minimal cut sets in a network can be found in
(Yeh et al. 2012).
5
2.5 Determining the Smallest-Cost Paths from the Source
Section 2.4.1 discusses a breadth-first search algorithm for determining the shortest
st path in terms of number of edges between the source s and the sink t . There
are a number of applications where each edge ( i , j ) is associated with a particular
non-negative weight (cost) w ( i , j )and it is required to determine the path with the
smallest cost from the source to each node of the network.
Search MirCeyron ::




Custom Search