最短路徑(Shortest Path)
對一個 n 個節點的網路(如下圖)，已知連結各節點的路徑及其加權(weight)，求出由網路中的一個節點至其他節點間的最短距離。
圖１. 網路圖
Dijkstra最短路徑演算法所需的資料結構
圖２.網路加權鄰接矩陣
二維陣列 Cost( , )
儲存相鄰節點路徑的加權值，Cost(i, j)表節點 i 和相鄰節點 j間的路徑距離。
Cost(i, j) = ∞ 表節點 i 和 j間並無直接連結。
圖３
Dist( ) 陣列儲存起始節點 V0 至各節點間的距離，經演算法計算後，最後會儲存V0到其他各點間的最短距離。
若此陣列經演算法後，其值如圖３.所示，可知:
節點 0 至節點 4 的最短路徑為10.
節點 0 至節點 7 的最短路徑為9.
圖４.
PreNode( )陣列儲存各節點至起始點最短路徑的前一個節點。
若此陣列經演算法後，其值如圖４.所示，可知:
節點0至節點4的行經節點為 0 -> 3 -> 5 -> 7->4。
節點0至節點7的行經節點為 0 -> 3 -> 5 -> 7。
圖５.
Decided( )陣列儲存起始節點到各節點間的最短路徑是否已經被找到。起始值除起始點設為1外，其他各節點皆設為 0。如起始點為節點0, 則節點0設1，其他節點皆設為0；如起始節點為節點1，則節點1設為1，其餘節點皆設為0，依此類推。
Dijkstra演算法步驟:
step 1:
假設起始節點為0，Dist( )陣列預設為每一個節點與起始節點 0間的路徑距離，NC表示節點與起始節點0間沒有直接連結，程式將NC設為一個遠大於路徑距離的值100000。
PreNode( )陣列中每一個節點的前一節點預設為起始節點0，若起始節點為節點１則全設為1，依此類推。
Decided( )除起始節點設為1(本例起始節點為節點0)，其餘節點皆設為0 表示尚未決是短路徑。
圖６.
Step 2:
由Decided ( )陣列中尚未決定最小路徑的節點中(Decided(i) = 0)找出最短路徑(Dist(i)最小)的節點 Nd，將Decided(Nd)設為１，表示已決定最短距離，並檢查其他尚未決定的節點 w 是否可經由此節點縮短與起始節點間的路徑距離，如Dist(w) > Dist(Nd) + Cost(Nd, w)，Dist(w) = Dist(Nd) + Cost(Nd, w)。
圖7表示: 節點1已找到最短路徑，沒有其他的節點經由其縮短路徑距離。
圖７.
圖8 表示:節點３已找到最短距離，節點４和５可經由節點３縮短路徑距離。
圖８.
經重複Step 2 流程，當Decided() 皆為１時，可由圖３和圖４的Dist( )陣列和PreNode( )陣列得出所有所有節點的最短路徑距離及路徑上的所有節點，
執行結果：
程式碼如下:
// =========================================================
// 從某一點到其餘各點的最短路徑
// Dijkstra() Dijkstra演算法
// find_Shortest() 找出Decided[]=0且Dist最小者
// Dist(N) 從起點到各點的最短距離
// PreNode(N) 各點最短路徑中的前一個頂點
// Decided(N) 最短路徑是否已決定
// 作者: Chris C.S Huang
// 程式語言: VC# 2008 Expression Edition
//=========================================================
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
public const int N = 8; //N是總頂點數
const int NC = 100000; //表二節點間沒有直接連結
//路網圖， NC表示沒有直接連接
public static int[,] Cost = new int[,] {{ 0, 3, 5, 4, NC, NC, NC, NC},
{ 3, 0, NC, 4, NC, NC, NC, NC},
{ 5, NC, 0, 3, NC, 2, NC, NC},
{ 4, 4, 3, 0, 7, 3, NC, NC},
{NC, NC, NC, 7, 0, NC, 6, 1},
{NC, NC, 2, 3, NC, 0, 4, 2},
{NC, NC, NC, NC, 6, 4, 0, 3},
{NC, NC, NC, NC, 1, 2, 3, 0}};
public static int[] Dist = new int[N];
public static int[] Decided = new int[N];
public static int[] PreNode = new int[N];
public static int Start;
static void Main(string[] args)
{
int i;
Console.WriteLine("求某一節點到其他節點間的距離.");
Console.Write("請輸入起點(0-7): ");
try{
Start = Convert.ToInt16(Console.ReadLine());
}
catch(Exception ex)
{
Console.WriteLine(ex.Message);
Console.WriteLine("Wrong Input! Press any key to Exit");
Console.Read();
System.Environment.Exit(1);
}
if(Start > 7 || Start < 0)
{
Console.WriteLine("Wrong Input! Press any key to Exit");
Console.Read();
System.Environment.Exit(1);
}
Dijkstra(Start);
for(i = 0; i < N; i++)
{
if(i != Start)
{
Console.WriteLine("V{0} --> V{1} Distance == {2}", Start, i, Dist[i]); //Dist陣列是行進距離
PrintPath(Start, i);
}
}
Console.WriteLine("Press Enter key to Exit");
Console.Read();
}
unsafe public static void Dijkstra(int Start) ///Start是指定的起點, 例如0表示N0 ; 編譯時必須使用Unsafe選項
{
int Nd, i, w;
for(i = 0; i < N; i++)
{
Dist[i] = Cost[Start, i]; //初設為Cost[]陣列的第Start列
PreNode[i] = Start; //由Start開始走到任意一點
Decided[i] = 0;
}
Decided[Start] = 1;
for(i = 0; i < N; i++)
{
find_Shortest(&Nd); ///找尚未找過且與V0最近的節點Nd
if (PreNode[Nd] == -1)
PreNode[Nd] = Start;
Decided[Nd] = 1;
for(w = 0; w < N; w++)
{
if(Decided[w] == 0 && Dist[w] > (Dist[Nd] + Cost[Nd, w]))
{
Dist[w] = Dist[Nd] + Cost[Nd, w];
PreNode[w] = Nd;
}
}
}
}
unsafe static void find_Shortest(int* Nd) //找出連接目前節點的所有點中距離最短的節點Nd
{
int low = 0, lowest = 32767, i = 0;
for(i = 0; i < N; i++)
{
if(Decided[i]==0 && Dist[i] < lowest)
{
lowest = Dist[i];
low = i;
}
}
*Nd = low;
}
public static void PrintPath(int Start, int Nd) // Start: 起始點, Nd終點
{
int i;
Stack<int> stack = new Stack<int>();
stack.Push(Nd);
i = PreNode[Nd];
while(i != Start)
{
stack.Push(i);
i = PreNode[i];
}
stack.Push(i);
Console.Write("經過節點 : ");
while (stack.Count > 0)
{
Console.Write("{0} ", stack.Pop());
}
Console.WriteLine();
}
}
}
文章定位：
