## introduce

from A Point to B What is the shortest path of a point ？ Two algorithms for finding the shortest path ：Dijkstra Algorithm and Floyd Algorithm .

Net diagram ： With weight chart .

The shortest path of non net graph ： The path with the least number of edges between two vertices .（ Non net graph can also be understood as the weight of each side is 1 Network diagram of .）

The shortest path of the net graph ： The path with the least sum of weights on the edge between two vertices . The first vertex on the path is the source point , The last vertex is the end .

problem ： The following figure V_{0} Point to the other vertices V_{k} What is the shortest path for ？

## demonstration

Set up a picture G Each vertex in is V_{0} The path to that point . And expressed in the following form ：

Path[x].Length：V_{0} To the end of the path V[x] Shortest path . Such as Path[2].Length by V_{0}->V_{2} Shortest path .

Path[x].Predecessor：V_{0} The number of the last vertex to the end of the path （ Subscript ）. Such as Path[2].Predecessor by 0, Express V_{0}->V_{2} Shortest path , The vertices V_{2} The previous vertex of is V_{1}, That is, through V_{1} Then arrive at V_{2}.

Path[x].IsVisited： The vertices Vx Have you ever used it as a foothold to find the shortest path . among V_{x} yes V_{0} To the end of the path .

G[i][j]： Graph is represented by adjacency matrix G.G[i][j] For the top V_{i} To the top V_{j} A weight .

0. initialization ：

Of all paths Predecessor Set to -1,Length Set to 0,IsVisited Set to false.

From the source Path[0].Predecessor = 0, because V_{0}->V_{0} One vertex on the path is V_{0},V_{0}->V_{0} The distance to 0, so Path[0].Length = 0.

step 0：

1. With V_{0} For a foothold , therefore Path[0].IsVisited = true.

2.V_{0} And V_{0}、V_{1} And V_{2} Connected to a .

Path[0].IsVisited by true, So skip this path .

Path[0].Length + G[0][1] = 0 + 1 < Path[2].Length = ∞ so Path[1].Length = 1,Path[1].Predecessor = 0;

Path[0].Length + G[0][2] = 0 + 5 < Path[2].Length = ∞ so Path[2].Length = 5,Path[2].Predecessor = 0;

3. Now look up the picture G All in 9 A path （ Every vertex forms a shortest path ） Which path has not been used as a foothold and the shortest path has the end point as a new foothold .

Path[0].IsVisited by true, So skip . And the rest are false.

Path[1].Length by 1,Path[2].Length by 5, rest Path.Length by ∞. So choose Path[1] The end V1 As a new foothold . Make V_{0} = 1, From the top V_{1} Start the next round of search .

step 1：

1. With V_{1} For a foothold , therefore Path[1].IsVisited = true.

2.V_{1} And V_{0}、V_{1}、V_{2}、V_{3} And V_{4} Connected to a .

Path[0].IsVisited by true,Path[1].IsVisited by true, So skip these paths .

Path[1].Length + G[1][2] = 1 + 3 < Path[2].Length = 5 so Path[2].Length = 4,Path[2].Predecessor = 1;

Path[1].Length + G[1][3] = 1 + 7 < Path[3].Length = ∞ so Path[3].Length = 8,Path[3].Predecessor = 1;

Path[1].Length + G[1][4] = 1 + 5 < Path[4].Length = ∞ so Path[4].Length = 6,Path[4].Predecessor = 1;

3. Now look up the picture G All in 9 A path （ Every vertex forms a shortest path ） Which path has not been used as a foothold and the shortest path has the end point as a new foothold .

Path[0、1].IsVisited by true, So skip . And the rest are false.

Path[2].Length by 4,Path[3].Length by 8,Path[4].Length by 6, rest Path.Length by ∞. So choose Path[2] The end V2 As a new foothold . Make V_{0} = 2, From the top V2 Start the next round of search .

step 2：

1. With V_{2} For a foothold , therefore Path[2].IsVisited = true.

2.V_{2} And V_{0}、V_{1}、V_{2}、V_{4}、 And V_{5} Connected to a .

Path[0、1、2].IsVisited by true, So skip these paths .

