前言

• 最短路徑的算法有兩個，Dijkstra算法 和 Floyd算法。
• Dijkstra算法 解決的是 單源 最短路徑問題。
• Floyd算法解決的是 多源 最短路徑問題，并且可以處理負(fù)權(quán)圖。
• 今天要講的就是Dijkstra算法。
• 加：feng--Insist(大寫的i)，進(jìn)java交流群討論互聯(lián)網(wǎng)+技術(shù)?？伤饕狿PT等資料。
• 其他資料，建議先看本篇博客。：Dijkstra算法和Floyd算法：https://blog.csdn.net/weixin_43872728/article/details/100662957
• 代碼位置：https://github.com/fengfanli/dataStructuresAndAlgorithm/tree/master/src/com/feng/algorithm/self_learn

一、單源最短路徑

1、單源最短路徑問題

• 解決的問題: 求解單源最短路徑,即各個節(jié)點到達(dá)源點的最短路徑或權(quán)值。如下圖中
  
  考察其他所有節(jié)點到源點的最短路徑和長度
• 局限性: 無法解決權(quán)值為負(fù)數(shù)的情況
• 資料
  • 可先看匹配視頻：https://www.bilibili.com/video/BV1o44y1B7NM/
  • 代碼：待上傳。

2、Dijkstra 初始化

首先已知的是：
給定 鄰接矩陣表示的圖Graph、源點S、終點T。

a、參數(shù)

參數(shù):

參數(shù)名	解釋
S	記錄當(dāng)前已經(jīng)處理過的源點到最短節(jié)點
U	記錄還未處理的節(jié)點
dist[]	記錄各個節(jié)點到起始節(jié)點的最短權(quán)值
path[]	記錄各個節(jié)點的上一級節(jié)點(用來聯(lián)系該節(jié)點到起始節(jié)點的路徑)

b、初始化參數(shù)

• 頂點集S: 節(jié)點A到自已的最短路徑長度為0。只包含源點，即S={A}，代碼中沒有這個，這里是為了步驟清晰而設(shè)置的。
• 頂點集U: 包含除A外的其他頂點. 即U={B,C,D,E,F,G}
• dist[]: 源點還不能到達(dá)的節(jié)點,其權(quán)值為∞

名	A	B	C	D	E	F	G
dist[]:	0	1	2	3	4	5	6
初始化值:	0	4	6	6	∞	∞	∞

path[]: 記錄當(dāng)前節(jié)點的前驅(qū)節(jié)點下標(biāo)(源點還不能到達(dá)的節(jié)點為-1)

名	A	B	C	D	E	F	G
path[]:	0	1	2	3	4	5	6
初始化值:	0	0	0	0	-1	-1	-1

c、算法步驟

1. 初始化：設(shè)定除源節(jié)點以外的其它所有節(jié)點到源節(jié)點的距離為INFINITE(一個很大的數(shù))，且這些節(jié)點都沒被處理過。如上圖所示
2. 從源節(jié)點出發(fā)，更新相鄰節(jié)點(圖中為B、C、D)到源節(jié)點的距離。然后在所有節(jié)點中選擇一個最段距離的點作為當(dāng)前節(jié)點。
3. 標(biāo)記當(dāng)前節(jié)點為done(表示已經(jīng)被處理過)，與步驟2類似，更新其相鄰節(jié)點的距離。(這些相鄰節(jié)點的距離更新也叫 松弛，目的是讓它們與源節(jié)點的距離最小。因為你是在當(dāng)前最小距離的基礎(chǔ)上進(jìn)行更新的，由于當(dāng)前節(jié)點到源節(jié)點的距離已經(jīng)是最小的了，那么如果這些節(jié)點之前得到的距離比這個距離大的話，我們就更新它)。
4. 步驟3做完以后，設(shè)置這個當(dāng)前節(jié)點已被done，然后尋找下一個具有最小代價(cost)的點，作為新的當(dāng)前節(jié)點，重復(fù)步驟3.
5. 如果最后檢測到目標(biāo)節(jié)點時，其周圍所有的節(jié)點都已被處理，那么目標(biāo)節(jié)點與源節(jié)點的距離就是最小距離了。如果想看這個最小距離所經(jīng)過的路徑，可以回溯，前提是你在步驟3里面加入了當(dāng)前節(jié)點的最優(yōu)路徑前驅(qū)節(jié)點信息。

