This is the fourth day of my participation in Gwen Challenge

What is Dijkstra

Dijkstra’s full name is Edsger Wybe Dijkstra, Dijkstra algorithm is invented by Dijkstra himself to find graph shortest path algorithm, Chinese name is Dijkstra algorithm.

Dijkstra is a greedy algorithm that computes the shortest path from a single source to all other sources.

Dijkstra algorithm uses breadth-first search to solve the single source shortest path problem of weighted directed graphs. A shortest path tree is generated by using one vertex as the source node and finding shortest paths from that vertex to all other nodes in the graph.

Dijkstra is still used in many places, from automatic pathfinding in turn-based games like Water Margin to finding the shortest route to a delicious restaurant on Baidu map.

Dijkstra algorithm detailed steps

The following detailed steps of the algorithm are from the article “Cartoon: The” Shortest Path “Problem of graphs” by the public account “Programmer Xiao Grey”.

Let’s say we have A directed graph like this, and let’s figure out what is the shortest path distance from vertex A to other vertices.

At this point, we need to build a distance table and access record table.

The key value of the distance table corresponds to the vertex of the instance graph, and the corresponding value is the known distance from the starting point A to the corresponding vertex. By default, the distance from starting point A to any other vertex is infinite.

The access record table records the access to each vertex of the graph instance. The default value is false(that is, not accessed).

From vertex A, we know that vertex A has adjacent vertices B and C, and the distance from vertex A to vertex B is 5, and the distance from vertex A to vertex C is 2. Because both vertex B and vertex C in the distance table are infinite by default, the known distance (A to B is 5, A to C is 2) can be updated to the distance table, and vertex A is recorded as visited in the access record table.

At this point, in the distance table, the vertex with the shortest path is vertex C, so we start to explore from vertex C, and we know that the adjacent vertices of vertex C have D and F(vertex A is visited in the access record table, so it does not need to be considered).

The distance from C to D is 6, so the distance from A to D is 2+6=8.

The distance between vertex C and F is 8, so the distance between vertex A and F is 2+8=10.

Vertex D and vertex F are both infinite by default in the distance table. Then, the distance obtained above can be updated to the distance table, and vertex C is recorded as visited in the access record table.

At this point, in the distance table, the vertex with the shortest path is vertex B(vertex A and C are visited in the access record table and do not need to be considered), then we start to explore from vertex B, and we know that the adjacent vertices of vertex B are D and E(vertex A is visited in the access record table and does not need to be considered).

The distance from B to D is 1, so the distance from A to D is 5+1=6.

The distance between vertex B and E is 6, so the distance between vertex A and E is 2+8=11.

The distance from vertex A to vertex D, 6, is less than 8 in the current distance table. At this point, we need to overwrite 8 of vertex D in the original distance table and refresh it to A new value of 6.

The distance from vertex A to vertex E is 11, and vertex F in the distance table is infinite by default. Infinity can be refreshed to A new distance value of 11.

Meanwhile, vertex B is recorded as visited in the access record table.

As in the previous part, the remaining steps are to judge the shortest path of graph instance vertices one by one through the distance table, refresh iteratively, brush out the old path length with the new path length, and finally get the shortest distance from the starting point to any other vertex:

At this point, the distance from the table, the shortest path vertex is D (vertex of A and B and vertex C in access form for the visit, do not need to consider), then we began to explore, from the vertex D known vertex D adjacent vertices have E and F (vertex B and C in the access form for the visit, do not need to consider).

The distance between vertex D and E is 1, so the distance between vertex A and E is 6+1=7.

The distance from vertex D to vertex F is 2, so the distance from vertex A to vertex F is 6+2=8.

The distance from vertex A to vertex E, 7, is less than 11 in the current distance table, and the distance from vertex A to vertex F, 8, is less than 10 in the current distance table.

We can then cover vertex E in the distance table with a distance of 7 and vertex F with a distance of 8.

Meanwhile, vertex D is recorded as visited in the access record table.

At this point, the distance from the table, the shortest path vertex is E (vertex of A and B, vertex C and D in the access form for the visit, do not need to consider), then we start from vertex E exploration, known vertex E adjacent vertices have G (vertex B and D in the access form for the visit, do not need to consider).

