目录

1. 什么是赋权最短路径

2. 赋权最短路径中的关键概念

3. Dijkstra 算法的基本思想

4. Dijkstra 算法实现（Java）

---

1. 什么是赋权最短路径

在图论中，最短路径问题是指在图中寻找两点之间路径总权重最小的路径问题。如果图的每条边都带有权值（weight），这种图称为赋权图（Weighted Graph）。

2. 赋权最短路径中的关键概念

在赋权最短路径算法中，常用的几个重要概念包括：

• 顶点（Vertex/Node） 图的基本组成元素，用于表示位置或对象。

• 边（Edge） 顶点之间的连接关系，可能是有向的（Directed）或无向的（Undirected）。

• 权重（Weight） 与每条边相关联的数值，表示从一个顶点到另一个顶点的“代价”，可能是时间、距离、费用等。

• 路径（Path） 由一系列顶点和边构成的通路。

• 路径长度（Path Length） 路径上所有边的权重之和。

• 前驱节点（Predecessor Node） 在最短路径中，到达某个顶点前的上一个顶点，用于回溯构建路径。

• 松弛操作（Relaxation） 如果通过某条边能找到更短的路径，则更新目标顶点的最短距离和前驱节点的过程。

3. Dijkstra 算法的基本思想

Dijkstra 算法由 Edsger W. Dijkstra 在 1956 年提出，是解决单源非负权重最短路径问题的经典算法。 其核心思想是：

1. 初始化

   • 将源点的最短距离设置为 0，其他顶点设置为无穷大（Integer.MAX_VALUE）。

   • 使用一个优先队列按当前已知的最短距离排序。

2. 迭代选择最近的未处理顶点

   • 从优先队列中取出当前距离最小的顶点 u。

   • 将其标记为“已处理”，不再更新它的距离。

3. 松弛邻居节点

   • 对于 u 的所有邻接顶点 v，计算 u 到 v 的新距离 newDist = dist[u] + weight(u, v)。

   • 如果 newDist < dist[v]，则更新 dist[v] = newDist，并记录 u 为 v 的前驱节点。

4. 重复步骤 2 和 3，直到所有顶点都处理完，或者优先队列为空。

算法特性：

• 时间复杂度：使用优先队列时为 O(E log V)，其中 E 是边数，V 是顶点数。

• 不能处理含有负权边的图（会导致错误结果）。

• 保证每次取出的顶点，其最短距离已经确定。

4. Dijkstra 算法实现（Java）

下面给出基于上述思路的完整 Java 实现代码，代码中包含了节点（Node）、边（Edge）的数据结构定义，以及 Dijkstra 算法的执行与路径回溯功能。

