## 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**

Definition**dist**Array to store the distance between the current A vertex and each other vertex

Definition**visited**The array is used to store whether ABCDEF vertices have been accessed, so as to avoid repeated accesses and form a ring.

Definition**length**To store the number of all vertices

Definition**INF**Max _ 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.