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.