• 我總結(jié)了下可用如下幾句話代替：
  兩步走
  1. 從dist[]中在集合U中的選擇最小距離加入到S中，作為當(dāng)前節(jié)點。(最小距離：就是 當(dāng)前節(jié)點到源點的最小距離)
  2. 遍歷當(dāng)前節(jié)點的鄰邊節(jié)點：更新dist[]和path[]
     • 如果經(jīng)過當(dāng)前節(jié)點+鄰邊權(quán)重 < 鄰邊節(jié)點，則改變dist[]和path[]，否者不改變。

3、Dijkstra 算法詳細(xì)步驟

a、第一輪算法執(zhí)行

• 如上圖，因為dist[]中排出掉集合U中節(jié)點，最小值是4，也就是節(jié)點B，所以將B納入到集合S中（圈中）。

• 首先 在dist[]數(shù)組中并在集合U中 最小值是節(jié)點B，既當(dāng)前節(jié)點，其鄰邊有C和E，所以看是否要更新C和E。

  • 節(jié)點C：因為C的最小距離dist[1](B的最小距離)4+1(B到C的距離)=5 < dist[2](C的最小距離) = 6，所以 dist[2]=5，path[2]=1
  • 節(jié)點E：因為E的最小距離 dist[1](B的最小距離)4+7(B到E的距離)=11 < dist[4] (E的最小距離)=無窮大，所以 dist[4]=11,path[4]=1

• 第一輪算法兩個鄰邊節(jié)點C、E有改變

b、第二輪算法執(zhí)行

• 如上圖，因為dist[]中排出掉集合U中節(jié)點，最小值是5，也就是節(jié)點C，所以將C納入到集合S中（圈中）。
• 首先在dist[]數(shù)組中并在集合U中 最小值是節(jié)點C，既當(dāng)前節(jié)點，其鄰邊有E和F，所以看是否要更新E和F。
  • 節(jié)點E：因為C的最小距離 dist[2](也就是C的最小距離)5+6(C到E的距離)=11 == dist[4](E的最小距離) = 11，所以不動
  • 節(jié)點F：因為F的最小距離 dist[2](也就是C的最小距離)5+4(C到F的距離)=9 < dist[5] (F的最小距離)=無窮大，所以 dist[5]=9,path[5]=2
• 第二輪算法兩個鄰邊節(jié)點僅有 F有改變

c、第三輪算法執(zhí)行

• 如上圖，因為dist[]中排出掉集合U中節(jié)點，最小值是6，也就是節(jié)點D，所以將D納入到集合S中（圈中）。
• 首先在dist[]數(shù)組中并在集合U中 最小值是節(jié)點D，既當(dāng)前節(jié)點，其鄰邊有C和F，所以看是否要更新C和F。
• 節(jié)點C：因為C的最小距離 dist[3](也就是D的最小距離)6+2(D到C的距離)=8 > dist[2](C的最小距離) = 5 ，所以不動
• 節(jié)點F：因為F的最小距離 dist[3](也就是D的最小距離)6+5(D到F的距離)=11 > dist[5] (F的最小距離)=9，所以不動
• 第三輪算法兩個鄰邊節(jié)點C、F都沒有改變

d、第四輪算法執(zhí)行

• 如上圖，因為dist[]中排出掉集合U中節(jié)點，最小值是9，也就是節(jié)點F，所以將F納入到集合S中（圈中）。
• 首先在dist[]數(shù)組中并在集合U中 最小值是節(jié)點F，既當(dāng)前節(jié)點，其鄰邊有E和G，所以看是否要更新E和G 。
• 節(jié)點E：因為E的最小距離 dist[5](也就是F的最小距離) 9 +1(F到E的距離)=10 < dist[4](E的最小距離) =11，所以 dist[4] = 10,path[4]=5
• 節(jié)點G：因為G的最小距離 dist[5](也就是F的最小距離) 9 +8(F到G的距離)=17 < dist[6](G的最小距離) =無窮大，所以 dist[6]=17,path[6]=5
• 第四輪算法兩個鄰邊節(jié)點E、G都有改變

e、第五輪算法執(zhí)行

• 如上圖，因為dist[]中排出掉集合U中節(jié)點，最小值是9，也就是節(jié)點F，所以將F納入到集合S中（圈中）。
• 首先在dist[]數(shù)組中并在集合U中 最小值是節(jié)點E，既當(dāng)前節(jié)點，其鄰邊有G，所以看是否要更新G 。
• 節(jié)點G：因為G的最小距離 dist[4](也就是E的最小距離) 10 +6(E到G的距離)=16 < dist[6](G的最小距離) =17，所以 dist[6]=16,path[6]=4
• 第五輪算法鄰邊 節(jié)點G有改變

