第十一章：图论part09
今天的建议依然是，一刷的时候，能了解 原理，照着代码随想录能抄下来代码就好，就算达标。
二刷的时候自己尝试独立去写，三刷的时候 才能有一定深度理解各个最短路算法。
dijkstra（堆优化版）精讲
思路
在之前的Dijkstra算法中，我们通过遍历所有节点来寻找未访问的最近节点。这种方法在稠密图（即边的数量很多）中表现良好，但在稀疏图（边的数量较少）中，效率较低。因此，我们可以通过使用堆（优先队列）和邻接表来优化Dijkstra算法，使其更适用于稀疏图。
一、图的存储方式
图的存储方式主要有两种：邻接矩阵和邻接表。这两种存储方式各有优缺点，适用于不同的场景。
邻接矩阵（Adjacency Matrix）:
结构: 使用二维数组来表示图。矩阵中的元素grid[i][j]表示节点i到节点j的边的权重。如果grid[i][j]是一个很大的值（如Integer.MAX_VALUE），表示节点i和节点j之间没有直接连接的边。
优点: 检查任意两个节点之间是否存在边非常快速，适合稠密图（边数接近顶点数平方的图）。
缺点: 对于稀疏图（边数远小于顶点数平方的图），会导致大量空间浪费。此外，在遍历邻接节点时效率较低，因为需要遍历整个矩阵。邻接表（Adjacency List）:
结构: 使用数组加链表（或数组加动态数组）的方式来表示图。每个节点对应一个链表，链表中的元素表示与该节点相邻的其他节点及其边的权重。
优点: 对于稀疏图，邻接表只存储实际存在的边，节省空间。在遍历邻接节点时，效率较高。
缺点: 检查任意两个节点之间是否存在边的效率相对较低。
二、算法实现
import java.util.*;
class Edge {
int to; // 邻接顶点
int val; // 边的权重
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(); // 节点数量
int m = scanner.nextInt(); // 边的数量
// 构建邻接表
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)); // 记录边的权重
}
// Dijkstra算法的堆优化实现
int start = 1; // 起始节点
int[] minDist = new int[n + 1]; // 存储从源点到每个节点的最短距离
boolean[] visited = new boolean[n + 1]; // 记录节点是否已被访问过
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0;
// 使用优先队列（小顶堆）来优化
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; // 如果该节点已被访问，跳过
visited[curNode] = true; // 标记该节点已被访问
// 遍历该节点的邻接边
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]}); // 将新节点及其距离加入堆中
}
}
}
// 输出结果
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]);
}
}
}
}
三、算法的步骤
无论是朴素版还是堆优化版，Dijkstra算法的基本步骤是相同的：
初始化：
将所有节点的最短距离初始化为无穷大（Integer.MAX_VALUE），将源点的最短距离初始化为0。选取未访问的最短距离节点：
朴素版通过遍历所有节点找到距离源点最近的未访问节点。
堆优化版通过小顶堆直接获取距离源点最近的未访问节点。标记该节点为已访问。
更新其邻接节点的最短距离：
对于该节点的每一个邻接节点，如果从源点经过该节点到达邻接节点的距离更短，则更新该邻接节点的最短距离。重复步骤2-4，直到所有节点都被访问或所有剩余节点不可达。
Bellman_ford 算法精讲
思路
- 本题不同之处在于 边的权值是有负数了。
- Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。
松弛（Relaxation）是什么？
松弛是图算法中的一个关键概念，尤其在求解最短路径问题时，松弛操作被广泛使用。简单来说，松弛是通过检查并更新当前路径，使得路径更短、更优的过程。
松弛操作的核心思想：
-
起点：每条边都有一个起点（
A）和一个终点（B），以及一个边的权值（value）。 -
当前最短路径：
minDist[B]表示当前已知的从源点到终点B的最短路径。 -
松弛操作：通过检查从源点到达终点
B的另一种路径，即先到达A，再通过边A -> B到达B，是否比当前路径minDist[B]更短。如果更短，则更新minDist[B]。
公式表达：
if (minDist[B] > minDist[A] + value) {
minDist[B] = minDist[A] + value;
}
这个过程就是所谓的“松弛”。如果通过A到达B的路径更短，我们就“放松”当前路径，使得minDist[B]变得更小。
为什么需要进行n-1次松弛？
在Bellman-Ford算法中，松弛操作是核心步骤。为了确保找到从源点到所有其他节点的最短路径，需要对所有边进行n-1次松弛，原因如下：
图的最大路径长度：在一个包含
n个节点的图中，任意两点之间的最短路径最多经过n-1条边。这是因为如果一个路径包含更多的边，必然会经过某些节点多次，意味着存在环。逐步扩展最短路径：每次松弛都会将当前节点的最短路径信息传播给它的邻接节点。第
k次松弛后，所有经过最多k条边的最短路径都会被正确计算出来。因此，经过n-1次松弛操作，最短路径必然会被完全计算出来。模拟过程参见文章
代码实现
import java.util.*;
public class BellmanFord {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 节点数量
int m = scanner.nextInt(); // 边的数量
List<int[]> edges = new ArrayList<>();
// 将所有边保存起来
for (int i = 0; i < m; i++) {
int p1 = scanner.nextInt(); // 边的起点
int p2 = scanner.nextInt(); // 边的终点
int val = scanner.nextInt(); // 边的权值
edges.add(new int[]{p1, p2, val});
}
int start = 1; // 起点
int end = n; // 终点
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE); // 初始化最短距离数组
minDist[start] = 0;
// 对所有边松弛 n-1 次
for (int i = 1; i < n; i++) {
for (int[] edge : edges) { // 每一次松弛，都是对所有边进行松弛
int from = edge[0]; // 边的出发点
int to = edge[1]; // 边的到达点
int price = edge[2]; // 边的权值
// 松弛操作
// minDist[from] != Integer.MAX_VALUE 防止从未计算过的节点出发
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"); // 不能到达终点
} else {
System.out.println(minDist[end]); // 到达终点的最短路径
}
}
}
