第十一章：圖論part09
今天的建議依然是赫舒，一刷的時(shí)候悍及，能了解 原理，照著代碼隨想錄能抄下來代碼就好号阿，就算達(dá)標(biāo)并鸵。
二刷的時(shí)候自己嘗試獨(dú)立去寫，三刷的時(shí)候 才能有一定深度理解各個(gè)最短路算法扔涧。
dijkstra（堆優(yōu)化版）精講
思路
在之前的Dijkstra算法中园担，我們通過遍歷所有節(jié)點(diǎn)來尋找未訪問的最近節(jié)點(diǎn)。這種方法在稠密圖（即邊的數(shù)量很多）中表現(xiàn)良好枯夜，但在稀疏圖（邊的數(shù)量較少）中弯汰，效率較低。因此湖雹，我們可以通過使用堆（優(yōu)先隊(duì)列）和鄰接表來優(yōu)化Dijkstra算法咏闪，使其更適用于稀疏圖。
一摔吏、圖的存儲(chǔ)方式
圖的存儲(chǔ)方式主要有兩種：鄰接矩陣和鄰接表鸽嫂。這兩種存儲(chǔ)方式各有優(yōu)缺點(diǎn)，適用于不同的場(chǎng)景征讲。
鄰接矩陣（Adjacency Matrix）:
結(jié)構(gòu): 使用二維數(shù)組來表示圖据某。矩陣中的元素grid[i][j]表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的邊的權(quán)重。如果grid[i][j]是一個(gè)很大的值（如Integer.MAX_VALUE）诗箍，表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間沒有直接連接的邊癣籽。
優(yōu)點(diǎn): 檢查任意兩個(gè)節(jié)點(diǎn)之間是否存在邊非常快速滤祖，適合稠密圖（邊數(shù)接近頂點(diǎn)數(shù)平方的圖）筷狼。
缺點(diǎn): 對(duì)于稀疏圖（邊數(shù)遠(yuǎn)小于頂點(diǎn)數(shù)平方的圖），會(huì)導(dǎo)致大量空間浪費(fèi)匠童。此外埂材，在遍歷鄰接節(jié)點(diǎn)時(shí)效率較低，因?yàn)樾枰闅v整個(gè)矩陣俏让。鄰接表（Adjacency List）:
結(jié)構(gòu): 使用數(shù)組加鏈表（或數(shù)組加動(dòng)態(tài)數(shù)組）的方式來表示圖楞遏。每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表茬暇，鏈表中的元素表示與該節(jié)點(diǎn)相鄰的其他節(jié)點(diǎn)及其邊的權(quán)重。
優(yōu)點(diǎn): 對(duì)于稀疏圖寡喝，鄰接表只存儲(chǔ)實(shí)際存在的邊糙俗，節(jié)省空間。在遍歷鄰接節(jié)點(diǎn)時(shí)预鬓，效率較高巧骚。
缺點(diǎn): 檢查任意兩個(gè)節(jié)點(diǎn)之間是否存在邊的效率相對(duì)較低。
二格二、算法實(shí)現(xiàn)
import java.util.*;
class Edge {
int to; // 鄰接頂點(diǎn)
int val; // 邊的權(quán)重
public Edge(int to, int val) {
this.to = to;
this.val = val;
}
}
class DijkstraWithHeap {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 節(jié)點(diǎn)數(shù)量
int m = scanner.nextInt(); // 邊的數(shù)量
// 構(gòu)建鄰接表
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>()); // 初始化鄰接表
}
// 讀取邊的信息
for (int i = 0; i < m; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
int w = scanner.nextInt();
graph.get(u).add(new Edge(v, w)); // 記錄邊的權(quán)重
}
// Dijkstra算法的堆優(yōu)化實(shí)現(xiàn)
int start = 1; // 起始節(jié)點(diǎn)
int[] minDist = new int[n + 1]; // 存儲(chǔ)從源點(diǎn)到每個(gè)節(jié)點(diǎn)的最短距離
boolean[] visited = new boolean[n + 1]; // 記錄節(jié)點(diǎn)是否已被訪問過
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0;
// 使用優(yōu)先隊(duì)列（小頂堆）來優(yōu)化
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(pair -> pair[1]));
pq.add(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int curNode = cur[0];
int curDist = cur[1];
if (visited[curNode]) continue; // 如果該節(jié)點(diǎn)已被訪問劈彪，跳過
visited[curNode] = true; // 標(biāo)記該節(jié)點(diǎn)已被訪問
// 遍歷該節(jié)點(diǎn)的鄰接邊
for (Edge edge : graph.get(curNode)) {
int nextNode = edge.to;
int weight = edge.val;
if (!visited[nextNode] && curDist + weight < minDist[nextNode]) {
minDist[nextNode] = curDist + weight; // 更新最短路徑
pq.add(new int[]{nextNode, minDist[nextNode]}); // 將新節(jié)點(diǎn)及其距離加入堆中
}
}
}
// 輸出結(jié)果
for (int i = 1; i <= n; i++) {
if (minDist[i] == Integer.MAX_VALUE) {
System.out.println("Node " + i + " is unreachable from the source.");
} else {
System.out.println("Shortest distance to node " + i + ": " + minDist[i]);
}
}
}
}
三、算法的步驟
無論是樸素版還是堆優(yōu)化版顶猜，Dijkstra算法的基本步驟是相同的：
初始化：
將所有節(jié)點(diǎn)的最短距離初始化為無窮大（Integer.MAX_VALUE）沧奴，將源點(diǎn)的最短距離初始化為0。選取未訪問的最短距離節(jié)點(diǎn)：
樸素版通過遍歷所有節(jié)點(diǎn)找到距離源點(diǎn)最近的未訪問節(jié)點(diǎn)长窄。
堆優(yōu)化版通過小頂堆直接獲取距離源點(diǎn)最近的未訪問節(jié)點(diǎn)滔吠。標(biāo)記該節(jié)點(diǎn)為已訪問。
更新其鄰接節(jié)點(diǎn)的最短距離：
對(duì)于該節(jié)點(diǎn)的每一個(gè)鄰接節(jié)點(diǎn)挠日，如果從源點(diǎn)經(jīng)過該節(jié)點(diǎn)到達(dá)鄰接節(jié)點(diǎn)的距離更短疮绷，則更新該鄰接節(jié)點(diǎn)的最短距離。重復(fù)步驟2-4嚣潜，直到所有節(jié)點(diǎn)都被訪問或所有剩余節(jié)點(diǎn)不可達(dá)冬骚。
Bellman_ford 算法精講
思路
- 本題不同之處在于 邊的權(quán)值是有負(fù)數(shù)了。
- Bellman_ford算法的核心思想是 對(duì)所有邊進(jìn)行松弛n-1次操作（n為節(jié)點(diǎn)數(shù)量）懂算，從而求得目標(biāo)最短路只冻。
松弛（Relaxation）是什么？
松弛是圖算法中的一個(gè)關(guān)鍵概念计技，尤其在求解最短路徑問題時(shí)属愤，松弛操作被廣泛使用。簡(jiǎn)單來說酸役，松弛是通過檢查并更新當(dāng)前路徑，使得路徑更短驾胆、更優(yōu)的過程涣澡。
松弛操作的核心思想：
-
起點(diǎn)：每條邊都有一個(gè)起點(diǎn)（
A）和一個(gè)終點(diǎn)（B），以及一個(gè)邊的權(quán)值（value）丧诺。 -
當(dāng)前最短路徑：
minDist[B]表示當(dāng)前已知的從源點(diǎn)到終點(diǎn)B的最短路徑入桂。 -
松弛操作：通過檢查從源點(diǎn)到達(dá)終點(diǎn)
B的另一種路徑，即先到達(dá)A驳阎，再通過邊A -> B到達(dá)B抗愁，是否比當(dāng)前路徑minDist[B]更短馁蒂。如果更短，則更新minDist[B]蜘腌。
公式表達(dá)：
if (minDist[B] > minDist[A] + value) {
minDist[B] = minDist[A] + value;
}
這個(gè)過程就是所謂的“松弛”沫屡。如果通過A到達(dá)B的路徑更短，我們就“放松”當(dāng)前路徑撮珠，使得minDist[B]變得更小沮脖。
為什么需要進(jìn)行n-1次松弛？
在Bellman-Ford算法中芯急，松弛操作是核心步驟勺届。為了確保找到從源點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑，需要對(duì)所有邊進(jìn)行n-1次松弛娶耍，原因如下：
圖的最大路徑長(zhǎng)度：在一個(gè)包含
n個(gè)節(jié)點(diǎn)的圖中免姿，任意兩點(diǎn)之間的最短路徑最多經(jīng)過n-1條邊。這是因?yàn)槿绻粋€(gè)路徑包含更多的邊榕酒，必然會(huì)經(jīng)過某些節(jié)點(diǎn)多次胚膊，意味著存在環(huán)。逐步擴(kuò)展最短路徑：每次松弛都會(huì)將當(dāng)前節(jié)點(diǎn)的最短路徑信息傳播給它的鄰接節(jié)點(diǎn)奈应。第
k次松弛后澜掩，所有經(jīng)過最多k條邊的最短路徑都會(huì)被正確計(jì)算出來。因此杖挣，經(jīng)過n-1次松弛操作肩榕，最短路徑必然會(huì)被完全計(jì)算出來。模擬過程參見文章
代碼實(shí)現(xiàn)
import java.util.*;
public class BellmanFord {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 節(jié)點(diǎn)數(shù)量
int m = scanner.nextInt(); // 邊的數(shù)量
List<int[]> edges = new ArrayList<>();
// 將所有邊保存起來
for (int i = 0; i < m; i++) {
int p1 = scanner.nextInt(); // 邊的起點(diǎn)
int p2 = scanner.nextInt(); // 邊的終點(diǎn)
int val = scanner.nextInt(); // 邊的權(quán)值
edges.add(new int[]{p1, p2, val});
}
int start = 1; // 起點(diǎn)
int end = n; // 終點(diǎn)
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE); // 初始化最短距離數(shù)組
minDist[start] = 0;
// 對(duì)所有邊松弛 n-1 次
for (int i = 1; i < n; i++) {
for (int[] edge : edges) { // 每一次松弛惩妇，都是對(duì)所有邊進(jìn)行松弛
int from = edge[0]; // 邊的出發(fā)點(diǎn)
int to = edge[1]; // 邊的到達(dá)點(diǎn)
int price = edge[2]; // 邊的權(quán)值
// 松弛操作
// minDist[from] != Integer.MAX_VALUE 防止從未計(jì)算過的節(jié)點(diǎn)出發(fā)
if (minDist[from] != Integer.MAX_VALUE && minDist[to] > minDist[from] + price) {
minDist[to] = minDist[from] + price;
}
}
}
if (minDist[end] == Integer.MAX_VALUE) {
System.out.println("unconnected"); // 不能到達(dá)終點(diǎn)
} else {
System.out.println(minDist[end]); // 到達(dá)終點(diǎn)的最短路徑
}
}
}