f、第六輪算法執(zhí)行

• 如上圖，因為dist[]中排出掉集合U中節(jié)點，最小值是16，也就是節(jié)點G，所以將G納入到集合S中（圈中）。
• 首先在dist[]數(shù)組中并在集合U中 最小值是節(jié)點G，既當(dāng)前節(jié)點，其沒有鄰邊。
• 第六輪算法鄰邊節(jié)點G沒有改變
• 到此算法遍歷結(jié)束

4、java算法實現(xiàn)

給定矩陣表示的Graph結(jié)構(gòu)。輸入源點v0和終點v1。

二、多源最短路徑

1、多源最短路徑問題

• 上面的Dijkstra 解決的是單源最短路徑的問題，首先要給定 開始節(jié)點和終止結(jié)點，如果換了開始和終止節(jié)點，那就要每次都要重新跑一次。
• 那就引出了多源最短路徑問題：就是執(zhí)行一次算法，求出每兩個點之間的最短距離，這就是多源最短路徑算法。這個算法代碼略簡單一些。
• 思想只有一個：要算兩個點之間的最短距離，就看有沒有第三個點使得

2、Floyd初始化

首先已知的是：
給定 **鄰接矩陣表示的圖Graph。

a、參數(shù)

參數(shù)名	解釋
A[][]	函數(shù)中的參數(shù)，需要返回，存儲的是節(jié)點的前置節(jié)點。
path[][]	存儲的是每兩點之間的所需距離。

b、參數(shù)初始化

參數(shù)名	解釋
A[][]	就是圖的賦值，從代碼中可以看出，比較簡單
path[][]	默認(rèn)都是-1.表示從A點到B點是直達(dá)的。

c、算法步驟

1. 對于每個頂點v（體現(xiàn)在代碼的第一層for循環(huán)），和任意一頂點（i,j）(體現(xiàn)代碼的第二、三層循環(huán)),切 i!=j、v!=i、v!=j。
2. 如果A[i][j] > A[i][v] + A[]v[j]，則將A[i][j] 更新為 A[i][v] + A[v][j] 的值，并且將path[i][j]改為v。

3、Floyd算法詳細(xì)步驟

4、java 算法實現(xiàn)

package com.feng.algorithm.self_learn.floyd.floyd1;/*** 學(xué)習(xí)視頻：https://www.bilibili.com/video/BV1LE411R7CS*/
public class FloydAlgorithm {public static void main(String[] args) {int[][] graph = new int[4][4];int N = Short.MAX_VALUE;graph[0] = new int[]{0, 5, N, 7};graph[1] = new int[]{N, 0, 4, 2};graph[2] = new int[]{3, 3, 0, 2};graph[3] = new int[]{N, N, 1, 0};int[][] path = new int[4][4];int[][] A = Floyd.floyd(graph, path);int u = 1;int v = 0;Floyd.printPath(u, v, path);System.out.println();System.out.println(u + "->" + v +" shortest path is :" + A[u][v]);}
}
class Floyd {/*** 佛洛依德算法，給定鄰接矩陣表示的圖，* path[][]:存放路徑中間的節(jié)點，如果是-1就是直達(dá)* A[][]:存放任意兩個節(jié)點之間的距離* 舉例：從1-0，從A得出距離是6，從path得出 1-3-2-0* @param graph* @param path*/static int[][] floyd(int[][] graph, int[][] path) {int n = graph.length;int v, i, j;int[][] A = new int[n][n];for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {A[i][j] = graph[i][j];path[i][j] = -1;}}for (v = 0; v < n; v++) {for (i = 0; i < n; i++) {for (j = 0; j < n; j++) {if (A[i][j] > A[i][v] + A[v][j]) {A[i][j] = A[i][v] + A[v][j];path[i][j] = v;}}}}return A;}/*** 遞歸打印路徑* @param u* @param v* @param path*/static void printPath(int u, int v, int[][] path) {if (path[u][v] == -1) { // 如果等于 -1 。說明就是直達(dá)的System.out.printf(u + "->" + v + " ");} else {int mid = path[u][v];printPath(u, mid, path);printPath(mid, v, path);}}
}