The distance from E to G is 7, so the distance from A to G is 7+7=14.

Vertex G is still infinite by default in the distance table, so we can overwrite vertex G in the distance table to 14.

Meanwhile, vertex E is recorded as visited in the access record table.

At this point, the distance from the table, the shortest path vertex is F (vertex of A and B, vertex C, D, and vertex E in access form for the visit, do not need to consider), then we start from vertex F exploration, known vertex E adjacent vertices have G (vertex C and D in the access form for the visit, do not need to consider).

The distance from vertex F to vertex G is 3, so the distance from vertex A to vertex G is 8+3=11(paths A-b-D-F-g).

We can now cover the distance from vertex G in the distance table with 11.

At the same time, vertex G is recorded as visited in the access record table. At this position, all vertices of the graph instance are traversed.

At this point, the distance table is returned, and the value stored in the distance table is the shortest distance between vertex A and other vertices.

Code implementation

// INF constant holds the infinity of type Number
const INF = Number.MAX_SAFE_INTEGER;
/** * An internal function that computes the smallest path vertex of all vertices in the graph instance *@param {*} Distance table of dist diagram instance *@param {*} The visit Record table of visited Graph instances *@returns {*} Returns the vertex subscript * */ of the shortest path in the current graph instance
const minDistance = (dist, visited) = > {
  // // Find the current shortest path vertex as a hop point
  let min = INF; // Store the current shortest path distance (default is infinite)
  let minIndex = -1; // Store the subscript of the current shortest path vertex
  for (let v = 0; v < dist.length; v++) { // Iterate over the list of vertices in the graph instance
    if (visited[v] === false && dist[v] <= min) { // If the vertex is not visited, and the minimum distance of the vertex is less than or equal to the current minimum distance
      min = dist[v]; // Update the shortest path distance
      minIndex = v; // Update the subscript of the shortest path vertices}}// Find the vertex subscript of the shortest path of all vertices in the graph instance and return it
  return minIndex; // Return the shortest path vertex of all vertices in the graph instance (subscript)
};
/** * Shortest path algorithm - Dijkstra algorithm *@param {*} Graph needs to compute the shortest path graph instance *@param {*} SRC Specifies the starting vertex *@returns {*} Graph instance shortest path */
export const dijkstra = (graph, src) = > {
  const dist = [];  // Create a distance table to store the temporary distance from the starting point to each vertex
  const visited = []; // Create an access record table for vertices traversed
  const { length } = graph;  // The number of vertices in the graph instance
  
  // Initialize the shortest path table, the path cost to each vertex is infinite by default, each vertex access record is not accessed (false)
  for (let i = 0; i < length; i++) {
    dist[i] = INF;
    visited[i] = false;
  }
  dist[src] = 0; // Get the starting point, refresh the distance table, graph instance passed the starting vertex distance is 0
  // The main loop repeats the operation of traversing the shortest vertex and refreshing the distance table
  for (let i = 0; i < length - 1; i++) {  
    const u = minDistance(dist, visited); // Each vertex of the graph instance traverses the shortest vertex, passing in the distance table and visited of the graph instance.
    visited[u] = true; // The access status of the current node item is changed to true
    for (let v = 0; v < length; v++) { // // traverses vertices (that is, traverses the adjacency matrix of the current vertex), refreshing the distance table
      // If a shorter path is found, the shortest path value is updated
      if(! visited[v] && graph[u][v] ! = =0&& dist[u] ! == INF && dist[u] + graph[u][v] < dist[v]) { dist[v] = dist[u] + graph[u][v]; }}}return dist; // After processing all vertices, return the result of the shortest path from the starting vertex (SRC) to the other vertices in the graph.
};
Copy the code

Code the use case

If I have an example of an adjacency matrix graph

let graph = [
 [0.2.4.0.0.0],
 [0.0.1.4.2.0],
 [0.0.0.0.3.0],
 [0.0.0.0.0.2],
 [0.0.0.3.0.2],
 [0.0.0.0.0.0]].Copy the code

The results obtained by Using Dijkstra are as follows:

/** 0 0 1 2 2 3 3 4 4 5 6 **/
Copy the code