好的，我们继续。根据您新图片中的内容，这次我们将深入探讨图论中另一个至关重要的话题：最短路径 (Shortest Path)。

我们将依次详细讲解三种经典的算法：

• Dijkstra (迪杰斯特拉) 算法：用于解决无负权边的单源最短路径问题。

• Bellman-Ford (贝尔曼-福特) 算法：用于解决可包含负权边的单源最短路径问题，并能检测负权环。

• Floyd-Warshall (弗洛伊德) 算法：用于解决所有顶点对之间的最短路径问题（多源最短路径）。

---

1. 前置知识：最短路径问题

在一个带权图中，从一个顶点到另一个顶点的路径可能有多条。最短路径问题就是要找出一条路径，使得这条路径上所有边的权重之和最小。

• 路径权重 (Path Weight)：一条路径上所有边的权重之和。

• 单源最短路径 (Single-Source Shortest Path, SSSP)：计算从一个指定的**源顶点（Source）**到图中所有其他顶点的最短路径。Dijkstra 和 Bellman-Ford 解决的就是这类问题。

• 多源最短路径 (All-Pairs Shortest Path, APSP)：计算图中每一对顶点之间的最短路径。Floyd-Warshall 解决的是这类问题。

• 负权边 (Negative-Weight Edge)：边的权重可以为负数。这在现实中可能代表“收益”或“折扣”。Dijkstra 算法不能处理这种情况，而 Bellman-Ford 和 Floyd-Warshall 可以。

• 负权环 (Negative-Weight Cycle)：一个环路的所有边权重之和为负数。如果图中存在负权环，那么最短路径可能没有意义，因为我们可以无限次地绕着这个环走，每走一圈路径权重就会变得更小，趋近于负无穷。Bellman-Ford 算法可以检测出这种情况。

---

2. Dijkstra (迪杰斯特拉) 算法 (5.1)

Dijkstra 算法是解决无负权边单源最短路径问题的最著名算法。它是一种贪心算法。

算法思想

1. 初始化：

   • 创建一个距离数组 dist[]，dist[i] 表示从源顶点 s 到顶点 i 的当前已知最短距离。初始化 dist[s] = 0，其他所有 dist[i] = ∞ (无穷大)。

   • 创建一个集合 S (或使用一个 visited 数组)，用于存放已经找到最短路径的顶点。初始时 S 为空。

2. 迭代：重复以下步骤 V 次（V 是顶点数）：

   • 从尚未访问的顶点中，选择一个 dist 值最小的顶点 u。

   • 将 u 加入集合 S (标记为已访问)。这表示从源点 s 到 u 的最短路径已经确定为 dist[u]。

   • 松弛 (Relaxation)：对于 u 的每一个邻接顶点 v，检查是否可以通过 u 来缩短到达 v 的路径。即，比较 dist[v] 和 dist[u] + weight(u, v)：

     • 如果 dist[u] + weight(u, v) < dist[v]，则更新 dist[v] = dist[u] + weight(u, v)。

核心数据结构：优先队列 (Min-Heap)

为了在每次迭代中高效地“选择一个 dist 值最小的尚未访问的顶点”，我们使用优先队列。

• 优先队列中存储 (距离, 顶点) 对。

• 每次从队列顶部取出距离最小的顶点，这个操作的时间复杂度是 O(logV)。

Java 代码实现与逐行注释

Java

import java.util.*;

// 用于在优先队列中存储节点信息
class Node implements Comparable<Node> {
    int vertex; // 顶点编号
    int distance; // 从源点到该顶点的距离

    public Node(int vertex, int distance) {
        this.vertex = vertex;
        this.distance = distance;
    }

    // 实现 Comparable 接口，让优先队列能按 distance 排序
    @Override
    public int compareTo(Node other) {
        return this.distance - other.distance; // 按距离升序排列
    }
}

public class DijkstraAlgorithm {
    