Path[2].Length + G[2][4] = 4 + 1 < Path[4].Length = 6 so Path[4].Length = 5,Path[4].Predecessor = 2;

Path[2].Length + G[2][5] = 4 + 7 < Path[5].Length = ∞ so Path[5].Length = 11,Path[5].Predecessor = 2;

3. Now look up the picture G All in 9 A path （ Every vertex forms a shortest path ） Which path has not been used as a foothold and the shortest path has the end point as a new foothold .

Path[0、1、2].IsVisited by true, So skip . And the rest are false.

Path[3].Length by 8,Path[4].Length by 5,Path[5].Length by 11, rest Path.Length by ∞. So choose Path[4] The end V_{4} As a new foothold . Make V_{0} = 4, From the top V4 Start the next round of search .

step 3：

1. With V_{4} For a foothold , therefore Path[4].IsVisited = true.

2.V_{4} And V_{1}、V_{2}、V_{3}、V_{4}、V_{5}、V_{6} And V_{7} Connected to a .

Path[0、1、2、4].IsVisited by true, So skip these paths .

Path[4].Length + G[4][3] = 5 + 2 < Path[3].Length = 8 so Path[3].Length = 7,Path[3].Predecessor = 4;

Path[4].Length + G[4][5] = 5 + 3 < Path[5].Length = 11 so Path[5].Length = 8,Path[5].Predecessor = 4;

Path[4].Length + G[4][6] = 5 + 6 < Path[6].Length = ∞ so Path[6].Length = 11,Path[6].Predecessor = 4;

Path[4].Length + G[4][7] = 5 + 9 < Path[7].Length = ∞ so Path[7].Length = 14,Path[6].Predecessor = 4;

3. Now look up the picture G All in 9 A path （ Every vertex forms a shortest path ） Which path has not been used as a foothold and the shortest path has the end point as a new foothold .

Path[0、1、2、4].IsVisited by true, So skip . And the rest are false.

Path[3].Length by 7,Path[5].Length by 8,Path[6].Length by 11,Path[7].Length by 14, rest Path.Length by ∞. So choose Path[3] The end V_{3} As a new foothold . Make V_{0}=3, From the top V3 Start the next round of search .

step 4：

1. With V_{3} For a foothold , therefore Path[3].IsVisited = true.

2.V_{3} And V_{1}、V_{4} And V_{6} Connected to a .

Path[0、1、2、3、4].IsVisited by true, So skip these paths .

Path[3].Length + G[3][6] = 7 + 3 < Path[6].Length = 11 so Path[6].Length = 10,Path[6].Predecessor = 3;

3. Now look up the picture G All in 9 A path （ Every vertex forms a shortest path ） Which path has not been used as a foothold and the shortest path has the end point as a new foothold .

Path[0、1、2、3、4].IsVisited by true, So skip . And the rest are false.

Path[5].Length by 8,Path[6].Length by 10,Path[7].Length by 14, rest Path.Length by ∞. So choose Path[5] The end V5 As a new foothold . Make V_{0} = 5, From the top V5 Start the next round of search .

step 5：

1. With V_{5} For a foothold , therefore Path[5].IsVisited = true.

2.V_{5} And V_{2}、V_{4}、V_{5} And V_{7} Connected to a .

Path[0、1、2、3、4、5].IsVisited by true, So skip these paths .

Path[5].Length + G[5][7] = 8 + 5 < Path[7].Length = 14 so Path[7].Length = 13,Path[7].Predecessor = 5;

3. Now look up the picture G All in 9 A path （ Every vertex forms a shortest path ） Which path has not been used as a foothold and the shortest path has the end point as a new foothold .

Path[0、1、2、3、4、5].IsVisited by true, So skip . And the rest are false.

Path[6].Length by 10,Path[7].Length by 13, rest Path.Length by ∞. So choose Path[6] The end V6 As a new foothold . Make V_{0} = 6, From the top V_{6} Start the next round of search .

step 6：

1. With V_{6} For a foothold , therefore Path[6].IsVisited = true.

2.V_{6} And V_{3}、V_{4}、V_{7} And V_{8} Connected to a .

Path[0、1、2、3、4、5、6].IsVisited by true, So skip these paths .

