Algorithm | figure – Freud algorithm of the shortest path algorithm

This is the fifth day of my participation in Gwen Challenge

What is floyd-Warshall algorithm

If I have a weighted graph, how can I find the shortest distance between all the vertices in the graph?

Using the Dijkstra algorithm introduced earlier, using it once for each vertex in the graph, you can also find the shortest distance between all vertices.

However, because the code logic of Dijkstra algorithm is more complex, floyd-Warshall algorithm can be used to do the same thing, the code logic is simpler, and the total time complexity of the two algorithms to find the multi-source shortest path is also the same, O (n^3).

The Freudian algorithm, known in English as Floyd-Warshall (not Freud), is designed to find the shortest path between multiple sources in a weighted graph. The idea of the algorithm is to introduce new vertices as relay vertices according to all the vertices in the graph instance, and deduce the shortest distance between all vertices step by step through one relay vertices.

Detailed steps of Floyd-Warshall algorithm

The following detailed steps of the algorithm are from the article “Manga: Multi-source Shortest Paths for Graphs” by the public account “Programmer Xiao Grey”.

Suppose I have an adjacency matrix with a weighted graph.

Suppose starting with A as the relay vertices of the adjacency matrix in the order of the vertices of the graph instance:

The distance between vertex B and C is infinite, which is shortened to the distance between vertex A and vertex B + the distance between vertex B and vertex C =5+2=7.

Suppose, now introduce new relay vertices, A and B as the relay vertices of adjacency matrix:

The distance between vertex A and vertex D is infinite, and vertex B is used as the relay vertex. At this time, the distance between vertex A and vertex B + the distance between vertex B and vertex D =5+1=6.

The distance between vertex A and E is infinite, and vertex B is used as the relay vertex. In this case, the distance between vertex A and vertex B + the distance between vertex B and vertex E is =5+6=11.

Suppose again, and then introduce new relay vertices, taking A, B and C as the relay vertices of adjacency matrix:

The distance between vertex A and vertex F is infinite, and vertex C is used as the relay vertex. At this time, the distance between vertex A and vertex C + the distance between vertex C and vertex F is =2+8=10.

(Note: In order to simplify understanding, the above diagram only considers the distance between vertex A and A certain vertex, and does not show the distance between any other vertex and A certain vertex.)

Repeat the previous steps to introduce new relay vertices and refresh the temporary distances in the adjacency matrix

Finally, the distance table of the example in the following figure is obtained:

At this point, the distance table records the shortest distance between one vertex in the graph and any other vertex.

Code implementation