    // Dijkstra 算法实现
    // V: 顶点数, adj: 邻接表, src: 源顶点
    public static void dijkstra(int V, List<List<Node>> adj, int src) {
        // dist 数组：存储从源点 src 到各个顶点的最短距离
        int[] dist = new int[V];
        // 初始化所有距离为无穷大
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        // 源点到自身的距离为 0
        dist[src] = 0;

        // 优先队列（最小堆），用于高效地获取当前距离最小的顶点
        // 存储的是 Node 对象，包含顶点和其当前距离
        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 将源点加入优先队列
        pq.add(new Node(src, 0));

        System.out.println("Dijkstra 算法执行过程：");

        // 当优先队列不为空时，说明还有未处理的顶点
        while (!pq.isEmpty()) {
            // 1. 从优先队列中取出距离源点最近的顶点 u
            Node currentNode = pq.poll();
            int u = currentNode.vertex;
            int currentDist = currentNode.distance;

            // 这是一个优化：如果取出的距离比数组中记录的还要大，
            // 说明这个节点信息是“过时”的（我们找到了更短的路径），直接跳过。
            if (currentDist > dist[u]) {
                continue;
            }

            System.out.printf("处理顶点 %d，当前最短距离为 %d\n", u, dist[u]);

            // 2. 遍历 u 的所有邻接顶点 v (松弛操作)
            for (Node neighbor : adj.get(u)) {
                int v = neighbor.vertex;
                int weight = neighbor.distance; // 这里 distance 存储的是边的权重

                // 3. 如果通过 u 到达 v 的距离比已知的 dist[v] 更短
                if (dist[u] + weight < dist[v]) {
                    // 更新到 v 的最短距离
                    dist[v] = dist[u] + weight;
                    // 将更新后的 (v, dist[v]) 加入优先队列
                    pq.add(new Node(v, dist[v]));
                    System.out.printf("  -> 松弛边 (%d, %d)，更新 dist[%d] = %d\n", u, v, v, dist[v]);
                }
            }
        }

        // 打印最终结果
        System.out.println("\n从源点 " + src + " 到各顶点的最短路径：");
        for (int i = 0; i < V; i++) {
            System.out.printf("顶点 %d: %s\n", i, (dist[i] == Integer.MAX_VALUE ? "不可达" : dist[i]));
        }
    }

    public static void main(String[] args) {
        int V = 5; // 顶点数
        int src = 0; // 源点

        // 使用邻接表表示图，List<Node> 表示与该顶点相连的边
        List<List<Node>> adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        // 添加边和权重
        adj.get(0).add(new Node(1, 9));
        adj.get(0).add(new Node(2, 6));
        adj.get(0).add(new Node(3, 5));
        adj.get(0).add(new Node(4, 3));
        
        adj.get(2).add(new Node(1, 2));
        adj.get(2).add(new Node(3, 4));

        dijkstra(V, adj, src);
    }
}

复杂度与扩展

• 时间复杂度：O(ElogV)。E 是边数，V 是顶点数。每个顶点最多入队和出队一次 (O(VlogV))，每条边最多被松弛一次 (O(ElogV))。

• 空间复杂度：O(V+E)。

• 局限性：不能处理带负权边的图。因为 Dijkstra 算法的贪心策略是基于“一旦一个顶点的最短路径被确定，它就不会再被更改”。但如果存在负权边，一条更长的路径（经过更多顶点）的总权重反而可能更小，这会打破 Dijkstra 算法的前提。

• 应用：路由协议（如 OSPF）、地图导航（计算最快或最短路线）、网络数据包转发等。

---

3. Bellman-Ford (贝尔曼-福特) 算法 (5.2)

Bellman-Ford 算法同样解决单源最短路径问题，但它更强大，因为可以处理带负权边的图，并且能够检测负权环。

算法思想

其核心思想是基于动态规划和松弛操作。它认为从源点 s 到任意顶点 t 的最短路径，最多包含 V−1 条边（如果超过，则一定有环）。

1. 初始化：和 Dijkstra 一样，初始化 dist 数组，dist[s] = 0，其他为 ∞。