Path[6].Length + G[6][7] = 10 + 2 < Path[7].Length = 13 so Path[7].Length = 12,Path[7].Predecessor = 6;

Path[6].Length + G[6][8] = 10 + 7 < Path[8].Length = ∞ so Path[8].Length = 17,Path[8].Predecessor = 6;

3. Now look up the picture G All in 9 A path （ Every vertex forms a shortest path ） Which path has not been used as a foothold and the shortest path has the end point as a new foothold .

Path[0、1、2、3、4、5、6].IsVisited by true, So skip . And the rest are false.

Path[7].Length by 12,Path[8].Length by 17, There is no other Path 了 . So choose Path[7] The end V7 As a new foothold . Make V_{0} = 7, From the top V7 Start the next round of search .

step 7：

1. With V_{7 For a foothold , therefore Path[7].IsVisited = true. 2.V7 And V4、V5、V6、V7 And V8 Connected to a . Path[0、1、2、3、4、5、6、7].IsVisited by true, So skip these paths .}

Path[7].Length + G[7][8] = 12 + 4<Path[8].Length = 17 so Path[8].Length = 16,Path[8].Predecessor = 7;

3. Now look up the picture G All in 9 A path （ Every vertex forms a shortest path ） Which path has not been used as a foothold and the shortest path has the end point as a new foothold .

Path[0、1、2、3、4、5、6、7].IsVisited by true, So skip . And the rest are false.

Path[8].Length by 16, Nothing else Path. So choose Path[8] The end V8 As a new foothold . Make V_{0} = 8, From the top V8 Start the next round of search .

step 8：

1. With V_{8} For a foothold , therefore Path[8].IsVisited = true.

2.V_{8} And V_{6}、V_{7} And V_{8} Connected to a .

Path[0、1、2、3、4、5、6、7、8].IsVisited by true, So skip these paths .

There's no path left to explore .

3. Now look up the picture G All in 9 A path （ Every vertex forms a shortest path ） Which path has not been used as a foothold and the shortest path has the end point as a new foothold .

Path[0、1、2、3、4、5、6、7、8].IsVisited by true, So skip . There's no path left to explore . There's no need to start the next round of searching .

Finish exploring ,Path An array is V_{0} The shortest path to each vertex . Output Path The array can be .

step 0~8 All operations in are repeated , Summarize and form code .

## Pseudo code

```
Dijkstra(Graph g, int v, int n)
{
// 0. initialization .
Path[] paths = new Path[n];
// Set each path to its initial value .
for (int i = 0; i < n; i++)
{
paths[i].Length = ∞;
paths[i].Predecessor = -1;
paths[i].IsVisited = false;
}
// With v Find the shortest path for the source .
int k = v;
// v0->v0 The path length of is 0.
paths[k].Length = 0;
// v0->v0 The last vertex of the path is v0.
paths[k].Predecessor = 0;
// Explore the shortest path one by one .
for (int i = 0; i < n; i++)
{
// 1. With vk Find the shortest path to the rest of the vertices for the foothold .
paths[k].IsVisited = true;
// 2. Explore vk Shortest path
for (int j = 0; j < n; j++)
{
// vj Not as a foothold &&
// There are edges (vk, vj) &&
// vk To vj The length of the current path is longer than that of the source point that has been explored vj The path is shorter .
if (paths[j].IsVisited = false &&
g[k][j] != ∞ &&
paths[k].Length + g[k][j] < paths[j].Length)
{
// Update source point to vj The path of （paths[k] It's from the source to vk Shortest path ）.
paths[j].Length = paths[k].Length + g[k][j];
// route j The previous vertex of should be updated to k（ From the source point to vj Is a vk arrive vj Of ）.
paths[j].Predecessor = k;
}
}
// 3. Look for pictures G The shortest path known in . And take the end of the path as a new foothold to explore the shortest path .
// Let the current minimum be infinite .
int min = ∞;
// Traverse all paths .
for (int j = 0; j < n; j++)
{
// The end of the path used to be the path of the foothold , It is the shortest path .
// The end of the path does not need to be used as a foothold to explore the shortest path .
// so , Just skip .
if (paths[j].IsVisited == true)
{
continue;
}
if (paths[j].Length < min)
{
min = paths[j].Length;
k = j;
}
}
// here k It is the subscript of the new shortest path .
}
// Output paths, Each path is the shortest path from the source to the end of the path .
}
```

