最短路徑問題最經(jīng)典的算法就是Dijkstra算法，雖然不如Floyd算法能夠求全源的最短路徑，但是在效率上明顯強于Floyd算法。

想了解Floyd算法的讀者可以參考動態(tài)規(guī)劃在求解全源最短路徑中的應(yīng)用（JAVA）--Floyd算法

單源最短路徑問題是對于加權(quán)連通圖來說，我們給定一個起點，求出它到其他頂點之間的一系列最短路徑。這個問題不同于從一個起點出發(fā)訪問其他所有頂點的問題（TSP問題），這種問題所求的一組路徑都是從起點出發(fā)通向圖中的一個不同頂點。這些路徑中可能存在公共邊。

Dijkstra算法和Prim算法的用法比較相似，二者都是從頂點集中選擇一個頂點來構(gòu)造樹，但是解決的問題是不同的。Dijkstra算法每次比較的是路徑的總長度，每次要把權(quán)重相加。而Prim算法則直接比較權(quán)重。

以下圖的例子來描述Dijkstra算法的過程：

Input:

5 7
1 2 3
1 4 7
2 4 2
2 3 4
3 4 5
3 5 6
4 5 4

Output:

0 3 7 5 9?

完整代碼如下：

import java.util.Scanner;public class Main {static int[][] e = new int[10][10];static int[] book = new int[10];static int[] dis = new int[10];static int n, m;static int min = 99999999;static int mark = 0;static Scanner input = new Scanner(System.in);public static void main(String[] args) {n = input.nextInt();m = input.nextInt();for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) {e[i][j] = 0;} else {e[i][j] = 99999999;}}}for (int i = 1; i <= m; i++) {int a = input.nextInt();int b = input.nextInt();int c = input.nextInt();e[a][b] = c;e[b][a] = c;}/*** 1到其他各點的距離* */for (int i = 1; i <= n; i++) {dis[i] = e[1][i];}book[1] = 1;dijkstra();for (int i = 1; i <= n; i++) {System.out.print(dis[i] + " ");}}public static void dijkstra() {/*** 遍歷n-1次，每次找出一個 1到某個點的最短距離* */for (int i = 1; i <= n-1; i++) {min = 99999999;/*** 選出離1號點最近的頂點* */for (int j = 1; j <= n; j++) {if (book[j] == 0 && dis[j] < min) {min = dis[j];mark = j;}}book[mark] = 1;/*** 松弛* */for (int j = 1; j <= n; j++) {if (e[mark][j] < 99999999) {if (dis[j] > dis[mark] + e[mark][j]) {dis[j] = dis[mark] + e[mark][j];}}}}} }

時間復(fù)雜度：O(nlogn)，當(dāng)然如果能夠采用鄰接表存儲數(shù)據(jù)會更快。

總結(jié)

以上是生活随笔為你收集整理的贪婪算法在求解最短路径中的应用（JAVA）--Dijkstra算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。