第十一章：图论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]); // 到达终点的最短路径
        }
    }
}

代码随想录算法训练营第59天 | 图论part09：dijkstra（堆优化版）精讲、Bellman_ford 算法精讲