/** * Shortest path algorithm - Freudian algorithm *@param {*} Graph needs to compute the shortest path graph instance *@returns {*} Shortest path of graph instance (weighted graph) */
 export const floydWarshall = graph= > {
  const dist = []; // Create a distance table to store the distance from the starting point to each vertex (weight)
   const { length } = graph; // The number of vertices in the graph instance
   // Initializes the distance table for each vertex of the graph instance and its adjacent matrix (weights)
  for (let i = 0; i < length; i++) { // Iterate over all vertices of the graph instance
    dist[i] = []; // Initialize the vertex corresponding to the graph instance as an empty matrix
    for (let j = 0; j < length; j++) { // Loop over the relationship between the current vertex and other vertices (whether the current vertex and other vertices have edges)
      if (i === j) {
        // If it is the distance between the vertex and itself, the distance is 0
        dist[i][j] = 0;
      } else if (!isFinite(graph[i][j])) {
        // If there are no edges between the two vertices, it is Infinity.
        dist[i][j] = Infinity;
      } else {
        // If there is an edge between these two vertices, record their distance (weight) in the distance table.dist[i][j] = graph[i][j]; }}}// Loop to update the matrix
  for (let k = 0; k < length; k++) { // Use vertices 0 to k(the length of the graph instance) as relay vertices
    for (let i = 0; i < length; i++) { // Loop over all vertices of the graph instance
      for (let j = 0; j < length; j++) { // Loop over the relationship between the current vertex and other vertices (whether the current vertex and other vertices have edges)
        The shortest path from I to j goes through k
        if (dist[i][k] + dist[k][j] < dist[i][j]) { // Compute the shortest path between I and j through vertex k
          // const numberToChat = ['A', 'B', 'C', 'D', 'E', 'F', 'G'];
          / / the console. The log (' k - 'numberToChat [k],' I - 'numberToChat [I],' j - 'numberToChat [j]);
          / / the console. The log (' dist [j] - [I] ', dist [j], [I] 'dist [k] - [I]', dist [k], [I] 'dist [k] [j] --', dist [k] [j]);
          // console.log(`${numberToChat[i]}${numberToChat[j]}=${numberToChat[i]}${numberToChat[k]}+${numberToChat[k]}${numberToChat[ j]}`);
          dist[i][j] = dist[i][k] + dist[k][j]; // If a new value of the shortest path is found, we use it and store it}}}}return dist; // After processing all vertices, return the result of the shortest path from all vertices to other vertices in the graph.
};
Copy the code

The code examples

Suppose we have an example of a graph like this:

const graphdemo = [
  [0.5.2.Infinity.Infinity.Infinity.Infinity],
  [5.0.Infinity.1.6.Infinity.Infinity],
  [2.Infinity.0.6.Infinity.8.Infinity],
  [Infinity.1.6.0.1.2.Infinity],
  [Infinity.6.Infinity.1.0.Infinity.7],
  [Infinity.Infinity.8.2.Infinity.0.3],
  [Infinity.Infinity.Infinity.Infinity.7.3.0]]Copy the code

Add numberToChar, an auxiliary constant that converts array subscripts to corresponding vertices

const numberToChar = ['A'.'B'.'C'.'D'.'E'.'F'.'G'];
Copy the code

Uncomment the above code implementation and pass the graph instance (Graphdemo) into the floydWarshall algorithm to get the following process result:

floydWarshall(graphdemo);
/** vm564:28 k -- A I -- B j -- C VM564:29 Dist [I][j] -- Infinity Dist [I][k] -- 5 dist[k] -- 2 vm564:30 BC=BA+AC vm564:28 K -- A I -- C j -- B VM564:29 Dist [I][J] -- Infinity Dist [I][k] -- 2 DIST [j] -- 5 vm564:30 CB=CA+AB VM564:28 k -- B I -- A J -- D vm564:29 DIST [I][J] -- Infinity Dist [I][k] -- 5 Dist [k] -- 1 VM564:30 AD=AB+BD VM564:28 k -- B I -- A j -- E VM564:29 Dist [I] [j] - Infinity dist [I] [k] - dist [k] [j] - 6 VM564:30 AE = AB + BE VM564:28 k - B - C j - I E VM564:29 dist [I] - [j] Infinity dist [I] [k] - 7 dist [k] [j] - 6 VM564:30 CE = CB + BE VM564:28 k - B - D j - I A VM564:29 dist [I] [j] - Infinity Dist [I][k] -- 1 DIST [k][J] -- vm564:30 DA=DB+BA VM564:28 K -- B I -- E j -- A VM564:29 DIST [I] -- Infinity Dist [I][k] -- 6 Dist [J] -- VM564:30 EA=EB+BA VM564:28 K -- I -- E j -- C VM564:29 DIST [I] -- Infinity Dist [I][K] -- 6 dist[K][J] -- 7 VM564:30 EC=EB+BC VM564:28 K -- C I -- A j -- F VM564:29 Dist [I][J] -- Infinity Dist [I][k] -- 2 dist[k] -- 8 VM564:30 AF=AC+CF vm564:28 K -- C I -- B j -- F VM564:29 Dist [I][J] -- Infinity Dist [I][k] -- 7 Dist [k][J] -- 8 vm564:30 BF=BC+CF VM564:28 k -- C I -- E j -- F VM564:29 Dist [I][J] -- Infinity Dist [I][k] -- 13 Dist [k] -- 8 VM564:30 EF=EC+CF VM564:28 K -- C I -- F j -- A VM564:29 Dist [I][J] -- Infinity Dist [I][k] -- 8 Dist [k] -- 2 VM564:30 FA=FC+CA VM564:28 k -- C I -- F j -- B Vm564:29 Dist [I][J] -- Infinity Dist [I][k] -- 8 Dist [k] -- 7 vm564:30 FB=FC+CB vm564:28 k -- C I -- F j -- E VM564:29 Dist [I] [j] - Infinity dist [I] [k] - 8 dist [k] [j] -- 13 VM564:30 FE = FC + CE VM564:28 k - D - A j, E I VM564:29 dist [I] - [j] 11 Dist [I][K] -- 6 Dist [K][J] -- 1 VM564:30 AE=AD+ vm564:28 K -- D I -- A j -- F VM564:29 DIST [I][J] -- 10 DIST [I][K] -- 6 Dist [k] [j] - 2 VM564:30 AF = AD + DF VM564:28 k - D - B j - I E VM564:29 dist [I] [j] - 6 dist [I] [k] - 1 dist [k] [j] - 1 VM564:30 BE= VM564 + VM564:28 k -- D I -- B j -- F VM564:29 Dist [I][J] -- 15 dist[I][k] -- 1 dist[k] -- 2 VM564:30 BF=BD+DF VM564:28 k -- D I -- C j -- E VM564:29 Dist [I] -- 13 Dist [I][k] -- 6 dist[k] -- 1 CE=CD+DE VM564:28 k -- D I -- E VM564:29 DIST [I] -- 13 dist[I][k] -- 6 dist[k] -- 1 CE=CD+DE VM564:28 k -- D I -- E J -- A VM564:29 DIST [I] -- 11 Dist [I][K] -- 1 DIST [k] -- 6 VM564:30 EA=ED+DA VM564:28 k -- D I -- E j -- B VM564:29 Dist [I] [j] - 6 dist [I] [k] - 1 dist [k] [j] - 1 VM564: EB = ED + 30 DB VM564:28 k - I - E j D - C VM564:29 dist [j] - [I] Dist [I] [k] - 1 dist [k] [j] - 6 VM564: EC = ED 30 + DC VM564:28 k - I - E j D - F VM564:29 dist [I] [j] - 21 dist [k] - [I] 1 Dist [k] [j] - 2 VM564: EF = ED 30 + DF VM564:28 k - D I - F j - A VM564:29 dist [I] [j] - dist [I] [k] - 2 dist [k] [j] - 6 VM564:30 FA=FD+DA VM564:28 k -- D I -- F j -- B VM564:29 Dist [I][J] -- 15 dist[I][k] -- 2 dist[k][j] -- 1 VM564:30 FB=FD+DB VM564:28 k -- D I -- F j -- E VM564:29 Dist [I] -- 21 Dist [I][k] -- 2 dist[k] -- 1 VM564:30 FE=FD+DE VM564:28 k -- E I -- A J -- G vm564:29 Dist [I][J] -- Infinity Dist [I][k] -- 7 DIST [k] -- 7 VM564:30 AG=AE+EG VM564:28 k -- E -- B j -- G Vm564:29 dist[I][J] -- Infinity Dist [I][k] -- 2 dist[k] -- 7 vm564:30 BG=BE+EG vm564:28 k -- E I -- C j -- G VM564:29 Dist [I] [j] - Infinity dist [I] [k] - dist [k] [j] VM564-7:30 CG = CE + EG VM564:28 k - E - D j - I G VM564:29 dist [I] - [j] Infinity dist [I] [k] - 1 dist [k] [j] VM564-7:30 DG = DE + EG VM564:28 k - E I - G j - A VM564:29 dist [I] [j] - Infinity Dist [I][k] -- 7 DIST [K] -- 7 VM564:30 GA=GE+EA VM564:28 K -- E I -- G j -- B VM564:29 Dist [I] -- Infinity Dist [I][k] -- 7 Dist [J] -- VM564:30 GB=GE+EB VM564:28 K -- G j -- C VM564:29 DIST [I][J] -- Infinity Dist [I][k] -- 7 Dist [K][J] -- VM564:30 GB=GE+EB VM564:28 K -- E -- G J -- C VM564:29 Dist [I] -- Infinity Dist [I][k] -- 7 Dist [k] -- 7 VM564:30 GC=GE+EC VM564:28 K -- E I -- G j -- D VM564:29 Dist [I][J] -- Infinity Dist [I][k] -- 7 Dist [k] -- 1 VM564:30 GC=GE+EC VM564:28 K -- E I -- G J -- D VM564:29 Dist [I] -- Infinity Dist [k] -- 7 Dist [k] -- 1 VM564:30 GD=GE+ED VM564:28 k -- F I -- A j -- G VM564:29 Dist [I][J] -- 14 Dist [I][k] -- 8 Dist [k][J] -- 3 VM564:30 AG=AF+FG VM564:28 VM564:28 k -- F I -- B j -- G VM564:29 DIST [I][J] -- 9 dist[I][k] -- 3 dist[k] -- 3 VM564:28 k -- F I -- C j -- G VM564:29 DIST [I] -- dist[I] -- dist[k] -- dist[k] -- dist[J] -- 3 VM564:30 CG=CF+FG VM564:28 k -- F -- D j -- G VM564:29 Dist [I] [j] - 8 dist [I] [k] - 2 dist [k] [j] - three VM564:30 DG = DF + FG VM564:28 k - I - E j F - G VM564:29 dist [I] [j] - 7 Dist [I] [k] - three dist [k] [j] - three VM564:30 EG = EF + FG VM564:28 k, F, G j, I A VM564:29 dist [I] [j] - dist [I] [k] - 3 Dist [k] [j] - 8 VM564:30 GA = GF + FA VM564:28 k, F, G j, I B VM564:29 dist [I] [j] - dist [I] [k] - three dist [k] [j] - 3 VM564:30 GB=GF+FB VM564:28 k -- F I -- G j -- C VM564:29 Dist [I] -- 14 Dist [I][k] -- 3 Dist [k][J] -- 8 VM564:30 GC=GF+FC VM564:28 k -- F I -- G j -- D VM564:29 Dist [I][J] -- 8 Dist [I][k] -- 3 dist[k] -- 5 GD=GF+FD VM564:28 k -- F I -- G J - E VM564:29 dist [I] [j] - dist [I] [k] - three dist [k] [j] - three VM564:30 GE = GF + FE * * /

Dist = dist; dist = dist; 5,0,7,1,2,3,6,5,2,6,7,8,11 [[0], [],,7,0,6,7,8,11 [2], [6,1,6,0,1,2,5],,2,7,1,0,3,6 [7], [8,3,8,2,3,0,3]. * * /,6,11,5,6,3,0 [11]]
Copy the code