0% found this document useful (0 votes)
60 views

Floyd Algorithm

Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
60 views

Floyd Algorithm

Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 12

Floyd Algorithm

❖Floyd’s algorithm: determines the shortest route between


any two nodes in the network. A n-node network as a
square matrix with n rows and n columns. Entry (i, j) is
the distance dij from node i to node j: which is finite if i is
linked directly to j, and infinite otherwise.
❖The idea: Given three nodes i, j, and k, it is shorter to go
from i to j passing through k if
(𝑑𝑖𝑘 + 𝑑𝑘𝑗 ) ≤ 𝑑𝑖𝑗 ➔ Replace route from i → j with
i → k → j. This is so-called triple operation.
1
k
dik dkj

i j
dij

❖ Step 0. Define the starting distance matrix D0 and node sequence matrix S0.
Set k = 1.
Matrix D0 Matrix S0
1 2 … j … n 1 2 … j … n

1 - d12 d1j d1n 1 - 2 … j … n

2 d21 - d2j d2n 2 1 - … j … n


… …

i di1 di2 dij din i 1 2 … j … n


… …

n dn1 dnj - n 1 2 … j … -

2
❖ General step k. Define row k and column k as pivot row and pivot column. Apply the
triple operation to each element dij in Dk-1, for all i and j.

❖ If the condition (𝑑𝑖𝑘 + 𝑑𝑘𝑗 ) ≤ 𝑑𝑖𝑗 ; (𝑖 ≠ 𝑗, 𝑗 ≠ 𝑘, 𝑖 ≠ 𝑘) is satisfied, make the


following changes:
– (a) Create Dk : by replacing dij in Dk-1 with (𝑑𝑖𝑘 + 𝑑𝑘𝑗 ).

– (b) Create Sk : by replacing sij in Sk-1 with k. Set k = k + 1. If k = n + 1, stop;

else repeat step k.

3
❖ Step k of the algorithm can be explained as follows:
Here, row k and column k define the current pivot row and column. Row i represents any of
the rows 1, 2, … and k - 1, and row p represents any of the rows k+1, k+2, …, and n.
Similarly, column j represents any of the columns 1,2, …, k-1,and column q represents any
of the columns k+1, k+2,…, n.

❖ The triple operation can be applied as follows: If the sum of the elements on the pivot
row and the pivot column (shown by squares) is smaller than the associated
intersection element (shown by a circle), then it is optimal to replace the intersection
distance by the sum of the pivot distances.

4
Triple Operation

1 … j … k n
1
...
i dij dik
...
k dkj

...
n

5
❖ After n steps, we can determine the shortest route between nodes i and j from the
matrices Dn and Sn using the following rules:
1. From Dn, dij gives the shortest distance between nodes i and j.
2. From Sn, determine the intermediate node k = sij that yields the route i→k→j.
❖ If sik = k and skj = j, stop; all the intermediate nodes of the route have been found.
❖ Otherwise, repeat the procedure between nodes i and k and between nodes k and j.

6
❖ Example (From book of Hamdy Taha): For the network including 5 nodes,
find the shortest routes between every two nodes. The distances (in miles)
are given on the arcs. Arc (3, 5) is directional, no traffic is allowed from
node 5 to node 3. All the other arcs allow two-way traffic.

5
2 4
4
3
6 5
1 10
15
3

7
D0 S0
1 2 3 4 5 1 2 3 4 5
1 - 3 10 ∞ ∞ 1 - 2 3 4 5
2 3 - ∞ 5 ∞ 2 1 - 1 4 5
3 10 ∞ - 6 15 3 1 1 - 4 5
4 ∞ 5 6 - 4 4 1 2 3 - 5
5 ∞ ∞ ∞ 4 - 5 1 2 3 4 -

5
2 4
4
3
6 5
1 10
15
3

8
D1 S1
1 2 3 4 5 1 2 3 4 5
1 - 3 10 ∞ ∞ 1 - 2 3 4 5
2 3 - 13 5 ∞ 2 1 - 1 4 5
3 10 13 - 6 15 3 1 1 - 4 5
4 ∞ 5 6 - 4 4 1 2 3 - 5
5 ∞ ∞ ∞ 4 - 5 1 2 3 4 -

5
2 4
4
3
6 5
1 10
15
3

9
D2 S2
1 2 3 4 5 1 2 3 4 5
1 - 3 10 8 ∞ 1 - 2 3 2 5
2 3 - 13 5 ∞ 2 1 - 1 4 5
3 10 13 - 6 15 3 1 1 - 4 5
4 8 5 6 - 4 4 2 2 3 - 5
5 ∞ ∞ ∞ 4 - 5 1 2 3 4 -

5
2 4
4
3
6 5
1 10
15
3

10
D3 S3
1 2 3 4 5 1 2 3 4 5
1 - 3 10 8 25 1 - 2 3 2 3
2 3 - 13 5 28 2 1 - 1 4 3
3 10 13 - 6 15 3 1 1 - 4 5
4 8 5 6 - 4 4 2 2 3 - 5
5 ∞ ∞ ∞ 4 - 5 1 2 3 4 -

5
2 4
4
3
6 5
1 10
15
3

11
D4 S4
1 2 3 4 5 1 2 3 4 5
1 - 3 10 8 12 1 - 2 3 2 4
2 3 - 11 5 9 2 1 - 1 4 4
3 10 11 - 6 10 3 1 1 - 4 4
4 8 5 6 - 4 4 2 2 3 - 5
5 12 9 10 4 - 5 4 4 4 4 -

5
2 4
4
3
6 5
1 10
15
3

12

You might also like