2. 迭代松弛：重复 V−1 次以下操作：

   • 遍历图中的所有边 (u, v)，并对它们进行松弛操作。

   • if (dist[u] + weight(u, v) < dist[v])，则更新 dist[v] = dist[u] + weight(u, v)。

3. 检测负权环：在完成上述 V−1 轮迭代后，再进行第 V 轮迭代：

   • 再次遍历所有边 (u, v) 进行松弛。

   • 如果在这一轮中，仍然有 dist[v] 的值被更新，则说明图中存在一个从源点可达的负权环。

Java 代码实现与逐行注释

Java

import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;

// 边类，用于 Bellman-Ford 的边列表表示
class Edge {
    int src, dest, weight;
    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
}

public class BellmanFordAlgorithm {

    public static void bellmanFord(int V, List<Edge> edges, int src) {
        // dist 数组：存储从源点 src 到各个顶点的最短距离
        int[] dist = new int[V];
        // 初始化所有距离为无穷大
        Arrays.fill(dist, Integer.MAX_VALUE);
        // 源点到自身的距离为 0
        dist[src] = 0;

        // 步骤 1: 进行 V-1 轮松弛操作
        // 因为最短路径最多包含 V-1 条边
        for (int i = 1; i < V; i++) {
            System.out.println("第 " + i + " 轮松弛:");
            // 遍历图中的每一条边
            for (Edge edge : edges) {
                int u = edge.src;
                int v = edge.dest;
                int weight = edge.weight;
                
                // 如果起点 u 是可达的，并且通过 u 到达 v 的路径更短
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    System.out.printf("  -> 松弛边 (%d, %d)，更新 dist[%d] = %d\n", u, v, v, dist[v]);
                }
            }
        }

        // 步骤 2: 进行第 V 轮，用于检测负权环
        boolean hasNegativeCycle = false;
        System.out.println("\n进行第 " + V + " 轮以检测负权环:");
        for (Edge edge : edges) {
            int u = edge.src;
            int v = edge.dest;
            int weight = edge.weight;
            
            // 如果在第 V 轮仍然可以松弛，说明存在负权环
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                hasNegativeCycle = true;
                System.out.printf("  -> 边 (%d, %d) 仍然可以被松弛，发现负权环！\n", u, v);
                break; // 找到一个即可停止
            }
        }
        
        // 打印最终结果
        if (hasNegativeCycle) {
            System.out.println("\n图中存在从源点可达的负权环，无法计算最短路径。");
        } else {
            System.out.println("\n从源点 " + src + " 到各顶点的最短路径：");
            for (int i = 0; i < V; i++) {
                System.out.printf("顶点 %d: %s\n", i, (dist[i] == Integer.MAX_VALUE ? "不可达" : dist[i]));
            }
        }
    }

    public static void main(String[] args) {
        int V = 5;
        int src = 0;
        List<Edge> edges = new ArrayList<>();

        edges.add(new Edge(0, 1, -1));
        edges.add(new Edge(0, 2, 4));
        edges.add(new Edge(1, 2, 3));
        edges.add(new Edge(1, 3, 2));
        edges.add(new Edge(1, 4, 2));
        edges.add(new Edge(3, 2, 5));
        edges.add(new Edge(3, 1, 1));
        edges.add(new Edge(4, 3, -3));
        
        bellmanFord(V, edges, src);

        // 包含负权环的例子
        System.out.println("\n--- 测试包含负权环的图 ---");
        V = 3;
        src = 0;
        edges.clear();
        edges.add(new Edge(0, 1, 1));
        edges.add(new Edge(1, 2, -1));
        edges.add(new Edge(2, 1, -1)); // 1->2->1 形成负权环
        bellmanFord(V, edges, src);
    }
}

复杂度与扩展

• 时间复杂度：O(V⋅E)。外层循环 V−1 次，内层循环遍历所有 E 条边。

• 空间复杂度：O(V+E)。

• 优点：非常稳健，可以处理负权边，还能检测负权环。

• 应用：在网络路由协议 RIP (Routing Information Protocol) 中有所应用。在金融领域，可用于检测套利机会（这可以模型化为寻找负权环）。

---

