Javascript Algorithm Series-Single Source Shortest Path-Dijkstra Algorithm

Dijkstra algorithm was developed by Dutch computer scientist Dijkstra in 1959
It is also called Dixtla algorithm. It is the shortest path algorithm from one vertex to the other vertices, which solves the shortest path problem in directed graph. The main feature of Dijkstra algorithm is to expand outward from the starting point until the end point is reached.

Ps: Dijkstra algorithm is a greedy algorithm

The above figure is an example.
We require the shortest path from vertex A to the other vertices.

First, we define the adjacency matrix of the above 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]]

Ps: Adjacency Matrix means that the relationship between vertices is determined by using a two-array to represent the relationship between vertices. Because the graph is a directed graph, the adjacency matrix of the above graph is as above

First release all the code of Dijkstra algorithm, then combine it and analyze it slowly.

let index = 'ABCDEF'
 let INF = Number.MAX_SAFE_INTEGER //1
 
 function dijkstra(src) {
 let dist = [],//2
 visited = [],//3
 length =  graph.length//4
 
 for (let i = 0;   i < length;  i++) {
 dist[i] = INF
 visited[i] = false
 }//5
 dist[src] = 0
 
 for (let i = 0;   i < length - 1;  i++) {
 let u = minDistance(dist, visited)
 visited[u] = true
 
 for (let v = 0;   v < length;  v++) {
 if (!  visited[v] && dist[u] !  == INF && graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
 dist[v] = dist[u] + graph[u][v]
 }
 }
 }
 
 return dist
 }
 
 function minDistance(dist, visited) {
 let min = INF,
 minIndex = -1
 
 for (let v = 0;   v < dist.length;  v++) {
 if (visited[v] === false && dist[v] <= min) {
 min = dist[v]
 minIndex = v
 }
 }
 
 return minIndex
 }

1. Initialization data
DefinitiondistArray to store the distance between the current A vertex and each other vertex
DefinitionvisitedThe array is used to store whether ABCDEF vertices have been accessed, so as to avoid repeated accesses and form a ring.
DefinitionlengthTo store the number of all vertices
DefinitionINFMax _ safe _ integer

for (let i = 0;   i < length;  i++) {
 dist[i] = INF
 visited[i] = false
 }//5
 dist[src] = 0

Initialize distvisited array, initialize all vertex distances to infinity, and define all vertices as accesses
Initialize the distance from vertex a to itself to 0

2. Process analysis

//Vertex Discovery Function
 for (let i = 0;   i < length - 1;  i++) {
 let u = minDistance(dist, visited)
 visited[u] = true
 
 for (let v = 0;   v < length;  v++) {
 if (!  visited[v] && dist[u] !  == INF && graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
 dist[v] = dist[u] + graph[u][v]
 }
 }
 }

//Find the shortest path function
 function minDistance(dist, visited) {
 let min = INF,
 minIndex = -1
 
 for (let v = 0;   v < dist.length;  v++) {
 if (visited[v] === false && dist[v] <= min) {
 min = dist[v]
 minIndex = v
 }
 }
 
 return minIndex
 }

The specific exploration logic is as follows

First cycle
Find the shortest vertex a
Traversing the distance from a to other vertices, if there is direct connection with other vertices, judging whether the distance from a to other vertices is the current distance from a to x+the distance from x to the new vertex < the distance from a to the new vertex
If less than, update that shortest distance to the vertex

The corresponding output value after the first cycle
Discovery a
Traversal found that A -> B is 2 A->C is 4 and is less than infinity, so the shortest distance from a to b, c is updated.

visited -> [ true, false, false, false, false, false ]
 dist -> [ 0, 2, 4, 9007199254740991, 9007199254740991, 9007199254740991 ]

Second cycle
Find the shortest side, except A, so explore point B.
Traversal found that B->C,B->E, B->D are 1, 2 and 4 respectively.
Then
The distance A-C is A-B+B-C = 3 less than the distance 4 directly to c, so the shortest distance A-C is updated.

visited -> [ true, true, false, false, false, false ]
 dist -> [ 0, 2, 3, 6, 4, 9007199254740991 ]

The output of the remaining three explorations is
dist -> [ 0, 2, 3, 6, 4, 9007199254740991 ]
visited -> [ true, true, true, false, true, false ]
dist -> [ 0, 2, 3, 6, 4, 6 ]
visited -> [ true, true, true, false, true, true ]
[ 0, 2, 3, 6, 4, 6 ]

This will get the shortest distance from A to all sides
[ 0, 2, 3, 6, 4, 6 ]

This is the process of js implementing Dijkstra algorithm. Some of them are short, and you can leave a message if you have any questions.