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.