DEV Community

Ashwani Rathee
Ashwani Rathee

Posted on

Floyd Warshall's Algorithm in Julia

Floyd Warshall Algorithm is used to solve all pairs shortest path problem. We have to find shortest path from all nodes to all other nodes.

Graph that we will be using in this article is a directed weighted graph and we use it in adjacency matrix form in our program:
Image description

So how does Floyd Warshall algorithm works?

Floyd warshall algorithm is a dynamic programing method and hence makes a decision on every step which reduces our time complexity.

  • First create a matrix with no nodes as intermediate node and let's call this array as being our A0. Each element in this represent distance from i to j where A0[i][j] is the element. Don't forget that arrays in Julia are 1-based, so A[1][1] is starting value in top left corner of the vector.
A^0 = [
       [ 0, 3, Inf, 7],
       [ 8, 0, 2, Inf],
       [ 5, Inf, 0, 1],
       [ 2, Inf, Inf, 0]
      ]; 
And its true that the initial matrix is same as our adjancency matrix.
Enter fullscreen mode Exit fullscreen mode
  • Now, subsequently create matrices A1, A2, A3, A4 which consider node 1, node 2, node 3, node 4 respectively as intermediate node and are built using previous matrice. For example, To create A1 we consider node 1 as our intermediate and update the distances if minimum distance value smaller than existing distance value found.
For like A1[2][3], new updated value will be
A1[2][3] = min(A0[2][3], A0[2][1] + A0[1][3])
Enter fullscreen mode Exit fullscreen mode

Let see the change from A0 to A1:

A0:
4-element Vector{Vector{Float64}}:
 [0.0, 3.0, Inf, 7.0]
 [8.0, 0.0, 2.0, Inf]
 [5.0, Inf, 0.0, 1.0]
 [2.0, Inf, Inf, 0.0]

A1:
4-element Vector{Vector{Float64}}:
 [0.0, 3.0, Inf, 7.0]
 [8.0, 0.0, 2.0, 15.0]
 [5.0, 8.0, 0.0, 1.0]
 [2.0, 5.0, Inf, 0.0]


A1[1][1] = min(A0[1][1], A0[1][1] + A0[1][1]) = min(0,0) = 0
A1[1][2] = min(A0[1][2], A0[1][1] + A0[1][2]) = min(3,3) = 3
A1[1][3] = min(A0[1][3], A0[1][1] + A0[1][3]) = min(Inf,Inf) = Inf
A1[1][4] = min(A0[1][4], A0[1][1] + A0[1][4]) = min(7,7) = 7
A1[2][1] = min(A0[2][1], A0[2][1] + A0[1][1]) = min(8,8) = 8
A1[2][2] = min(A0[2][2], A0[2][1] + A0[1][2]) = min(0,0) = 0
A1[2][3] = min(A0[2][3], A0[2][1] + A0[1][3]) = min(2,2) = 2
A1[2][4] = min(A0[2][4], A0[2][1] + A0[1][4]) = min(Inf,8+7) = 15
A1[3][1] = min(A0[3][1], A0[3][1] + A0[1][1]) = min(5,5) =5
:
:
:
:
Enter fullscreen mode Exit fullscreen mode
  • Distances in the matrice Alast in which last is number of vertices and will be the one with the solution of all pairs shortest path problem and has minimum distances of a node to all other nodes.

Pseudo code:

let dist be a |V| × |V| array of minimum distances initialized to  (infinity)
for each edge (u, v) do
    dist[u][v]  w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v]  0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j]  dist[i][k] + dist[k][j]
            end if
Enter fullscreen mode Exit fullscreen mode

Code:

# All pairs shortest path

function FloydWarshall(dist)
    println("Initial Adjacency matrix: ")
    display(dist)
    println("\n")
    for k in 1:V
        # pick all vertices as source one by one
        println("Matrix A^k with k as ", k)
        println("Current dist:")
        display(dist)
        println("\n")
        for i in 1:V
            # Pick all vertices as destination for the
            # above picked source
            for j in 1:V

                # If vertex k is on the shortest path from
                # i to j, then update the value of dist[i][j]
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            end
        end
    end
    println("\nMatrix after applying Floyd Warshall: ")
    display(dist)
    println("\n")
end

graph = [[ 0, 3, Inf, 7],
         [ 8, 0, 2, Inf],
         [ 5, Inf, 0, 1],
         [ 2, Inf, Inf, 0]
        ];  

V = size(graph)[1] # Number of vertices in the graph

FloydWarshall(graph)
Enter fullscreen mode Exit fullscreen mode

Output:

(base) ashwani@user:~/practice/DAY2$ julia floyd.jl 
Initial Adjacency matrix: 
4-element Vector{Vector{Float64}}:
 [0.0, 3.0, Inf, 7.0]
 [8.0, 0.0, 2.0, Inf]
 [5.0, Inf, 0.0, 1.0]
 [2.0, Inf, Inf, 0.0]

Matrix A^k with k as 0
Current dist:
4-element Vector{Vector{Float64}}:
 [0.0, 3.0, Inf, 7.0]
 [8.0, 0.0, 2.0, Inf]
 [5.0, Inf, 0.0, 1.0]
 [2.0, Inf, Inf, 0.0]

Matrix A^k with k as 1
Current dist:
4-element Vector{Vector{Float64}}:
 [0.0, 3.0, Inf, 7.0]
 [8.0, 0.0, 2.0, 15.0]
 [5.0, 8.0, 0.0, 1.0]
 [2.0, 5.0, Inf, 0.0]

Matrix A^k with k as 2
Current dist:
4-element Vector{Vector{Float64}}:
 [0.0, 3.0, 5.0, 7.0]
 [8.0, 0.0, 2.0, 15.0]
 [5.0, 8.0, 0.0, 1.0]
 [2.0, 5.0, 7.0, 0.0]

Matrix A^k with k as 3
Current dist:
4-element Vector{Vector{Float64}}:
 [0.0, 3.0, 5.0, 6.0]
 [7.0, 0.0, 2.0, 3.0]
 [5.0, 8.0, 0.0, 1.0]
 [2.0, 5.0, 7.0, 0.0]

Matrix A^k with k as 4
Current dist:
4-element Vector{Vector{Float64}}:
 [0.0, 3.0, 5.0, 6.0]
 [5.0, 0.0, 2.0, 3.0]
 [3.0, 6.0, 0.0, 1.0]
 [2.0, 5.0, 7.0, 0.0]


Matrix after applying Floyd Warshall: 
4-element Vector{Vector{Float64}}:
 [0.0, 3.0, 5.0, 6.0]
 [5.0, 0.0, 2.0, 3.0]
 [3.0, 6.0, 0.0, 1.0]
 [2.0, 5.0, 7.0, 0.0]

Enter fullscreen mode Exit fullscreen mode

Floyd Warshall Algorithm is usually faster than Dijsktra Algorithm which can also be used to solve this problem by take each node as source one by node and finding shortest paths to all other nodes.

Floyd Warshall Algorithm Complexity

Time Complexity

There are three loops. Each loop has constant complexities. So, the time complexity of the Floyd-Warshall algorithm is O(n3).

Space Complexity

The space complexity of the Floyd-Warshall algorithm is O(n2).

Floyd Warshall Algorithm Applications

  • To find the shortest path is a directed graph
  • To find the transitive closure of directed graphs
  • To find the Inversion of real matrices
  • For testing whether an undirected graph is bipartite

References:

Discussion (0)