狄克斯特拉（Dijkstra）算法
引入
從A點到B點的最短路徑是什麼？求最短路徑的兩種算法：Dijkstra算法和Floyd算法。
網圖：帶權圖。
非網圖最短路徑：兩頂點間經過的邊數最少的路徑。（非網圖也可被理解為各邊權值為1的網圖。）
網圖最短路徑：兩頂點間經過的邊上權值之和最少的路徑。路徑上第一個頂點是源點，最後的頂點是終點。
問題：下圖中V0 點到其餘各個頂點Vk的最短路徑是什麼？
演示
設圖G中的每個頂點為V0到該點的路徑。並用以下形式來表示：
Path[x].Length：V0到該路徑所處終點的V[x]的最短路徑。如Path[2].Length為V0->V2的最短路徑。
Path[x].Predecessor：V0到該路徑所處終點的上一個頂點的編號（下標）。如Path[2].Predecessor為0，表示V0->V2的最短路徑，頂點V2的前一個頂點為V1，即經過V1然後到達V2。
Path[x].IsVisited：頂點Vx是否曾作為立足點來查找接下來的最短路徑。其中Vx是V0到該路徑所處的終點。
G[i][j]：用鄰接矩陣表示圖G。G[i][j]為頂點Vi到頂點Vj的權值。
0.初始化：
所有路徑的Predecessor設為-1，Length設為0，IsVisited設為false。
從源點開始Path[0].Predecessor = 0，因為V0->V0路徑上的一個頂點為V0，V0->V0的距離為0，故Path[0].Length = 0。
步驟0：
1.以V0為立足點，所以Path[0].IsVisited = true。
2.V0與V0、V1及V2相連。
Path[0].IsVisited為true，故跳過這個路徑。
Path[0].Length + G[0][1] = 0 + 1 < Path[2].Length = ∞故Path[1].Length = 1，Path[1].Predecessor = 0；
Path[0].Length + G[0][2] = 0 + 5 < Path[2].Length = ∞故Path[2].Length = 5，Path[2].Predecessor = 0；
3.現查找圖G中所有9個路徑（每個頂點皆構成一個最短路徑）中未曾作為立足點且路徑最短的哪個路徑的終點作為新的立足點。
Path[0].IsVisited為true，故跳過。而其餘的為false。
Path[1].Length為1，Path[2].Length為5，其餘Path.Length為∞。故選Path[1]的終點V1作為新的立足點。令V0 = 1，從頂點V1開始下一輪尋找。
步驟1：
1.以V1為立足點，所以Path[1].IsVisited = true。
2.V1與V0、V1、V2、V3及V4相連。
Path[0].IsVisited為true，Path[1].IsVisited為true，故跳過這些路徑。
Path[1].Length + G[1][2] = 1 + 3 < Path[2].Length = 5故Path[2].Length = 4，Path[2].Predecessor = 1；
Path[1].Length + G[1][3] = 1 + 7 < Path[3].Length = ∞故Path[3].Length = 8，Path[3].Predecessor = 1；
Path[1].Length + G[1][4] = 1 + 5 < Path[4].Length = ∞故Path[4].Length = 6，Path[4].Predecessor = 1；
3.現查找圖G中所有9個路徑（每個頂點皆構成一個最短路徑）中未曾作為立足點且路徑最短的哪個路徑的終點作為新的立足點。
Path[0、1].IsVisited為true，故跳過。而其餘的為false。
Path[2].Length為4，Path[3].Length為8，Path[4].Length為6，其餘Path.Length為∞。故選Path[2]的終點V2作為新的立足點。令V0 = 2，從頂點V2開始下一輪尋找。
步驟2：
1.以V2為立足點，所以Path[2].IsVisited = true。
2.V2與V0、V1、V2、V4、及V5相連。
Path[0、1、2].IsVisited為true，故跳過這些路徑。
Path[2].Length + G[2][4] = 4 + 1 < Path[4].Length = 6故Path[4].Length = 5，Path[4].Predecessor = 2；
Path[2].Length + G[2][5] = 4 + 7 < Path[5].Length = ∞故Path[5].Length = 11，Path[5].Predecessor = 2；
3.現查找圖G中所有9個路徑（每個頂點皆構成一個最短路徑）中未曾作為立足點且路徑最短的哪個路徑的終點作為新的立足點。
Path[0、1、2].IsVisited為true，故跳過。而其餘的為false。
Path[3].Length為8，Path[4].Length為5，Path[5].Length為11，其餘Path.Length為∞。故選Path[4]的終點V4作為新的立足點。令V0 = 4，從頂點V4開始下一輪尋找。
步驟3：
1.以V4為立足點，所以Path[4].IsVisited = true。
2.V4與V1、V2、V3、V4、V5、V6及V7相連。
Path[0、1、2、4].IsVisited為true，故跳過這些路徑。
Path[4].Length + G[4][3] = 5 + 2 < Path[3].Length = 8故Path[3].Length = 7，Path[3].Predecessor = 4；
Path[4].Length + G[4][5] = 5 + 3 < Path[5].Length = 11故Path[5].Length = 8，Path[5].Predecessor = 4；
Path[4].Length + G[4][6] = 5 + 6 < Path[6].Length = ∞故Path[6].Length = 11，Path[6].Predecessor = 4；
Path[4].Length + G[4][7] = 5 + 9 < Path[7].Length = ∞故Path[7].Length = 14，Path[6].Predecessor = 4；
3.現查找圖G中所有9個路徑（每個頂點皆構成一個最短路徑）中未曾作為立足點且路徑最短的哪個路徑的終點作為新的立足點。
Path[0、1、2、4].IsVisited為true，故跳過。而其餘的為false。
Path[3].Length為7，Path[5].Length為8，Path[6].Length為11，Path[7].Length為14，其餘Path.Length為∞。故選Path[3]的終點V3作為新的立足點。令V0=3，從頂點V3開始下一輪尋找。
步驟4：
1.以V3為立足點，所以Path[3].IsVisited = true。
2.V3與V1、V4及V6相連。
Path[0、1、2、3、4].IsVisited為true，故跳過這些路徑。
Path[3].Length + G[3][6] = 7 + 3 < Path[6].Length = 11故Path[6].Length = 10，Path[6].Predecessor = 3；
3.現查找圖G中所有9個路徑（每個頂點皆構成一個最短路徑）中未曾作為立足點且路徑最短的哪個路徑的終點作為新的立足點。
Path[0、1、2、3、4].IsVisited為true，故跳過。而其餘的為false。
Path[5].Length為8，Path[6].Length為10，Path[7].Length為14，其餘Path.Length為∞。故選Path[5]的終點V5作為新的立足點。令V0 = 5，從頂點V5開始下一輪尋找。
步驟5：
1.以V5為立足點，所以Path[5].IsVisited = true。
2.V5與V2、V4、V5及V7相連。
Path[0、1、2、3、4、5].IsVisited為true，故跳過這些路徑。
Path[5].Length + G[5][7] = 8 + 5 < Path[7].Length = 14故Path[7].Length = 13，Path[7].Predecessor = 5；
3.現查找圖G中所有9個路徑（每個頂點皆構成一個最短路徑）中未曾作為立足點且路徑最短的哪個路徑的終點作為新的立足點。
Path[0、1、2、3、4、5].IsVisited為true，故跳過。而其餘的為false。
Path[6].Length為10，Path[7].Length為13，其餘Path.Length為∞。故選Path[6]的終點V6作為新的立足點。令V0 = 6，從頂點V6開始下一輪尋找。
步驟6：
1.以V6為立足點，所以Path[6].IsVisited = true。
2.V6與V3、V4、V7及V8相連。
Path[0、1、2、3、4、5、6].IsVisited為true，故跳過這些路徑。
Path[6].Length + G[6][7] = 10 + 2 < Path[7].Length = 13故Path[7].Length = 12，Path[7].Predecessor = 6；
Path[6].Length + G[6][8] = 10 + 7 < Path[8].Length = ∞故Path[8].Length = 17，Path[8].Predecessor = 6；
3.現查找圖G中所有9個路徑（每個頂點皆構成一個最短路徑）中未曾作為立足點且路徑最短的哪個路徑的終點作為新的立足點。
Path[0、1、2、3、4、5、6].IsVisited為true，故跳過。而其餘的為false。
Path[7].Length為12，Path[8].Length為17，沒有其餘Path了。故選Path[7]的終點V7作為新的立足點。令V0 = 7，從頂點V7開始下一輪尋找。
步驟7：
1.以V7為立足點，所以Path[7].IsVisited = true。
2.V7與V4、V5、V6、V7及V8相連。
Path[0、1、2、3、4、5、6、7].IsVisited為true，故跳過這些路徑。
Path[7].Length + G[7][8] = 12 + 4<Path[8].Length = 17故Path[8].Length = 16，Path[8].Predecessor = 7；
3.現查找圖G中所有9個路徑（每個頂點皆構成一個最短路徑）中未曾作為立足點且路徑最短的哪個路徑的終點作為新的立足點。
Path[0、1、2、3、4、5、6、7].IsVisited為true，故跳過。而其餘的為false。
Path[8].Length為16，無其餘Path。故選Path[8]的終點V8作為新的立足點。令V0 = 8，從頂點V8開始下一輪尋找。
步驟8：
1.以V8為立足點，所以Path[8].IsVisited = true。
2.V8與V6、V7及V8相連。
Path[0、1、2、3、4、5、6、7、8].IsVisited為true，故跳過這些路徑。
已無沒有探索過的路徑了。
3.現查找圖G中所有9個路徑（每個頂點皆構成一個最短路徑）中未曾作為立足點且路徑最短的哪個路徑的終點作為新的立足點。
Path[0、1、2、3、4、5、6、7、8].IsVisited為true，故跳過。已無沒有探索過的路徑了。無需開始下一輪的尋找。
完成探索，Path數組即是V0到各頂點的最短路徑。輸出Path數組即可。
步驟0~8中的操作都是重複的，總結形成代碼。
偽代碼
Dijkstra(Graph g, int v, int n)
{
// 0. 初始化。
Path[] paths = new Path[n];
// 將每個路徑設為初始值。
for (int i = 0; i < n; i++)
{
paths[i].Length = ∞;
paths[i].Predecessor = -1;
paths[i].IsVisited = false;
}
// 以v為源點尋找最短路徑。
int k = v;
// v0->v0的路徑長度為0。
paths[k].Length = 0;
// v0->v0路徑的上一個頂點為v0。
paths[k].Predecessor = 0;
// 逐個頂點探索最短路徑。
for (int i = 0; i < n; i++)
{
// 1.以vk為立足點尋找它到其餘頂點的最短路徑。
paths[k].IsVisited = true;
// 2.探索vk的最短路徑
for (int j = 0; j < n; j++)
{
// vj未曾作為立足點 &&
// 存在邊(vk, vj) &&
// vk到vj的當前路徑長度比已經探索到的源點到vj的路徑還更短。
if (paths[j].IsVisited = false &&
g[k][j] != ∞ &&
paths[k].Length + g[k][j] < paths[j].Length)
{
// 更新源點到vj的路徑（paths[k]是源點到vk的最短路徑）。
paths[j].Length = paths[k].Length + g[k][j];
// 路徑j的上一個頂點應該更新為k（即源點到vj是經過vk到達vj的）。
paths[j].Predecessor = k;
}
}
// 3.尋找圖G中已知的最短路徑。並以該路徑的終點為新的立足點探索最短路徑。
// 設當前最小值為無窮。
int min = ∞;
// 遍歷所有路徑。
for (int j = 0; j < n; j++)
{
// 路徑的終點曾作為立足點的路徑，其已是最短路徑。
// 該路徑的終點無需再作為立足點去探索最短路徑。
// 故，直接跳過。
if (paths[j].IsVisited == true)
{
continue;
}
if (paths[j].Length < min)
{
min = paths[j].Length;
k = j;
}
}
// 此時k即是新的最短路徑的下標。
}
// 輸出paths，每條路徑皆為源點到該路徑的終點的最短路徑。
}
分析
Dijkstra算法解決了從某源點到其餘各點的最短路徑問題。從循環嵌套可知算法的時間複雜度為O(n2)。（摘自《大話數據結構》。）
最小生成樹與最小路徑的區別
最小生成樹：將圖G中所有頂點相連所用的路程最短（所有路徑之和最小）。保證圖中的所有路徑之和最短。但某個點到另一個點是否最近，不能保證。
最小路徑：從圖G某各頂點出發，到其它頂點所用路程最短。保證某個點到其餘點路程最短，但把所有點連接起來是否路程最短，就不一定了。
例如：下面這幅圖的最小生成樹和最小路徑。
代碼
用鄰接矩陣來表示圖G。如下：
C#代碼
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>
/// 源點到圖中各頂點的最短路徑。
/// </summary>
/// <param name="graph">圖G。</param>
/// <param name="initialVertex">源點（圖G中頂點的下標），圖中任意頂點都可以是源點。</param>
/// <param name="numberOfVertexes">圖G中頂點的數目。</param>
static void Dijkstra(int[][] graph, int initialVertex, int numberOfVertexes)
{
/**
* 源點到以數組paths的下標為下標的頂點的最短路徑
* 的長度（或權重累加和）。
* 比如：paths[2]，表示源點到頂點v2的最短路徑。
*/
// 0.初始化
Path[] paths = new Path[numberOfVertexes];
/**
* 每條路徑設為初始值。
*/
for (int i = 0; i < numberOfVertexes; i++)
{
paths[i] = new Path()
{
Length = Constants.Infinity,
Predecessor = -1,
IsVisited = false
};
}
int k = initialVertex; // 從源點開始尋找最短路徑。
paths[k].Length = 0; // 源點->源點的路徑為0。
paths[k].Predecessor = k; // 源點->源點的路徑的前驅（上一個）頂點就是源點。如：(v1, v1)。
/**
* 圖G有n個頂點。需要以圖中各頂點作為最短路徑的立足
* 點探索最短路徑。
*/
// 逐個頂點探索最短路徑。
for (int i = 0; i < numberOfVertexes; i++)
{
paths[k].IsVisited = true; // 1.以Vk為立足點探索它到其餘頂點的最短路徑。
/**
* 2.探索Vk的最短路徑。從Vk到其餘各與Vk相關聯的頂點。
*/
for (int j = 0; j < numberOfVertexes; j++)
{
/**
* 若
* 1.paths[j]對應的終點未曾作為立足點。（Vj未曾作為立足點。）
* 2.存在邊(Vk, Vj)。
* 3.當前最短路徑paths[k]的終點Vk到Vj的路徑比已經探索到的源點到Vj的路徑paths[j]還更短。
* 則需要更新paths[j]，即發現路一條到vj的新路徑且比已知長度更短。
*/
if (paths[j].IsVisited == false &&
graph[k][j] != Constants.Infinity &&
(paths[k].Length + graph[k][j] < paths[j].Length))
{
// 更新源點到vj的路徑（paths[k]是源點到vk的最短路徑)。
paths[j].Length = paths[k].Length + graph[k][j];
// 路徑j的上一個頂點應該更新為k（即源點到vj是經過vk到達vj的）。
paths[j].Predecessor = k;
}
}
/**
* 3.尋找圖G中已知的最短路徑。並以該路徑的終點為新的立足點探索最短路徑。
* 新立足點Vk，其需滿足以下條件：
* 1.未曾作為立足點，即paths[k].IsVisited為false。
* 2.路徑最小，即paths[k].Length為Min(paths[0].Length, ..., paths[n-1].Length)
*/
int min = Constants.Infinity; // 設當前最小值為無窮。
for (int j = 0; j < numberOfVertexes; j++)
{
if (paths[j].IsVisited) // 若曾作為立足點，則跳過並轉向下一個。
continue;
if (paths[j].Length < min) // 發現更小的路徑：
{
k = j; // 記錄下頂點下標（編號）。
min = paths[j].Length; // 記錄下最小路徑。
}
} // 在paths[k]處找到最小路徑。
}
// 輸出結果
PrintResult(paths, initialVertex);
}
static void DijkstraSimplified(int[][] graph, int initialVertex, int numberOfVertexes)
{
/**
* 源點到以數組paths的下標為下標的頂點的最短路徑
* 的長度（或權重累加和）。
* 比如：paths[2]，表示源點到頂點v2的最短路徑。
*/
// 0.初始化（轉換為數組，而不用類。）
//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];
/**
* 每條路徑設為初始值。
*/
for (int i = 0; i < numberOfVertexes; i++)
{
lengths[i] = Constants.Infinity;
predecessors[i] = -1;
isVisiteds[i] = false;
}
int k = initialVertex; // 從源點開始尋找最短路徑。
lengths[k] = 0; // 源點->源點的路徑為0。
predecessors[k] = k; // 源點->源點的路徑的前驅（上一個）頂點就是源點。如：(v1, v1)。
/**
* 圖G有n個頂點。需要以圖中各頂點作為最短路徑的立足
* 點探索最短路徑。
*/
// 逐個頂點探索最短路徑。
for (int i = 0; i < numberOfVertexes; i++)
{
// 1.以Vk為立足點探索它到其餘頂點的最短路徑。
isVisiteds[k] = true;
/**
* 2.探索Vk的最短路徑。從Vk到其餘各與Vk相關聯的頂點。
*/
for (int j = 0; j < numberOfVertexes; j++)
{
/**
* 若
* 1.paths[j]對應的終點未曾作為立足點。（Vj未曾作為立足點。）
* 2.存在邊(Vk, Vj)。
* 3.當前最短路徑paths[k]的終點Vk到Vj的路徑比已經探索到的源點到Vj的路徑paths[j]還更短。
* 則需要更新paths[j]，即發現路一條到vj的新路徑且比已知長度更短。
*/
if (isVisiteds[j] == false &&
graph[k][j] != Constants.Infinity &&
(lengths[k] + graph[k][j] < lengths[j]))
{
// 更新源點到vj的路徑（paths[k]是源點到vk的最短路徑)。
lengths[j] = lengths[k] + graph[k][j];
// 路徑j的上一個頂點應該更新為k（即源點到vj是經過vk到達vj的）。
predecessors[j] = k;
}
}
/**
* 3.尋找圖G中已知的最短路徑。並以該路徑的終點為新的立足點探索最短路徑。
* 新立足點Vk，其需滿足以下條件：
* 1.未曾作為立足點，即paths[k].IsVisited為false。
* 2.路徑最小，即paths[k].Length為Min(paths[0].Length, ..., paths[n-1].Length)
*/
int min = Constants.Infinity; // 設當前最小值為無窮。
for (int j = 0; j < numberOfVertexes; j++)
{
if (isVisiteds[j]) // 若曾作為立足點，則跳過並轉向下一個。
continue;
if (lengths[j] < min) // 發現更小的路徑：
{
k = j; // 記錄下頂點下標（編號）。
min = lengths[j]; // 記錄下最小路徑。
}
} // 在paths[k]處找到最小路徑。
}
// 輸出結果
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++) // 輸出數組的前面n-1個
{
Console.Write($"{ToInfinity(array[i])}, ");
}
if (array.Length > 0) // 輸出數組的最後1個
{
int n = array.Length - 1;
Console.Write($"{ToInfinity(array[n])}");
}
Console.WriteLine(" ]");
}
static string ToInfinity(int i) => i == int.MaxValue ? "∞" : i.ToString();
}
/**
* 路徑類。源點到圖中其餘頂點vk的最短路徑。
*/
public class Path
{
// 源點到頂點vk的路徑長度。（途徑的各邊的權值之和。該值最終即是最短路徑長度。）
public int Length { get; set; } = Constants.Infinity;
// 路徑終點途經的上一個頂點（的下標）。
public int Predecessor { get; set; } = -1;
// 路徑終點是否曾作為立足點。
public bool IsVisited { get; set; } = false;
}
/**
* 表示常量的類。
*/
public static class Constants
{
public static int Infinity { get => int.MaxValue; }
}
}
/**
運行結果：
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代碼
const infinity: number = Number.MAX_VALUE;
/**
* 路徑類。源點到圖中其餘頂點vk的最短路徑。
*/
class Path {
// 源點到頂點vk的路徑長度。（途徑的各邊的權值之和。該值最終即是最短路徑長度。）
Length: number = 0;
// 路徑終點途經的上一個頂點（的下標）。
Predecessor: number = -1;
// 路徑終點是否曾作為立足點。
IsVisited: boolean = false;
}
/**
* 源點到圖中各頂點的最短路徑。
* @param graph 圖G。
* @param initialVertex 源點（圖G中頂點的下標），圖中任意頂點都可以是源點。
* @param numberOfVertexes 圖G中頂點的數目。
* @author kokiafan
*/
function dijkstra(graph: number[][], initialVertex: number, numberOfVertexes: number): void {
/**
* 源點到以數組paths的下標為下標的頂點的最短路徑
* 的長度（或權重累加和）。
* 比如：paths[2]，表示源點到頂點v2的最短路徑。
*/
// 0.初始化
let paths: Path[] = [];
/**
* 每條路徑設為初始值。
*/
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; // 從源點開始尋找最短路徑。
paths[k].Length = 0; // 源點->源點的路徑為0。
paths[k].Predecessor = k; // 源點->源點的路徑的前驅（上一個）頂點就是源點。如：(v1, v1)。
/**
* 圖G有n個頂點。需要以圖中各頂點作為最短路徑的立足
* 點探索最短路徑。
*/
// 逐個頂點探索最短路徑。
for (let i = 0; i < numberOfVertexes; i++) {
// 1.以Vk為立足點探索它到其餘頂點的最短路徑。
paths[k].IsVisited = true;
/**
* 2.探索Vk的最短路徑。從Vk到其餘各與Vk相關聯的頂點。
*/
for (let j = 0; j < numberOfVertexes; j++) {
/**
* 若
* 1.paths[j]對應的終點未曾作為立足點。（Vj未曾作為立足點。）
* 2.存在邊(Vk, Vj)。
* 3.當前最短路徑paths[k]的終點Vk到Vj的路徑比已經探索到的源點到Vj的路徑paths[j]還更短。
* 則需要更新paths[j]，即發現路一條到vj的新路徑且比已知長度更短。
*/
if (paths[j].IsVisited == false &&
graph[k][j] != infinity &&
(paths[k].Length + graph[k][j] < paths[j].Length)) {
// 更新源點到vj的路徑（paths[k]是源點到vk的最短路徑)。
paths[j].Length = paths[k].Length + graph[k][j];
// 路徑j的上一個頂點應該更新為k（即源點到vj是經過vk到達vj的）。
paths[j].Predecessor = k;
}
}
/**
* 3.尋找圖G中已知的最短路徑。並以該路徑的終點為新的立足點探索最短路徑。
* 新立足點Vk，其需滿足以下條件：
* 1.未曾作為立足點，即paths[k].IsVisited為false。
* 2.路徑最小，即paths[k].Length為Min(paths[0].Length, ..., paths[n-1].Length)
*/
let min: number = infinity; // 設當前最小值為無窮。
for (let j = 0; j < numberOfVertexes; j++) {
if (paths[j].IsVisited) // 若曾作為立足點，則跳過並轉向下一個。
continue;
if (paths[j].Length < min) // 發現更小的路徑：
{
k = j; // 記錄下頂點下標（編號）。
min = paths[j].Length; // 記錄下最小路徑。
}
} // 在paths[k]處找到最小路徑。
}
// 輸出結果
console.log(printResult(paths, initialVertex));
}
function dijkstraSimplified(graph: number[][], initialVertex: number, numberOfVertexes: number): void {
/**
* 源點到以數組paths的下標為下標的頂點的最短路徑
* 的長度（或權重累加和）。
* 比如：paths[2]，表示源點到頂點v2的最短路徑。
*/
// 0.初始化（轉換為數組，而不用類。）
let lengths: number[] = [];
let predecessors: number[] = [];
let isVisiteds: boolean[] = [];
//Path[] paths = new Path[numberOfVertexes];
/**
* 每條路徑設為初始值。
*/
for (let i = 0; i < numberOfVertexes; i++) {
lengths[i] = infinity;
predecessors[i] = -1;
isVisiteds[i] = false;
}
let k: number = initialVertex; // 從源點開始尋找最短路徑。
lengths[k] = 0; // 源點->源點的路徑為0。
predecessors[k] = k; // 源點->源點的路徑的前驅（上一個）頂點就是源點。如：(v1, v1)。
/**
* 圖G有n個頂點。需要以圖中各頂點作為最短路徑的立足
* 點探索最短路徑。
*/
// 逐個頂點探索最短路徑。
for (let i = 0; i < numberOfVertexes; i++) {
// 1.以Vk為立足點探索它到其餘頂點的最短路徑。
isVisiteds[k] = true;
/**
* 2.探索Vk的最短路徑。從Vk到其餘各與Vk相關聯的頂點。
*/
for (let j = 0; j < numberOfVertexes; j++) {
/**
* 若
* 1.paths[j]對應的終點未曾作為立足點。（Vj未曾作為立足點。）
* 2.存在邊(Vk, Vj)。
* 3.當前最短路徑paths[k]的終點Vk到Vj的路徑比已經探索到的源點到Vj的路徑paths[j]還更短。
* 則需要更新paths[j]，即發現路一條到vj的新路徑且比已知長度更短。
*/
if (isVisiteds[j] == false &&
graph[k][j] != infinity &&
(lengths[k] + graph[k][j] < lengths[j])) {
// 更新源點到vj的路徑（paths[k]是源點到vk的最短路徑)。
lengths[j] = lengths[k] + graph[k][j];
// 路徑j的上一個頂點應該更新為k（即源點到vj是經過vk到達vj的）。
predecessors[j] = k;
}
}
/**
* 3.尋找圖G中已知的最短路徑。並以該路徑的終點為新的立足點探索最短路徑。
* 新立足點Vk，其需滿足以下條件：
* 1.未曾作為立足點，即paths[k].IsVisited為false。
* 2.路徑最小，即paths[k].Length為Min(paths[0].Length, ..., paths[n-1].Length)
*/
let min: number = infinity; // 設當前最小值為無窮。
for (let j = 0; j < numberOfVertexes; j++) {
if (isVisiteds[j]) // 若曾作為立足點，則跳過並轉向下一個。
continue;
if (lengths[j] < min) // 發現更小的路徑：
{
k = j; // 記錄下頂點下標（編號）。
min = lengths[j]; // 記錄下最小路徑。
}
} // 在paths[k]處找到最小路徑。
}
// 輸出結果
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();
/**
運行結果：
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
*/
參考資料：
《大話數據結構》 – 程傑 著 – 清華大學出版社
《我的第一本算法書》 – 宮崎修一 & 石田保輝 著 – 人民郵電出版社 或 《算法動畫圖解》iOS App
