Dijkstra算法求解最短路徑分析
最短路徑是圖論算法中的經典問題。圖分為有向圖、無向圖，路徑權值有正值、負值，針對不同的情況需要分別選用不同的算法。在維基上面給出了各種不同的場景應用不同的算法的基本原則：最短路問題。
針對無向圖，正權值路徑，采取Dijkstra算法。
如上圖，是求a到b的最短路徑，這里并不限定b節點，修改為到任意節點的路徑，問題是完全一樣的。
首先需要記錄每個點到原點的距離，這個距離會在每一輪遍歷的過程中刷新。每一個節點到原點的最短路徑是其上一個節點（前驅節點）到原點的最短路徑加上前驅節點到該節點的距離。以這個原則，經過N輪計算就能得到每一個節點的最短距離。
第一輪，可以計算出，2、3、4、5、6到原點1的距離分別為：[7, 9, -1, -1, 14]。-1表示無窮大。取其中最小的，為7，即可以確定1的最短路徑為0，2為下一輪的前驅節點。同時確定2節點的最短路徑為7，路線：1->2。
第二輪，取2節點為前驅節點，按照前驅節點的最短距離加上該節點與前驅節點的距離計算新的最短距離，可以得到3，4，5，6節點到原點的距離為： [17, 22, -1, -1]，此時需要將這一輪得到的結果與上一輪的比較，3節點：17 > 9，最短路徑仍然為9；4節點：22 < 無窮大，刷新4節點的最短路徑為22；5節點：不變，仍然為無窮大；6節點：14 < 無窮大，取14，不變。則可以得到本輪的最短距離為：[9, 22, -1, 14]，取最短路徑最小的節點，為3，作為下一輪的前驅節點。同時確定3節點的最短路徑為9，路線：1->3。
第三輪，同上，以3為前驅節點，得到4，5，6的計算距離為：[20, -1, 11]，按照取最短路徑的原則，與上一輪的進行比較，刷新為：[20, –1, 11]，選定6為下一輪的前驅節點。同時取定6的最短路徑為11，路線：1->3->6。
第四輪，同上，以6為前驅節點，得到4和5的計算距離為[20, 20]，與上一輪進行比較，刷新后為[20, 20]，二者相等只剩下兩個節點，并且二者想等，剩下的計算已經不需要了。則兩個節點的最短路徑都為20。整個計算結束。4的最短路徑為20，路 線：1->3->4。5的最短路徑為20，路線：1->3->6->5。
如果二者不相等，則還需要進行第五輪，先確定二者中的一個的最短路徑和路線，再取定剩下的。直到整個5次循環都完成。
結合上面的文字，算法的偽代碼比較好理解，但是翻譯成代碼還是有一點麻煩：
function Dijkstra(G, w, s)
for each vertex v in V[G] //初始化
d[v] := infinity // 將各點的已知最短距離先設成無窮大
previous[v] := undefined // 各點的已知最短路徑上的前趨都未知
d[s] := 0 // 因為出發點到出發點間不需移動任何距離，所以可以直接將s到s的最小距離設為0
S := empty set
Q := set of all vertices
while Q is not an empty set // Dijkstra演算法主體
u := Extract_Min(Q)
S.append(u)
for each edge outgoing from u as (u,v)
if d[v] > d[u] + w(u,v) // 拓展邊（u,v）。w(u,v)為從u到v的路徑長度。
d[v] := d[u] + w(u,v) // 更新路徑長度到更小的那個和值。
previous[v] := u // 紀錄前趨頂點
</pre>
</div>
翻譯成代碼，則還有一些復雜。
Extract_Min(Q)方法就是從頂點集合中刪除掉距離最小的點，并確定該節點的最短距離和路線。這里給出求最短距離的代碼，具體的路徑記錄還沒有比較簡潔的思路實現。后面有空再來補充。
public class Dijkstra
{
public static final int M = -1;
public static void main(String[] args)
{
int[][] map1 = {
{ 0, 7, 9, M, M, 14 },
{ 7, 0, 10, 15, M, M },
{ 9, 10, 0, 11, M, 2 },
{ M, 15, 11, 0, 6, M },
{ M, M, M, 6, 0, 9 },
{ 14, M, 2, M, 9, 0 } };
int orig = 0;
int[] shortPath = Dijsktra(map1, orig);
if (shortPath == null)
{
return;
}
for (int i = 0; i < shortPath.length; i++)
{
System.out.println("從" + (orig + 1) + "出發到" + (i + 1) + "的最短距離為："
+ shortPath[i]);
}
}
public static int[] Dijsktra(int[][] weight, int orig)
{
int n = weight.length; // 頂點個數
int[] shortest = new int[n]; // 存放從start到其他各點的最短路徑
boolean[] visited = new boolean[n]; // 標記當前該頂點的最短路徑是否已經求出，true表示已求出
// 初始化，第一個頂點求出
shortest[orig] = 0;
visited[orig] = true;
for (int count = 0; count != n - 1; count++) // 要加入n-1個頂點
{
// 選出一個距離初始頂點最近的未標記頂點
int k = M;
int dmin = M;
for (int i = 0; i < n; i++)
{
if (!visited[i] && weight[orig][i] != M)
{
if (dmin == -1 || dmin > weight[orig][i])
{
dmin = weight[orig][i];
k = i;
}
}
}
// 正確的圖生成的矩陣不可能出現K == M的情況
if (k == M)
{
System.out.println("the input map matrix is wrong!");
return null;
}
shortest[k] = dmin;
visited[k] = true;
// 以k為中間點，修正從原點到未訪問各點的距離
for (int i = 0; i < n; i++)
{
if (!visited[i] && weight[k][i] != M)
{
int callen = dmin + weight[k][i];
if (weight[orig][i] == M || weight[orig][i] > callen)
{
weight[orig][i] = callen;
}
}
}
}
return shortest;
}