目录
1. 什么是赋权最短路径
在图论中，最短路径问题是指在图中寻找两点之间路径总权重最小的路径问题。如果图的每条边都带有权值（weight），这种图称为赋权图（Weighted Graph）。
2. 赋权最短路径中的关键概念
在赋权最短路径算法中，常用的几个重要概念包括：
顶点（Vertex/Node） 图的基本组成元素，用于表示位置或对象。
边（Edge） 顶点之间的连接关系，可能是有向的（Directed）或无向的（Undirected）。
权重（Weight） 与每条边相关联的数值，表示从一个顶点到另一个顶点的“代价”，可能是时间、距离、费用等。
路径（Path） 由一系列顶点和边构成的通路。
路径长度（Path Length） 路径上所有边的权重之和。
前驱节点（Predecessor Node） 在最短路径中，到达某个顶点前的上一个顶点，用于回溯构建路径。
松弛操作（Relaxation） 如果通过某条边能找到更短的路径，则更新目标顶点的最短距离和前驱节点的过程。
3. Dijkstra 算法的基本思想
Dijkstra 算法由 Edsger W. Dijkstra 在 1956 年提出，是解决单源非负权重最短路径问题的经典算法。 其核心思想是：
初始化
将源点的最短距离设置为 0，其他顶点设置为无穷大（
Integer.MAX_VALUE）。使用一个优先队列按当前已知的最短距离排序。
迭代选择最近的未处理顶点
从优先队列中取出当前距离最小的顶点
u。将其标记为“已处理”，不再更新它的距离。
松弛邻居节点
对于
u的所有邻接顶点v，计算u到v的新距离newDist = dist[u] + weight(u, v)。如果
newDist < dist[v]，则更新dist[v] = newDist，并记录u为v的前驱节点。
重复步骤 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; // 源点距离设为0
queue.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 食堂 图书馆 → 食堂 → 校门 从图书馆到校门的最短路径: 图书馆 → 食堂 → 校门