Introduction to the

Floyd-warshall algorithm (FLOyd-Warshall algorithm) is an algorithm that uses the idea of dynamic programming to find the shortest path between multiple source points in a given weighted graph, similar to Dijkstra algorithm. The algorithm is named after one of its founders, Robert Floyd, a 1978 Turing Award winner and professor of computer science at Stanford University.Copy the code

Simply speaking, it is an algorithm to solve the shortest path between any two points. It can correctly deal with the shortest path problem of directed graph or negative weight, and it is also used to calculate the transitive closure of directed graph. The time complexity of Floyd-Warshall algorithm is O(N3) and the space complexity is O(N2).

There are several well-known algorithms for solving shortest path problems:

  • 1. Dijkstra algorithm, the most classical single-source shortest path algorithm, has been mentioned in the previous article

  • 2. Bellman-ford algorithm, a single-source shortest path algorithm that allows negative edge weights

  • 3. Spfa, which is actually Bellman-Ford + queue optimization, is actually more closely related to BFS

  • 4. Floyd algorithm, a classical multi-source shortest path algorithm

Let’s start today with Floyd

Floyd algorithm in detail

describe

A) as shown in figure: there are four points [0,1,2,3], and the distance between the two points is the number on the edge. If there is no edge connected between the two points, it cannot be reached, which is infinite. B) To shorten the distance between any two points (e.g. from vertex A to b), only by introducing a third point (vertex k) and passing through this vertex K, i.e. a->k-> B, can the original distance from vertex A to vertex B be shortened. So what is the vertex k of the transit between 0 and n?

The algorithm process

To prepare

1) as shown in figure 0->1, the distance is 5,0 ->2 is unreachable, the distance is ∞, 0->3 is 7…… In turn, the graph can be transformed into an adjacency matrix (the main diagonal, i.e., self to itself, we specify a distance of 0 and an infinite unreachable distance). The graph matrix is used to store the shortest path weights between any pair of vertices.

Start looking for

1) List all paths (self to self does not count)

0 -> 1, 0 -> 2, 0 -> 3, 1 -> 0, 1 -> 2, 1 -> 3, 2 -> 0, 1 -> 1, 1 -> 3, 2 -> 0, 1 -> 1, 1 -> 3 {0, 1}, {0, 2}, {0, 3}, {1, 0}, {1, 2}, {1, 3}, {2, 0}, {2, 1}, {2, 3}, {3, 0}, {3, 1}, {3, 2}

2) Select point 0 as the intermediate point

{0,1}, {0,2}, {0,3}, {1,0}, {1,2}, {1,3}, {2,0}, {2,1}, {2,3}, {3,0}, {3,1}, {3,1}, {3,2} from the first element of the binary set above, the loop executes the following:

1. Use two variables I and j to refer to two elements in the binary group, such as {0, 1}, I refers to 0; 2. Judge (A[I][0]+A[0][j]) < A[I][j] (that is, judge I -> j, whether the distance from point I to point J is smaller than the distance from point 0), iffalse, then judge the next group of binary arrays. If A[I] [j] = A[I] [0] + A[0] [j]; if A[I] [j] = A[I] [0] + A[0] [j]; if A[I] [j] = A[I] [0] + A[0] [j];Copy the code

{0,1} after following this procedure,

The same goes for the next group {0,2}, {0,3}, {1,0}, {2,0}, {3,0}

{1,2} Follow this procedure, A[1,0] is infinite, A[0,2] is also infinite, and A[1,4] = 4, 1 to 2 definitely does not transfer from 0.

A[1][0] is infinite and so is the next group {1, 2}, {1, 3}.

{2, 1} according to the process execution, A [2] [0] = 3, A [0] [1] = 5, A [2] [1] = 3 so A [2] + [0], A [0] [1] > [2] A [1]………………… And so on, traversing the set of binary groups, no 0 points are suitable for transit

3) Select point 1 as the intermediate point

4) Select point 2 as the intermediate point

So on, the traversing binary group set {0, 1}, {0, 2}, {0, 3}, {1, 0}, {1, 2}, {1, 3}, {2, 0}, {2, 1}, {2, 3}, {3, 0}, {3, 1}, {3, 2}, when traversing {3, 0} [3] A [2] = 1, A [2] [0] = 3, A[3][0] = unreachable, then 2 is suitable to be the intermediate point between 3 and 0. Set the distance matrix A[3][0] = 1+3 =4, and the Path matrix Path[3][0] = 2 points, indicating that the transition from 3 to 0 is at 2 points and the distance is closest.

And so on, traversing the set of tuples

5) Select point 3 as the intermediate point and the final result

And so on, traversing the set of tuples until all vertices have made an intermediate point.

6) According to the final result, the shortest distance and path of any 2 points can be known

Like how do I get between 1:00 and 2:00? According to the Path Path matrix,Path[1][2] = 3, indicating the transfer from point 3, namely, 1-> 3 ->2

6) What if there is more than one transit point?

Sometimes the transfer is shorter through not one point, but two or more points, namely A ->k1-> K2b -> or A ->k1->k2… – > k – > I… – > b. Path[3][0] = 2, Path[2][0] = 2, Path[2][0] = -1, Path[1][0] = 3, Path[1][0] = 3, Path[3][0] = 2, Path[2][0] = -1, It means that vertex 2 has no path to vertex 0, that is, it can go directly from vertex 2 to vertex 0, that is, they have edge connections.

Finally, the shortest path is 1->3->2->0 and the distance is A[1][0] = 6. Obviously, this is a hierarchical, recursive process.

Algorithm implementation

The basic definition

Public static int MAX = integer.max_value; Public int[][] dist; // Path matrix public int[][] Path;Copy the code

The core algorithm

// Core algorithmfor(int k = 0 ; k < size ; k++){
           for(int i = 0; i < size; i++){for(int j = 0 ; j < size; J ++){// If ik is reachable and KJ is reachable and the distance between I and j is greater than the sum of the distances between I -> k and k->jif( dist[i][k] ! = MAX && dist[k][j] ! = MAX && dist[i][j] > (dist[i][k] + dist[k][j]) ){ path[i][j]= k; dist[i][j]= dist[i][k] + dist[k][j]; }}}}Copy the code

The results

Download the source code

Floyd algorithm Java implementation – Download

Floyd algorithm Java implementation

If you don’t know Floyd by the end of this article, please leave a comment.