java實現Dijkstra算法

本文實例為大家分享了java實現Dijkstra算法的具體代碼，供大家參考，具體內容如下

1 問題描述

何為Dijkstra算法？

Dijkstra算法功能：給出加權連通圖中一個頂點，稱之為起點，找出起點到其它所有頂點之間的最短距離。

Dijkstra算法思想：採用貪心法思想，進行n-1次查找（PS:n為加權連通圖的頂點總個數，除去起點，則剩下n-1個頂點），第一次進行查找，找出距離起點最近的一個頂點，標記為已遍歷；下一次進行查找時，從未被遍歷中的頂點尋找距離起點最近的一個頂點， 標記為已遍歷；直到n-1次查找完畢，結束查找，返回最終結果。

2 解決方案

2.1 使用Dijkstra算法得到最短距離示例

此處借用文末參考資料1博客中一個插圖（PS：個人感覺此圖描述簡單易懂）：

2.2 具體編碼

Dijkstra複雜度是O(N^2)，如果用binary heap優化可以達到O((E+N)logN)，用fibonacci heap可以優化到O(NlogN+E) 。

注意，Dijkstra算法只能應用於不含負權值的圖。因為在大多數應用中這個條件都滿足，所以這種侷限性並沒有影響Dijkstra算法的廣泛應用。

其次，大家要注意把Dijkstra算法與尋找最小生成樹的Prim算法區分開來。兩者都是運行貪心法思想，但是Dijkstra算法是比較路徑的長度，所以必須把起點到相應頂點之間的邊的權重相加，而Prim算法則是直接比較相應邊給定的權重。

下面的代碼時間複雜度為O(N^2)，代碼中所用圖為2.1使用Dijkstra算法得到最短距離示例中所給的圖。

 package com.liuzhen.chapter9; public class Dijkstra { /* * 參數adjMatrix:為圖的權重矩陣，權值為-1的兩個頂點表示不能直接相連 * 函數功能：返回頂點0到其它所有頂點的最短距離，其中頂點0到頂點0的最短距離為0 */ public int[] getShortestPaths(int[][] adjMatrix) { int[] result = new int[adjMatrix.length]; //用於存放頂點0到其它頂點的最短距離 boolean[] used = new boolean[adjMatrix.length]; //用於判斷頂點是否被遍歷 used[0] = true; //表示頂點0已被遍歷 for(int i = 1;i<adjMatrix.length;i++) { result[i] = adjMatrix[0][i]; used[i] = false; } for(int i = 1;i <adjMatrix.length;i++) { int min = Integer.MAX_VALUE; //用於暫時存放頂點0到i的最短距離，初始化為Integer型最大值 int k = 0; for(int j = 1;j result[j]) { min = result[j]; k = j; } } used[k] = true; //將距離最小的頂點，記為已遍歷 for(int j = 1;jmin + adjMatrix[k][j] || result[j] == -1)) result[j] = min + adjMatrix[k][j]; } } } return result; } public static void main(String[] args) { Dijkstra test = new Dijkstra(); int[][] adjMatrix = {{0,6,3,-1,-1,-1}, {6,0,2,5,-1,-1}, {3,2,0,3,4,-1}, {-1,5,3,0,2,3}, {-1,-1,4,2,0,5}, {-1,-1,-1,3,5,0}}; int[] result = test.getShortestPaths(adjMatrix); System.out.println("頂點0到圖中所有頂點之間的最短距離為："); for(int i = 0;i<result.length;i++) System.out.print(result[i]+" "); } }

運行結果：

頂點0到圖中所有頂點之間的最短距離為：
0 5 3 6 7 9