求最短路算法總覽
關(guān)于最短路可見：https://oi-wiki.org/graph/shortest-path/
無向圖 是一種 特殊的 有向圖。（所以上面的知識地圖上沒有區(qū)分邊有向還是無向）
關(guān)于存儲：稠密圖用鄰接矩陣，稀疏圖用鄰接表。
樸素Dijkstra 和 堆優(yōu)化Dijkstra算法的 選擇就在于圖 是 稠密的還是稀疏的。
Dijkstra
樸素 Dijkstra 算法（?原理講解！?重要！）（用于稠密圖）
算法步驟：
有一個集合 s 存儲當(dāng)前已經(jīng)確定是最短距離的點。
- 初始化距離，dis[1] = 0, dis[i] = +∞
- for i: 1 ~ n 。 (每次循環(huán)確定一個點到起點的最短距離，這樣 n 次循環(huán)就可以確定 n 個點的最短距離)
找到不在 s 中的 距離最近的點 t，將其放入 s 中。
用 t 來更新其它所有點的距離（檢查所有從 t 出發(fā)可以到達的點 x，是否有 dis[x] > dis[t] + w）
例題：849. Dijkstra求最短路 I
https://www.acwing.com/activity/content/problem/content/918/
注意圖是有向圖，圖中可能存在重邊和自環(huán)，所有邊權(quán)為正值。
求從 1 號點到 n 號點 的最短距離。
按照樸素 Dijkstra 算法的原理，每次用當(dāng)前不在 s 中的最短距離節(jié)點 t 更新其它所有 t 可以到達的下一個節(jié)點，重復(fù)這個過程 n 次就可以確定 n 個節(jié)點的最短距離。
代碼1——使用鄰接表
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
// 建圖
List<int[]>[] g = new ArrayList[n + 1];
Arrays.setAll(g, e -> new ArrayList<>());
for (int i = 0; i < m; ++i) {
int x = scanner.nextInt(), y = scanner.nextInt(), z = scanner.nextInt();
g[x].add(new int[]{y, z});
}
// 初始化距離
int[] dis = new int[n + 1];
Arrays.fill(dis, Integer.MAX_VALUE);
dis[1] = 0;
boolean[] st = new boolean[n + 1];
for (int i = 1; i < n; ++i) {
int t = -1;
// 找到當(dāng)前不在 s 中的最短距離 t 的位置
for (int j = 1; j <= n; ++j) {
if (!st[j] && (t == -1 || dis[j] < dis[t])) t = j;
}
if (t == n) break; // 當(dāng)前離得最近的就是 n 了，直接返回
st[t] = true;
// 使用 t 更新所有從 t 出發(fā)可以達到的下一個節(jié)點
for (int[] y: g[t]) dis[y[0]] = Math.min(dis[y[0]], dis[t] + y[1]);
}
if (dis[n] == Integer.MAX_VALUE) System.out.println("-1");
else System.out.println(dis[n]);
}
}
代碼2——使用鄰接矩陣
從題目中可以看出是稠密圖，所以使用鄰接矩陣效率會更高一些。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
// 建圖 g[i][j]表示從i到j(luò)的距離
int[][] g = new int[n + 1][n + 1];
for (int[] ints : g) Arrays.fill(ints, 0x3f3f3f3f);
for (int i = 0; i < m; ++i) {
int x = scanner.nextInt(), y = scanner.nextInt(), z = scanner.nextInt();
g[x][y] = Math.min(g[x][y], z);
}
// 初始化各個點到起始點的距離
int[] dis = new int[n + 1];
Arrays.fill(dis, Integer.MAX_VALUE);
dis[1] = 0;
boolean[] st = new boolean[n + 1];
for (int i = 1; i < n; ++i) {
int t = -1;
// 找到當(dāng)前不在 s 中的最短距離 t 的位置
for (int j = 1; j <= n; ++j) {
if (!st[j] && (t == -1 || dis[j] < dis[t])) t = j;
}
if (t == n) break; // 當(dāng)前離得最近的就是 n 了，直接返回
st[t] = true;
// 使用 t 更新所有從 t 出發(fā)可以達到的下一個節(jié)點
for (int j = 1; j <= n; ++j) {
dis[j] = Math.min(dis[j], dis[t] + g[t][j]);
}
}
if (dis[n] == 0x3f3f3f3f) System.out.println("-1");
else System.out.println(dis[n]);
}
}
補充：稠密圖和稀疏圖 & 鄰接矩陣和鄰接表
總結(jié)一下：
鄰接矩陣的空間復(fù)雜度為 O ( n 2 ) O(n^2) O(n2)，鄰接表的空間復(fù)雜度為 O ( n + m ) O(n + m) O(n+m)，其中 n 是圖中節(jié)點的數(shù)量，m 是邊的數(shù)量。
Q：如何判斷什么時候是稠密的？
A：當(dāng)
m
m
m 接近最大可能邊數(shù)
n
?
(
n
?
1
)
/
2
n * (n - 1)/2
n?(n?1)/2 時，那么圖通常被視為稠密的。
堆優(yōu)化版Dijkstra算法（?原理講解！?重要?。┯糜谙∈鑸D
如果是一個稀疏圖，
O
(
n
2
)
O(n^2)
O(n2) 的樸素 Dijkstra 算法可能會很慢，因此出現(xiàn)了堆優(yōu)化版本的 Dijkstra 算法。
用堆來存儲所有點到起點的最短距離，就可以減小整個算法的時間復(fù)雜度。
用 t 更新其它點的距離，因為有 m 條邊，所以這個操作是 m 次，每次的時間復(fù)雜度是 logn，因此一共是 m ? log ? n m*\log{n} m?logn。 （所以 m 比較小時，即稀疏圖，使用堆優(yōu)化效果更好）
其實就是用堆來優(yōu)化了每次找當(dāng)前和起始點最近的點的過程。（樸素的需要枚舉 n）
例題：850. Dijkstra求最短路 II
https://www.acwing.com/activity/content/problem/content/919/
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
// 建圖
List<int[]>[] g = new ArrayList[n + 1];
Arrays.setAll(g, e -> new ArrayList<int[]>());
for (int i = 0; i < m; ++i) {
int x = scanner.nextInt(), y = scanner.nextInt(), z = scanner.nextInt();
g[x].add(new int[]{y, z});
}
//
int[] dis = new int[n + 1];
Arrays.fill(dis, 0x3f3f3f3f);
dis[1] = 0;
boolean[] st = new boolean[n + 1];
// 按照各個節(jié)點與初始節(jié)點之間距離 從小到大 排序
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
pq.offer(new int[]{1, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int x = cur[0], d = cur[1];
if (st[x]) continue; // 檢查這個節(jié)點是否已經(jīng)用來更新過了
st[x] = true;
// 只要被當(dāng)前節(jié)點更新了就放入優(yōu)先隊列中
for (int[] y: g[x]) { // 這個循環(huán)最多被執(zhí)行 m 次（因為有 m 條邊）
if (dis[y[0]] > d + y[1]) {
dis[y[0]] = d + y[1];
pq.offer(new int[]{y[0], dis[y[0]]});
}
}
}
System.out.println(dis[n] == 0x3f3f3f3f? -1: dis[n]);;
}
}
bellman-ford
枚舉 n 次：
每次 循環(huán)所有邊 a, b, w
dis[b] = min(dis[b], dis[a] + w)
循環(huán)完之后， 所有節(jié)點會滿足 dis[b] <= dis[a] + w。
對于 n 次循環(huán)中的第 k 次循環(huán)，求出的是 ： 從 起點走 不超過 k 條邊 的最短距離。
因此 如果第 n 次循環(huán)時有更新，說明圖中存在負環(huán)。
例題：853. 有邊數(shù)限制的最短路
https://www.acwing.com/problem/content/description/855/
注意！ ： 如果有負權(quán)回路，那么最短路就一定不存在了！
bellman-ford 算法可以判斷出 圖中是否存在負權(quán)回路。（但是一般使用 spfa 來判斷是否有負環(huán)）
Q：這道題為什么必須使用 bellman-ford 算法？
A：因為限制了最多經(jīng)過 k 條邊，即存在邊數(shù)限制。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt(), k = scanner.nextInt();
// 存儲所有邊
int[][] edges = new int[m][3];
for (int i = 0; i < m; ++i) {
edges[i][0] = scanner.nextInt();
edges[i][1] = scanner.nextInt();
edges[i][2] = scanner.nextInt();
}
int[] dis = new int[n + 1], last;
Arrays.fill(dis, 0x3f3f3f3f);
dis[1] = 0;
// 限制 k 次。 （k 次就表示最多經(jīng)過 k 條邊）
for (int i = 0; i < k; ++i) {
last = Arrays.copyOf(dis, n + 1); // 將dis數(shù)組先備份一下
for (int j = 0; j < m; ++j) { // 枚舉所有邊
dis[edges[j][1]] = Math.min(dis[edges[j][1]], last[edges[j][0]] + edges[j][2]);
}
}
// 因為存在負權(quán)邊，而本題的數(shù)據(jù)范圍最多減 500 * 10000。所以和 0x3f3f3f3f/2 比較大小
System.out.println(dis[n] > 0x3f3f3f3f / 2? "impossible": dis[n]);
}
}
為什么需要對 dis 數(shù)組進行備份？
因為如果不備份的話可能會發(fā)生串聯(lián)，為了避免串聯(lián)，每次更新時只用上一次的結(jié)果。
比如上圖，在第一次循環(huán)中 2 的 dis 被更新成了 1，如果不使用備份的話，那么 3 的 dis 會被接著更新為 2，但這并不是我們所期望的， 3 的 dis 被更新成 2 應(yīng)該是在第 2 次循環(huán)時才會發(fā)生的事情。
spfa算法（bellman-ford 算法的優(yōu)化）
相當(dāng)于對 bellman-ford 算法做了一個優(yōu)化。
bellman-ford 在每次循環(huán)中枚舉了所有邊，但實際上有些邊并不會對松弛有作用，所以 spfa 就是從這一點進行了優(yōu)化。
（使用隊列寬搜進行優(yōu)化）。
從公式 d i s [ b ] = m i n ( d i s [ b ] , d i s [ a ] + w ) dis[b] = min(dis[b], dis[a] + w) dis[b]=min(dis[b],dis[a]+w) 可以看出，只有當(dāng) d i s [ a ] dis[a] dis[a] 變小了，這條邊才有可能讓 d i s [ b ] dis[b] dis[b] 跟著變小。
算法步驟：
基本思想：只有我變小了，我后面的人才會跟著變小。
隊列里面存的是待更新的點，就是等著用來更新其它點的點。
例題：851. spfa求最短路
https://www.acwing.com/activity/content/problem/content/920/
這一題的數(shù)據(jù)保證了圖中不存在負環(huán)。
代碼中不再是 n 次循環(huán)嵌套 m 次循環(huán)的 bellman-ford 算法了，
而是一個隊列維護可以用來更新其它節(jié)點的節(jié)點隊列，初始時放入起始節(jié)點 1，其余時間每次取出隊首的節(jié)點即可。
取出一個節(jié)點后，枚舉它影響的所有其它節(jié)點即可，如果其它節(jié)點被影響了，就表示可以把這個被影響的節(jié)點放入隊列中，（不過放進隊列之前要先判斷一下是否已經(jīng)在隊列中了，防止重復(fù)更新）。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
// 使用鄰接表存儲
List<int[]>[] g = new ArrayList[n + 1];
Arrays.setAll(g, e -> new ArrayList<int[]>());
for (int i = 0; i < m; ++i) {
g[scanner.nextInt()].add(new int[]{scanner.nextInt(), scanner.nextInt()});
}
// 初始化距離、隊列、是否在隊列里的狀態(tài)
int[] dis = new int[n + 1];
Arrays.fill(dis, 0x3f3f3f3f);
dis[1] = 0;
Queue<Integer> q = new LinkedList<Integer>();
q.offer(1);
boolean[] st = new boolean[n + 1];
st[1] = true;
while (!q.isEmpty()) {
int t = q.poll();
st[t] = false;
for (int[] y: g[t]) {
int j = y[0], w = y[1];
if (dis[j] > dis[t] + w) {
dis[j] = dis[t] + w;
// 由于 j 變小了，所以它可以被更新，可以放入隊列中
// 但是放進去之前要先判斷已經(jīng)是否已經(jīng)在隊列中了，防止重復(fù)放置
if (!st[j]) {
q.offer(j);
st[j] = true;
}
}
}
}
System.out.println(dis[n] == 0x3f3f3f3f? "impossible": dis[n]);
}
}
例題：852. spfa判斷負環(huán)
https://www.acwing.com/problem/content/description/854/
跟 bellman-ford 算法判斷負環(huán)的思路差不多，在更新 dis 數(shù)組的同時，維護一個 cnt 數(shù)組，cnt[x] 表示當(dāng)前這個最短路的經(jīng)過的邊數(shù)。
每次更新 dis[x] 的時候，就把 cnt[x] 更新成 cnt[t] + 1。（因為 x 是從節(jié)點 t 更新過來的）。
如果在更新的過程中出現(xiàn)了 cnt[x] >= n，就表示至少經(jīng)過了 n 條邊，即至少經(jīng)過了 n + 1 個點，這肯定是不合理的，說明存在負環(huán)。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
// 使用鄰接表存儲
List<int[]>[] g = new ArrayList[n + 1];
Arrays.setAll(g, e -> new ArrayList<int[]>());
for (int i = 0; i < m; ++i) {
g[scanner.nextInt()].add(new int[]{scanner.nextInt(), scanner.nextInt()});
}
System.out.println(spfa(g, n)? "Yes": "No");
}
static boolean spfa(List<int[]>[] g, int n) {
// 初始化距離、隊列、是否在隊列里的狀態(tài)
int[] dis = new int[n + 1], cnt = new int[n + 1];
Arrays.fill(dis, 0x3f3f3f3f);
dis[1] = 0;
boolean[] st = new boolean[n + 1];
Queue<Integer> q = new LinkedList<Integer>();
// 是判斷是否存在負環(huán)，而不是只判斷從1開始是否存在負環(huán)
for (int i = 1; i <= n; ++i) {
q.offer(i);
st[i] = true;
}
while (!q.isEmpty()) {
int t = q.poll();
st[t] = false;
for (int[] y: g[t]) {
int j = y[0], w = y[1];
if (dis[j] > dis[t] + w) {
dis[j] = dis[t] + w;
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 表示有負環(huán)
// 由于 j 變小了，所以它可以被更新，可以放入隊列中
// 但是放進去之前要先判斷已經(jīng)是否已經(jīng)在隊列中了，防止重復(fù)放置
if (!st[j]) {
q.offer(j);
st[j] = true;
}
}
}
}
return false; // false表示沒有負環(huán)
}
}
Floyd（很暴力的三重循環(huán)）
https://oi-wiki.org/graph/shortest-path/#floyd-%E7%AE%97%E6%B3%95
用于求多源匯最短路?？梢郧笕我鈨蓚€結(jié)點之間的最短路。
使用鄰接矩陣將原圖存儲下來，三重循環(huán)。
d[i][j]
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
// 看看i直接到j(luò)更近還是 經(jīng)過k之后更近
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
原理其實是基于：動態(tài)規(guī)劃
例題：854. Floyd求最短路
https://www.acwing.com/problem/content/856/
題目數(shù)據(jù)保證了不存在負權(quán)回路。文章來源：http://www.zghlxwxcb.cn/news/detail-600846.html
同樣要注意最后各個距離要和 INF / 2 比較而不是和 INF 比較，因為圖中可能存在負權(quán)。文章來源地址http://www.zghlxwxcb.cn/news/detail-600846.html
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt(), t = scanner.nextInt(), INF = (int)1e9;
// 建圖
int[][] g = new int[n + 1][n + 1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == j) g[i][j] = 0;
else g[i][j] = INF;
}
}
for (int i = 0; i < m; ++i) {
int x = scanner.nextInt(), y = scanner.nextInt(), z = scanner.nextInt();
g[x][y] = Math.min(g[x][y], z);
}
// 求多源最短路
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
// 回答詢問
while (t-- != 0) {
int x = scanner.nextInt(), y = scanner.nextInt();
System.out.println(g[x][y] > INF / 2? "impossible": g[x][y]); // 由于有負權(quán)，所以和INF/2比較
}
}
}
到了這里，關(guān)于【算法基礎(chǔ)：搜索與圖論】3.4 求最短路算法（Dijkstra&bellman-ford&spfa&Floyd）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
