本文實(shí)例為大家分享了java實(shí)現(xiàn)Dijkstra算法的具體代碼，供大家參考，具體內(nèi)容如下

1 問(wèn)題描述

何為Dijkstra算法？

Dijkstra算法功能：給出加權(quán)連通圖中一個(gè)頂點(diǎn)，稱(chēng)之為起點(diǎn)，找出起點(diǎn)到其它所有頂點(diǎn)之間的最短距離。

Dijkstra算法思想：采用貪心法思想，進(jìn)行n-1次查找（PS:n為加權(quán)連通圖的頂點(diǎn)總個(gè)數(shù)，除去起點(diǎn)，則剩下n-1個(gè)頂點(diǎn)），第一次進(jìn)行查找，找出距離起點(diǎn)最近的一個(gè)頂點(diǎn)，標(biāo)記為已遍歷；下一次進(jìn)行查找時(shí)，從未被遍歷中的頂點(diǎn)尋找距離起點(diǎn)最近的一個(gè)頂點(diǎn)， 標(biāo)記為已遍歷；直到n-1次查找完畢，結(jié)束查找，返回最終結(jié)果。

2 解決方案

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

此處借用文末參考資料1博客中一個(gè)插圖（PS：個(gè)人感覺(jué)此圖描述簡(jiǎn)單易懂）：

2.2 具體編碼

Dijkstra復(fù)雜度是O(N^2)，如果用binary heap優(yōu)化可以達(dá)到O((E+N)logN)，用fibonacci heap可以?xún)?yōu)化到O(NlogN+E) 。

注意，Dijkstra算法只能應(yīng)用于不含負(fù)權(quán)值的圖。因?yàn)樵诖蠖鄶?shù)應(yīng)用中這個(gè)條件都滿(mǎn)足，所以這種局限性并沒(méi)有影響Dijkstra算法的廣泛應(yīng)用。

其次，大家要注意把Dijkstra算法與尋找最小生成樹(shù)的Prim算法區(qū)分開(kāi)來(lái)。兩者都是運(yùn)行貪心法思想，但是Dijkstra算法是比較路徑的長(zhǎng)度，所以必須把起點(diǎn)到相應(yīng)頂點(diǎn)之間的邊的權(quán)重相加，而Prim算法則是直接比較相應(yīng)邊給定的權(quán)重。

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

package com.liuzhen.chapter9;public class Dijkstra { /* * 參數(shù)adjMatrix:為圖的權(quán)重矩陣，權(quán)值為-1的兩個(gè)頂點(diǎn)表示不能直接相連 * 函數(shù)功能：返回頂點(diǎn)0到其它所有頂點(diǎn)的最短距離，其中頂點(diǎn)0到頂點(diǎn)0的最短距離為0 */ public int[] getShortestPaths(int[][] adjMatrix) { int[] result = new int[adjMatrix.length]; //用于存放頂點(diǎn)0到其它頂點(diǎn)的最短距離 boolean[] used = new boolean[adjMatrix.length]; //用于判斷頂點(diǎn)是否被遍歷 used[0] = true; //表示頂點(diǎn)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; //用于暫時(shí)存放頂點(diǎn)0到i的最短距離，初始化為Integer型最大值 int k = 0; for(int j = 1;j < adjMatrix.length;j++) { //找到頂點(diǎn)0到其它頂點(diǎn)中距離最小的一個(gè)頂點(diǎn)if(!used[j] && result[j] != -1 && min > result[j]) { min = result[j]; k = j;} } used[k] = true; //將距離最小的頂點(diǎn)，記為已遍歷 for(int j = 1;j < adjMatrix.length;j++) { //然后，將頂點(diǎn)0到其它頂點(diǎn)的距離與加入中間頂點(diǎn)k之后的距離進(jìn)行比較，更新最短距離if(!used[j]) { //當(dāng)頂點(diǎn)j未被遍歷時(shí) //首先，頂點(diǎn)k到頂點(diǎn)j要能通行；這時(shí)，當(dāng)頂點(diǎn)0到頂點(diǎn)j的距離大于頂點(diǎn)0到k再到j(luò)的距離或者頂點(diǎn)0無(wú)法直接到達(dá)頂點(diǎn)j時(shí)，更新頂點(diǎn)0到頂點(diǎn)j的最短距離 if(adjMatrix[k][j] != -1 && (result[j] > min + 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('頂點(diǎn)0到圖中所有頂點(diǎn)之間的最短距離為：'); for(int i = 0;i < result.length;i++) System.out.print(result[i]+' '); }}

運(yùn)行結(jié)果：

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

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持好吧啦網(wǎng)。