Ethan

Floyd algorithm
Floyd's algorithm is more general than that of Dijkstra, since it determines the shortest path between any two nodes in the network.
* The algorithm represents a network of n nodes as a square matrix of order n, the matrix C call. Thus, the value Cij is the cost to go from node i to node j, initially in the absence of an arc between them, the value Cij will be infinite.
*Define another matrix D, also square of order n, whose elements will be the predecessor nodes on the path to the source node, ie, the value Dij represent the predecessor node j in the shortest path from ito j. Initially begins with paths of length 1, so that Dij = i.
* The diagonals of both matrices represent the cost and the predecessor node to move from one node to itself, so that no usewill be blocked.
The next steps in implementing the Floyd algorithm are:
* Form the initials C and D matrices.
* K = 1 is taken.
* You select the row and column k of matrix C and then for i and j with i ≠ k, j ≠ k and i ≠ j, do:
If (Cik + CKJ) <Dij = Cij → DKJ and Cij = Cik + CKJ
Otherwise, let the matrices as they are.
* If k ≤ n, we increase k by one and repeat the previousstep, otherwise stop the iterations.
* The final matrix C contains the optimal cost to go from one vertex to another, while the matrix Dcontains the penultimate vertices of the optimal paths joining two vertices, which can reconstruct any optimal path to get from one vertex to another.
Example: Apply the algorithm of Floyd on the following graph for the shortest paths between any twonodes. The arc (3, 5) is directional, so it is not allowed any traffic from node 5 to node 3. All other arcs allow traffic in both directions.

Initialize the arrays:
We take k = 1:
We i = 2 (i ≠ k):
* j = 3 (j ≠ k, i ≠ j): C [2,1] + C [1.3] = 3 +10 = 13 <C [2,3] = ∞, therefore we do:
C [2,3] = 13 and D [2,3] = 1.
* j = 4 (j ≠ k, i ≠ j): C [2,1] + C [1.4] = 3 + ∞ = ∞, do not change anything,we can not reach 2 to 4through 1 .
* j = 5 (j ≠ k, i ≠ j): C [2,1] + C [1.5] = 3 + ∞ = ∞, do not change anything, we can not reach 2 to 5through 1 .
* We i = 3 (i ≠ k):
* j = 2 (j ≠ k, i ≠ j): C [3,1] + C [1.2] = 10 +3 = 13 <C [3.2] = ∞, therefore we do:
C [3.2] = 13 and D [3.2] = 1.
* j = 4 (j ≠ k, j ≠ i): C [3,1] + C [1.4] = 10 + ∞ = ∞, do not change anything, we can notreach 3 to 4through 1 .
* j = 5 (j ≠ k, i ≠ j): C [3,1] + C [1.5] = 10 + ∞ = ∞, do not change anything, we can not reach 3 to 5through 1 .
* We i = 4 (i ≠ k):
* j = 2 (j ≠ k, i ≠ j): C [4.1] + C [1.2] = ∞ +3 = ∞, do not change anything, we can not get from4 to 2 by 1 .
* j = 3 (j ≠ k, i ≠ j): C [4.1] + C [1.3] = +10 ∞ = ∞, do not change anything, we can not getfrom 4 to 3 through 1 .
* j = 5 (j ≠ k, i ≠ j): C [4.1] + C [1.5] = ∞ + ∞ = ∞, do not change anything, we can not reach4 to 5 through 1 .
We take i = 5 (i ≠ k), occurs here as in the previous step, such as C [5.1] = ∞, then there will be no change, there can be no path from 5 through 1.
We k = 2:
We i = 1:
* j = 3: C [1,2] + C [2.3] = 3 +13 = 16> C [1.3] = 10, therefore we should not changeanything, the road is greater than the existing one.
* j = 4: C [1,2] + C [2.4] = 3 +5 = 8 <C [1.4] = ∞, therefore we do:
C [1,4] = 8 and D [1.4] = 2.
* j = 5: C [1,2] + C [2.5] = 3 + ∞ = ∞, do not change anything.
* We take i = 3:
* j = 1: C [3,2] + C [2.1] = 13 +3 = 16> C [3.1] = 10, do not change anything.
* j = 4: C [3,2] + C [2.4] = 13 +5 = 18> C [3.4] = 6, do notchange anything.
* j = 5: C [3,2] + C [2.5] = 13 + ∞ = ∞, do not change anything.
* We i = 4:
* j = 1: C [4.2] + C [2.1] = 5 +3 = 8 <C [4.1] = ∞, therefore we do:
C [4.1] = 8 and D [4.1] = 2.
* j = 3: C [4.2] + C [2.3] = 5 +13 = 18> C [4.3] = 6, do not change anything.
* j = 5: C [4.2] + C [2.5] = 5 + ∞ = ∞, do not change anything.
We take i = 5, and C...