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 V0 Point to the other vertices Vk What is the shortest path for ？

demonstration

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

Path[x].Length：V0 To the end of the path V[x] Shortest path . Such as Path[2].Length by V0->V2 Shortest path .

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

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

G[i][j]： Graph is represented by adjacency matrix G.G[i][j] For the top Vi To the top Vj 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 V0->V0 One vertex on the path is V0,V0->V0 The distance to 0, so Path[0].Length = 0.

step 0：

1. With V0 For a foothold , therefore Path[0].IsVisited = true.
2.V0 And V0、V1 And V2 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 V0 = 1, From the top V1 Start the next round of search .

step 1：

1. With V1 For a foothold , therefore Path[1].IsVisited = true.
2.V1 And V0、V1、V2、V3 And V4 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 V0 = 2, From the top V2 Start the next round of search .

step 2：

1. With V2 For a foothold , therefore Path[2].IsVisited = true.
2.V2 And V0、V1、V2、V4、 And V5 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 V4 As a new foothold . Make V0 = 4, From the top V4 Start the next round of search .

step 3：

1. With V4 For a foothold , therefore Path[4].IsVisited = true.
2.V4 And V1、V2、V3、V4、V5、V6 And V7 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 V3 As a new foothold . Make V0=3, From the top V3 Start the next round of search .

step 4：

1. With V3 For a foothold , therefore Path[3].IsVisited = true.
2.V3 And V1、V4 And V6 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 V0 = 5, From the top V5 Start the next round of search .

step 5：

1. With V5 For a foothold , therefore Path[5].IsVisited = true.
2.V5 And V2、V4、V5 And V7 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 V0 = 6, From the top V6 Start the next round of search .

step 6：

1. With V6 For a foothold , therefore Path[6].IsVisited = true.
2.V6 And V3、V4、V7 And V8 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 V0 = 7, From the top V7 Start the next round of search .

step 7：

1. With V7 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 V0 = 8, From the top V8 Start the next round of search .

step 8：

1. With V8 For a foothold , therefore Path[8].IsVisited = true.
2.V8 And V6、V7 And V8 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 V0 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

https://cdmana.com/2021/05/20210522122819974g.html

Scroll to Top