## analysis

Dijkstra The algorithm solves the shortest path problem from a source point to other points . From the loop nesting, we can see that the time complexity of the algorithm is O(n2).（ Excerpt from 《 Big talk data structure 》.）

The difference between minimum spanning tree and minimum path

Minimum spanning tree ： Map G It takes the shortest distance to connect all the vertices in （ The sum of all paths is the smallest ）. Make sure that the sum of all paths in the graph is the shortest . But is one point closest to another , There is no guarantee .

Minimum path ： From the picture G Set out at the top of a certain point , It takes the shortest distance to get to the other vertices . Ensure the shortest distance from one point to the rest , But is it the shortest way to connect all the points , Not necessarily .

for example ： The minimum spanning tree and minimum path of the following graph .

## Code

Graph is represented by adjacency matrix G. as follows ：

### C# Code

```
using System;
namespace Dijkstra
{
class Program
{
static void Main(string[] args)
{
int numberOfVertexes = 9,
infinity = Constants.Infinity;
int[][] graph = new int[][] {
new int[]{0, 1, 5, infinity, infinity, infinity, infinity, infinity, infinity },
new int[]{ 1, 0, 3, 7, 5, infinity, infinity, infinity, infinity },
new int[]{ 5, 3, 0, infinity, 1, 7, infinity, infinity, infinity },
new int[]{ infinity, 7, infinity, 0, 2, infinity, 3, infinity, infinity },
new int[]{ infinity, 5, 1, 2, 0, 3, 6, 9, infinity },
new int[]{ infinity, infinity, 7, infinity, 3, 0, infinity, 5, infinity },
new int[]{ infinity, infinity, infinity, 3, 6, infinity, 0, 2, 7 },
new int[]{ infinity, infinity, infinity, infinity, 9, 5, 2, 0, 4 },
new int[]{ infinity, infinity, infinity, infinity, infinity, infinity, 7, 4, 0 },
};
Dijkstra(graph, 0, numberOfVertexes);
}
/// <summary>
/// The shortest path from the source point to each vertex in the graph .
/// </summary>
/// <param name="graph"> chart G.</param>
/// <param name="initialVertex"> Source point （ chart G The subscript of the vertex in the ）, Any vertex in a graph can be a source point .</param>
/// <param name="numberOfVertexes"> chart G The number of vertices in .</param>
static void Dijkstra(int[][] graph, int initialVertex, int numberOfVertexes)
{
/**
* Source point to array paths The subscript of is the shortest path of the subscript vertex
* The length of （ Or the sum of weights ）.
* such as ：paths[2], Represents the source point to the vertex v2 Shortest path .
*/
// 0. initialization
Path[] paths = new Path[numberOfVertexes];
/**
* Each path is set to the initial value .
*/
for (int i = 0; i < numberOfVertexes; i++)
{
paths[i] = new Path()
{
Length = Constants.Infinity,
Predecessor = -1,
IsVisited = false
};
}
int k = initialVertex; // Find the shortest path from the source .
paths[k].Length = 0; // Source point -> The path of the source point is 0.
paths[k].Predecessor = k; // Source point -> The precursor of the path of the source point （ the previous ） The vertex is the source . Such as ：(v1, v1).
/**
* chart G Yes n vertices . We need to take each vertex in the graph as the foothold of the shortest path
* Point to explore the shortest path .
*/
// Explore the shortest path one by one .
for (int i = 0; i < numberOfVertexes; i++)
{
paths[k].IsVisited = true; // 1. With Vk Explore its shortest path to the rest of the vertices for a foothold .
/**
* 2. Explore Vk Shortest path . from Vk The rest are related to Vk Associated vertices .
*/
for (int j = 0; j < numberOfVertexes; j++)
{
/**
* if
* 1.paths[j] The corresponding end has never been a foothold .（Vj Not as a foothold .）
* 2. There are edges (Vk, Vj).
* 3. The current shortest path paths[k] The end Vk To Vj The path ratio has been explored to the source point Vj The path of paths[j] It's shorter .
* You need to update paths[j], That is to find a way to vj And shorter than the known length .
*/
if (paths[j].IsVisited == false &&
graph[k][j] != Constants.Infinity &&
(paths[k].Length + graph[k][j] < paths[j].Length))
{
// Update source point to vj The path of （paths[k] It's from the source to vk Shortest path ).
paths[j].Length = paths[k].Length + graph[k][j];
// route j The previous vertex of should be updated to k（ From the source point to vj Is a vk arrive vj Of ）.
paths[j].Predecessor = k;
}
}
/**
* 3. Look for pictures G The shortest path known in . And take the end of the path as a new foothold to explore the shortest path .
* A new foothold Vk, It needs to meet the following conditions ：
* 1. Not as a foothold , namely paths[k].IsVisited by false.
* 2. The path is the smallest , namely paths[k].Length by Min(paths[0].Length, ..., paths[n-1].Length)
*/
int min = Constants.Infinity; // Let the current minimum be infinite .
for (int j = 0; j < numberOfVertexes; j++)
{
if (paths[j].IsVisited) // If ever as a foothold , Then skip and go to the next .
continue;
if (paths[j].Length < min) // Find smaller paths ：
{
k = j; // Record the vertex subscripts （ Number ）.
min = paths[j].Length; // Record the minimum path .
}
} // stay paths[k] Find the minimum path at .
}
// Output results
PrintResult(paths, initialVertex);
}
static void DijkstraSimplified(int[][] graph, int initialVertex, int numberOfVertexes)
{
/**
* Source point to array paths The subscript of is the shortest path of the subscript vertex
* The length of （ Or the sum of weights ）.
* such as ：paths[2], Represents the source point to the vertex v2 Shortest path .
*/
// 0. initialization （ Convert to array , Instead of classes .）
//int[] paths = new int[numberOfVertexes];
int[] lengths = new int[numberOfVertexes];
int[] predecessors = new int[numberOfVertexes];
bool[] isVisiteds = new bool[numberOfVertexes];
//Path[] paths = new Path[numberOfVertexes];
/**
* Each path is set to the initial value .
*/
for (int i = 0; i < numberOfVertexes; i++)
{
lengths[i] = Constants.Infinity;
predecessors[i] = -1;
isVisiteds[i] = false;
}
int k = initialVertex; // Find the shortest path from the source .
lengths[k] = 0; // Source point -> The path of the source point is 0.
predecessors[k] = k; // Source point -> The precursor of the path of the source point （ the previous ） The vertex is the source . Such as ：(v1, v1).
/**
* chart G Yes n vertices . We need to take each vertex in the graph as the foothold of the shortest path
* Point to explore the shortest path .
*/
// Explore the shortest path one by one .
for (int i = 0; i < numberOfVertexes; i++)
{
// 1. With Vk Explore its shortest path to the rest of the vertices for a foothold .
isVisiteds[k] = true;
/**
* 2. Explore Vk Shortest path . from Vk The rest are related to Vk Associated vertices .
*/
for (int j = 0; j < numberOfVertexes; j++)
{
/**
* if
* 1.paths[j] The corresponding end has never been a foothold .（Vj Not as a foothold .）
* 2. There are edges (Vk, Vj).
* 3. The current shortest path paths[k] The end Vk To Vj The path ratio has been explored to the source point Vj The path of paths[j] It's shorter .
* You need to update paths[j], That is to find a way to vj And shorter than the known length .
*/
if (isVisiteds[j] == false &&
graph[k][j] != Constants.Infinity &&
(lengths[k] + graph[k][j] < lengths[j]))
{
// Update source point to vj The path of （paths[k] It's from the source to vk Shortest path ).
lengths[j] = lengths[k] + graph[k][j];
// route j The previous vertex of should be updated to k（ From the source point to vj Is a vk arrive vj Of ）.
predecessors[j] = k;
}
}
/**
* 3. Look for pictures G The shortest path known in . And take the end of the path as a new foothold to explore the shortest path .
* A new foothold Vk, It needs to meet the following conditions ：
* 1. Not as a foothold , namely paths[k].IsVisited by false.
* 2. The path is the smallest , namely paths[k].Length by Min(paths[0].Length, ..., paths[n-1].Length)
*/
int min = Constants.Infinity; // Let the current minimum be infinite .
for (int j = 0; j < numberOfVertexes; j++)
{
if (isVisiteds[j]) // If ever as a foothold , Then skip and go to the next .
continue;
if (lengths[j] < min) // Find smaller paths ：
{
k = j; // Record the vertex subscripts （ Number ）.
min = lengths[j]; // Record the minimum path .
}
} // stay paths[k] Find the minimum path at .
}
// Output results
for (int i = 0; i < numberOfVertexes; i++)
{
string result = $"";
int cursor = i;
if (cursor == initialVertex)
{
result = $"->{cursor}";
}
while (cursor != initialVertex)
{
result = $"->{cursor}{result}";
cursor = predecessors[cursor];
}
result = $"{cursor}{result}: {lengths[i]}";
Console.WriteLine(result);
}
}
static void PrintResult(Path[] paths, int initialVertex)
{
int numberOfVertexes = paths.Length;
for (int i = 0; i < numberOfVertexes; i++)
{
string result = $"";
int cursor = i;
if (cursor == initialVertex)
{
result = $"->{cursor}";
}
while (cursor != initialVertex)
{
result = $"->{cursor}{result}";
cursor = paths[cursor].Predecessor;
}
result = $"{cursor}{result}: {paths[i].Length}";
Console.WriteLine(result);
}
}
static void PrintArray(int[] array)
{
Console.Write("[ ");
for (int i = 0; i < array.Length - 1; i++) // The front of the output array n-1 individual
{
Console.Write($"{ToInfinity(array[i])}, ");
}
if (array.Length > 0) // At the end of the output array 1 individual
{
int n = array.Length - 1;
Console.Write($"{ToInfinity(array[n])}");
}
Console.WriteLine(" ]");
}
static string ToInfinity(int i) => i == int.MaxValue ? "∞" : i.ToString();
}
/**
* Path class . Source points to the rest of the vertices in the graph vk Shortest path .
*/
public class Path
{
// Source to vertex vk The path length of .（ The sum of the weights of the sides of the path . This value is ultimately the shortest path length .）
public int Length { get; set; } = Constants.Infinity;
// The last vertex the path ends at （ The subscript ）.
public int Predecessor { get; set; } = -1;
// Has the end of the path ever been a foothold .
public bool IsVisited { get; set; } = false;
}
/**
* Classes that represent constants .
*/
public static class Constants
{
public static int Infinity { get => int.MaxValue; }
}
}
/**
Running results ：
0->0: 0
0->1: 1
0->1->2: 4
0->1->2->4->3: 7
0->1->2->4: 5
0->1->2->4->5: 8
0->1->2->4->3->6: 10
0->1->2->4->3->6->7: 12
0->1->2->4->3->6->7->8: 16
*/
```