import java.util.*;class Node {public String name;          // 顶点名称public List<Edge> adj;    // 邻接顶点列表boolean processed;        // 是否已处理public int dist;  // 初始距离设为无穷大public Node preNode;         // 最短路径上的前驱顶点public Node(String name) {this.name = name;this.adj = new ArrayList<>();this.processed = false;this.dist = Integer.MAX_VALUE;this.preNode = null;}// 添加邻接边public void addEdge(Node to, int weight) {this.adj.add(new Edge(this, to, weight));}
}// 边类定义
class Edge {Node from;Node to;   // 目标节点int weight;    // 边权重public Edge(Node from, Node to, int weight) {this.from = from;this.to = to;this.weight = weight;}
}public class GraphShortPath {public static final int INFINITY = Integer.MAX_VALUE;/*** 计算单源无权最短路径* @param source 源顶点*/public static void unweighted(Node source) {Queue<Node> queue = new LinkedList<>();source.dist = 0;             // 源点距离设为0queue.add(source);               // 源点入队while (!queue.isEmpty()) {Node current = queue.poll();// 遍历所有邻接顶点for (Edge edge : current.adj) {Node neighbor = edge.to;// 如果顶点未被访问过if (neighbor.dist == INFINITY) {neighbor.dist = current.dist + 1;    // 更新距离neighbor.preNode = current;             // 记录路径queue.add(neighbor);               // 邻接点入队}}}}/*** Dijkstra 算法 计算 单源赋权最短路径* @param source*/public static void dijkstra(Node source) {PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(node -> node.dist));source.dist = 0;queue.add(source);while (!queue.isEmpty()) {Node current = queue.poll();if (current.processed) continue;current.processed = true;for (Edge edge : current.adj) {Node neighbor = edge.to;if (neighbor.processed) continue;long newDist = (long) current.dist + edge.weight;if (newDist > Integer.MAX_VALUE) continue;if (newDist < neighbor.dist) { // 发现更短路径则更新 neighbor.dist = (int) newDist;neighbor.preNode = current;queue.add(neighbor);}}}}/*** 重构从源点到目标顶点的最短路径* @param to 目标顶点* @return 路径顶点列表*/public static List<Node> reconstructPath(Node to) {List<Node> path = new ArrayList<>();// 如果目标顶点不可达if (to.dist == INFINITY) {return path;}// 从目标顶点回溯到源顶点for (Node v = to; v != null; v = v.preNode) {path.add(v);}// 反转路径：从源顶点到目标顶点Collections.reverse(path);return path;}/*** 打印最短路径结果* @param vertices 顶点列表*/public static void printResults(List<Node> vertices) {System.out.println("顶点\t距离\t前驱\t路径");System.out.println("--------------------------------------");for (Node v : vertices) {System.out.printf("%s\t%d\t%s\t",v.name,v.dist,(v.preNode != null) ? v.preNode.name : "null");// 打印路径List<Node> path = reconstructPath(v);if (path.isEmpty()) {System.out.print("不可达");} else {for (int i = 0; i < path.size(); i++) {if (i > 0) System.out.print(" → ");System.out.print(path.get(i).name);}}System.out.println();}}// 测试用例public static void main(String[] args) {// 创建顶点Node v1 = new Node("图书馆");Node v2 = new Node("教学楼A");Node v3 = new Node("教学楼B");Node v4 = new Node("食堂");Node v5 = new Node("体育馆");Node v6 = new Node("宿舍");Node v7 = new Node("校门");// 构建校园地图的无向图v1.addEdge(v2,5);v1.addEdge(v4,1);v2.addEdge(v1,2);v2.addEdge(v3,3);v2.addEdge(v5,5);v3.addEdge(v2,4);v3.addEdge(v6,3);v4.addEdge(v1,3);v4.addEdge(v5,5);v4.addEdge(v7,2);v5.addEdge(v2,1);v5.addEdge(v4,1);v5.addEdge(v6,3);v6.addEdge(v3,2);v6.addEdge(v5,3);v6.addEdge(v6,4);v7.addEdge(v4,2);v7.addEdge(v6,2);List<Node> campus = Arrays.asList(v1, v2, v3, v4, v5, v6, v7);// 从图书馆出发计算最短路径
//        unweighted(v1);// 从图书馆出发计算最短路径dijkstra(v1);// 打印结果printResults(campus);// 额外测试：从图书馆到校门的最短路径System.out.println("\n从图书馆到校门的最短路径:");List<Node> pathToGate = reconstructPath(v7);for (Node v : pathToGate) {System.out.print(v.name + (v != v7 ? " → " : ""));}}
}

• 运行结果

顶点    距离    前驱    路径
--------------------------------------
图书馆    0    null    图书馆
教学楼A    5    图书馆    图书馆 → 教学楼A
教学楼B    7    宿舍    图书馆 → 食堂 → 校门 → 宿舍 → 教学楼B
食堂    1    图书馆    图书馆 → 食堂
体育馆    6    食堂    图书馆 → 食堂 → 体育馆
宿舍    5    校门    图书馆 → 食堂 → 校门 → 宿舍
校门    3    食堂    图书馆 → 食堂 → 校门从图书馆到校门的最短路径:
图书馆 → 食堂 → 校门