4. Floyd-Warshall (弗洛伊德) 算法 (5.3)

Floyd-Warshall 算法解决的是所有顶点对之间的最短路径（APSP）问题。它同样可以处理负权边，但不能处理负权环。

算法思想

这是一个非常优美的动态规划算法。其核心思想是：

• 对于任意一对顶点 (i, j)，它们之间的最短路径，要么是直接连接它们的边 (i, j)，要么是经过了某个中间顶点 k。

• 算法通过一个 k 的循环，逐步允许更多的顶点作为中间点，从而不断优化任意两点 i 和 j 之间的路径。

状态转移方程为：

dist(i,j)=min(dist(i,j),dist(i,k)+dist(k,j))

这个方程的含义是：从 i 到 j 的新最短路径，是“原来的最短路径”和“经过 k 中转的路径”两者中的较小值。

Java 代码实现与逐行注释

Java

import java.util.Arrays;

public class FloydWarshallAlgorithm {
    // 定义无穷大，防止加法溢出
    final static int INF = 99999; 

    public static void floydWarshall(int V, int[][] graph) {
        // dist 矩阵：用于存储任意两点间的最短路径
        // 初始化 dist 矩阵等于输入的邻接矩阵
        int[][] dist = new int[V][V];
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }
        
        // 核心的动态规划过程
        // k 是允许作为中间点的顶点
        for (int k = 0; k < V; k++) {
            System.out.println("允许使用顶点 " + k + " 作为中间点进行更新：");
            // i 是路径的起点
            for (int i = 0; i < V; i++) {
                // j 是路径的终点
                for (int j = 0; j < V; j++) {
                    // 如果从 i 到 k 和从 k 到 j 的路径都存在
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        // 检查通过 k 中转是否能缩短 i 到 j 的距离
                        if (dist[i][k] + dist[k][j] < dist[i][j]) {
                            // 更新 dist[i][j]
                            dist[i][j] = dist[i][k] + dist[k][j];
                            System.out.printf("  -> 更新 dist[%d][%d] = dist[%d][%d] + dist[%d][%d] = %d\n", 
                                i, j, i, k, k, j, dist[i][j]);
                        }
                    }
                }
            }
        }

        // 打印最终的最短路径矩阵
        printSolution(V, dist);

        // 检测负权环：如果一个顶点到其自身的距离为负，则存在负权环
        for (int i = 0; i < V; i++) {
            if (dist[i][i] < 0) {
                System.out.println("\n图中存在负权环！");
                return;
            }
        }
    }

    public static void printSolution(int V, int[][] dist) {
        System.out.println("\n所有顶点对之间的最短路径矩阵：");
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dist[i][j] == INF) {
                    System.out.print("INF ");
                } else {
                    System.out.print(dist[i][j] + "   ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int V = 4;
        // 使用邻接矩阵表示图
        int[][] graph = {
            {0,   5,   INF, 10},
            {INF, 0,   3,   INF},
            {INF, INF, 0,   1},
            {INF, INF, INF, 0}
        };

        floydWarshall(V, graph);
    }
}

复杂度与扩展

• 时间复杂度：O(V3)。由于三层嵌套循环，非常直观。

• 空间复杂度：O(V2)。用于存储距离矩阵。

• 优点：代码简洁，易于实现。对于需要计算所有点对之间最短路径的稠密图来说，效率很高。

• 应用：计算图的传递闭包、寻找图的中心点、交通网络中的路线规划等。

---

总结与对比

算法	问题类型	边权要求	时间复杂度	核心思想
Dijkstra	单源最短路径 (SSSP)	不能有负权边	O(ElogV)	贪心法，每次选择最近的未访问顶点
Bellman-Ford	单源最短路径 (SSSP)	可以有负权边	O(V⋅E)	动态规划，迭代松弛所有边 V−1 次
Floyd-Warshall	多源最短路径 (APSP)	可以有负权边 (但不能有负权环)	O(V3)	动态规划，不断引入中间点优化路径

希望这份详细的讲解能帮助您彻底理解这三种核心的最短路径算法！