TypeScript Code

```
const infinity: number = Number.MAX_VALUE;
/**
* Path class . Source points to the rest of the vertices in the graph vk Shortest path .
*/
class Path {
// Source to vertex vk The path length of .（ The sum of the weights of the sides of the path . This value is ultimately the shortest path length .）
Length: number = 0;
// The last vertex the path ends at （ The subscript ）.
Predecessor: number = -1;
// Has the end of the path ever been a foothold .
IsVisited: boolean = false;
}
/**
* The shortest path from the source point to each vertex in the graph .
* @param graph chart G.
* @param initialVertex Source point （ chart G The subscript of the vertex in the ）, Any vertex in a graph can be a source point .
* @param numberOfVertexes chart G The number of vertices in .
* @author kokiafan
*/
function dijkstra(graph: number[][], initialVertex: number, numberOfVertexes: number): void {
/**
* Source point to array paths The subscript of is the shortest path of the subscript vertex
* The length of （ Or the sum of weights ）.
* such as ：paths[2], Represents the source point to the vertex v2 Shortest path .
*/
// 0. initialization
let paths: Path[] = [];
/**
* Each path is set to the initial value .
*/
for (let i = 0; i < numberOfVertexes; i++) {
paths[i] = new Path();
paths[i].Length = infinity;
paths[i].Predecessor = -1;
paths[i].IsVisited = false;
}
let k: number = initialVertex; // Find the shortest path from the source .
paths[k].Length = 0; // Source point -> The path of the source point is 0.
paths[k].Predecessor = k; // Source point -> The precursor of the path of the source point （ the previous ） The vertex is the source . Such as ：(v1, v1).
/**
* chart G Yes n vertices . We need to take each vertex in the graph as the foothold of the shortest path
* Point to explore the shortest path .
*/
// Explore the shortest path one by one .
for (let i = 0; i < numberOfVertexes; i++) {
// 1. With Vk Explore its shortest path to the rest of the vertices for a foothold .
paths[k].IsVisited = true;
/**
* 2. Explore Vk Shortest path . from Vk The rest are related to Vk Associated vertices .
*/
for (let j = 0; j < numberOfVertexes; j++) {
/**
* if
* 1.paths[j] The corresponding end has never been a foothold .（Vj Not as a foothold .）
* 2. There are edges (Vk, Vj).
* 3. The current shortest path paths[k] The end Vk To Vj The path ratio has been explored to the source point Vj The path of paths[j] It's shorter .
* You need to update paths[j], That is to find a way to vj And shorter than the known length .
*/
if (paths[j].IsVisited == false &&
graph[k][j] != infinity &&
(paths[k].Length + graph[k][j] < paths[j].Length)) {
// Update source point to vj The path of （paths[k] It's from the source to vk Shortest path ).
paths[j].Length = paths[k].Length + graph[k][j];
// route j The previous vertex of should be updated to k（ From the source point to vj Is a vk arrive vj Of ）.
paths[j].Predecessor = k;
}
}
/**
* 3. Look for pictures G The shortest path known in . And take the end of the path as a new foothold to explore the shortest path .
* A new foothold Vk, It needs to meet the following conditions ：
* 1. Not as a foothold , namely paths[k].IsVisited by false.
* 2. The path is the smallest , namely paths[k].Length by Min(paths[0].Length, ..., paths[n-1].Length)
*/
let min: number = infinity; // Let the current minimum be infinite .
for (let j = 0; j < numberOfVertexes; j++) {
if (paths[j].IsVisited) // If ever as a foothold , Then skip and go to the next .
continue;
if (paths[j].Length < min) // Find smaller paths ：
{
k = j; // Record the vertex subscripts （ Number ）.
min = paths[j].Length; // Record the minimum path .
}
} // stay paths[k] Find the minimum path at .
}
// Output results
console.log(printResult(paths, initialVertex));
}
function dijkstraSimplified(graph: number[][], initialVertex: number, numberOfVertexes: number): void {
/**
* Source point to array paths The subscript of is the shortest path of the subscript vertex
* The length of （ Or the sum of weights ）.
* such as ：paths[2], Represents the source point to the vertex v2 Shortest path .
*/
// 0. initialization （ Convert to array , Instead of classes .）
let lengths: number[] = [];
let predecessors: number[] = [];
let isVisiteds: boolean[] = [];
//Path[] paths = new Path[numberOfVertexes];
/**
* Each path is set to the initial value .
*/
for (let i = 0; i < numberOfVertexes; i++) {
lengths[i] = infinity;
predecessors[i] = -1;
isVisiteds[i] = false;
}
let k: number = initialVertex; // Find the shortest path from the source .
lengths[k] = 0; // Source point -> The path of the source point is 0.
predecessors[k] = k; // Source point -> The precursor of the path of the source point （ the previous ） The vertex is the source . Such as ：(v1, v1).
/**
* chart G Yes n vertices . We need to take each vertex in the graph as the foothold of the shortest path
* Point to explore the shortest path .
*/
// Explore the shortest path one by one .
for (let i = 0; i < numberOfVertexes; i++) {
// 1. With Vk Explore its shortest path to the rest of the vertices for a foothold .
isVisiteds[k] = true;
/**
* 2. Explore Vk Shortest path . from Vk The rest are related to Vk Associated vertices .
*/
for (let j = 0; j < numberOfVertexes; j++) {
/**
* if
* 1.paths[j] The corresponding end has never been a foothold .（Vj Not as a foothold .）
* 2. There are edges (Vk, Vj).
* 3. The current shortest path paths[k] The end Vk To Vj The path ratio has been explored to the source point Vj The path of paths[j] It's shorter .
* You need to update paths[j], That is to find a way to vj And shorter than the known length .
*/
if (isVisiteds[j] == false &&
graph[k][j] != infinity &&
(lengths[k] + graph[k][j] < lengths[j])) {
// Update source point to vj The path of （paths[k] It's from the source to vk Shortest path ).
lengths[j] = lengths[k] + graph[k][j];
// route j The previous vertex of should be updated to k（ From the source point to vj Is a vk arrive vj Of ）.
predecessors[j] = k;
}
}
/**
* 3. Look for pictures G The shortest path known in . And take the end of the path as a new foothold to explore the shortest path .
* A new foothold Vk, It needs to meet the following conditions ：
* 1. Not as a foothold , namely paths[k].IsVisited by false.
* 2. The path is the smallest , namely paths[k].Length by Min(paths[0].Length, ..., paths[n-1].Length)
*/
let min: number = infinity; // Let the current minimum be infinite .
for (let j = 0; j < numberOfVertexes; j++) {
if (isVisiteds[j]) // If ever as a foothold , Then skip and go to the next .
continue;
if (lengths[j] < min) // Find smaller paths ：
{
k = j; // Record the vertex subscripts （ Number ）.
min = lengths[j]; // Record the minimum path .
}
} // stay paths[k] Find the minimum path at .
}
// Output results
for (let i = 0; i < numberOfVertexes; i++) {
let result: string = "";
let cursor: number = i;
if (cursor == initialVertex) {
result = `->${cursor}`;
}
while (cursor != initialVertex) {
result = `->${cursor}${result}`;
cursor = predecessors[cursor];
}
result = `${cursor}${result}: ${lengths[i]}`;
console.log(result);
}
}
function printResult(paths: Path[], initialVertex: number): string {
let numberOfVertexes = paths.length;
let result: string = "";
for (let i = 0; i < numberOfVertexes; i++) {
let line: string = "";
let cursor = i;
if (cursor === initialVertex) {
line = `->${cursor}`;
}
while (cursor != initialVertex) {
line = `->${cursor}${line}`;
cursor = paths[cursor].Predecessor;
}
line = `${cursor}${line}: ${paths[i].Length}`;
result = result.concat(line, "\n");
}
return result;
}
function Main() {
let numberOfVertexes: number = 9;
let graph: number[][] = [
[0, 1, 5, infinity, infinity, infinity, infinity, infinity, infinity],
[1, 0, 3, 7, 5, infinity, infinity, infinity, infinity],
[5, 3, 0, infinity, 1, 7, infinity, infinity, infinity],
[infinity, 7, infinity, 0, 2, infinity, 3, infinity, infinity],
[infinity, 5, 1, 2, 0, 3, 6, 9, infinity],
[infinity, infinity, 7, infinity, 3, 0, infinity, 5, infinity],
[infinity, infinity, infinity, 3, 6, infinity, 0, 2, 7],
[infinity, infinity, infinity, infinity, 9, 5, 2, 0, 4],
[infinity, infinity, infinity, infinity, infinity, infinity, 7, 4, 0],
];
dijkstra(graph, 5, numberOfVertexes);
dijkstraSimplified(graph, 5, numberOfVertexes);
}
Main();
/**
Running results ：
0->0: 0
0->1: 1
0->1->2: 4
0->1->2->4->3: 7
0->1->2->4: 5
0->1->2->4->5: 8
0->1->2->4->3->6: 10
0->1->2->4->3->6->7: 12
0->1->2->4->3->6->7->8: 16
*/
```

Reference material ：

《 Big talk data structure 》 - gemee Writing - tsinghua university press

《 My first algorithm book 》 - Miyazaki Shoichi & Ishida Baohui Writing - People's post and Telecommunications Press or 《 Algorithm animation illustration 》iOS App