目录
在图论中，单源无权最短路径问题是指在一个无权图（所有边权重相等，通常视为1）中，从某个源顶点出发，计算到图中所有其他顶点的最短路径的问题。这类问题在计算机科学和现实应用中有着广泛的应用：
关键概念
无权图：所有边具有相同的权重（通常视为1）
最短路径：连接两个顶点的边数最少的路径
源顶点：算法计算的起点
距离：从源顶点到目标顶点的最短路径长度
前驱节点：在最短路径上，某个顶点的前一个顶点
一 BFS算法实现思路
广度优先搜索（BFS）是解决单源无权最短路径问题的理想算法，因为它按层级遍历图结构，天然保证了最先到达的路径就是最短路径。
1 算法核心思想
层级遍历：从源顶点开始，首先访问所有距离为1的顶点，然后是距离为2的顶点，以此类推
队列管理：使用队列存储待访问的顶点，确保先进先出（FIFO）的访问顺序
距离标记：为每个顶点记录从源顶点到该顶点的距离
路径追踪：记录最短路径上的前驱顶点，便于重构完整路径
2 算法步骤
初始化源顶点距离为0，其他顶点距离为无穷大(∞)
将源顶点加入队列
当队列不为空时：
从队列中取出一个顶点v
遍历v的所有邻接顶点w：
如果w未被访问过（距离为∞）：
设置w的距离为v的距离+1
设置w的前驱为v
将w加入队列
当队列为空时，算法结束
3 算法特点
时间复杂度：O(V+E)，其中V是顶点数，E是边数
空间复杂度：O(V)，用于存储队列和顶点信息
完整性：能够找到源顶点到所有可达顶点的最短路径
最优性：保证找到的路径是最短的
二 代码实现(Java)
import java.util.*;
class Vertex {
public String name; // 顶点名称
public List<Vertex> adj; // 邻接顶点列表
public int dist = Integer.MAX_VALUE; // 初始距离设为无穷大
public Vertex path; // 最短路径上的前驱顶点
public Vertex(String name) {
this.name = name;
this.adj = new ArrayList<>();
}
// 添加邻接顶点
public void addNeighbor(Vertex... neighbors) {
for (Vertex neighbor : neighbors) {
this.adj.add(neighbor);
}
}
}
public class UnweightedShortestPath {
public static final int INFINITY = Integer.MAX_VALUE;
/**
* 计算单源无权最短路径
* @param s 源顶点
*/
public static void unweighted(Vertex s) {
// 初始化队列
Queue<Vertex> q = new LinkedList<>();
// 初始化源顶点
s.dist = 0; // 源点距离设为0
q.add(s); // 源点入队
while (!q.isEmpty()) {
Vertex v = q.remove();
// 遍历所有邻接顶点
for (Vertex w : v.adj) {
// 如果顶点未被访问过
if (w.dist == INFINITY) {
w.dist = v.dist + 1; // 更新距离
w.path = v; // 记录路径
q.add(w); // 邻接点入队
}
}
}
}
/**
* 重构从源点到目标顶点的最短路径
* @param target 目标顶点
* @return 路径顶点列表
*/
public static List<Vertex> reconstructPath(Vertex target) {
List<Vertex> path = new ArrayList<>();
// 如果目标顶点不可达
if (target.dist == INFINITY) {
return path;
}
// 从目标顶点回溯到源顶点
for (Vertex v = target; v != null; v = v.path) {
path.add(v);
}
// 反转路径：从源顶点到目标顶点
Collections.reverse(path);
return path;
}
/**
* 打印最短路径结果
* @param vertices 顶点列表
*/
public static void printResults(List<Vertex> vertices) {
System.out.println("顶点\t距离\t前驱\t路径");
System.out.println("--------------------------------------");
for (Vertex v : vertices) {
System.out.printf("%s\t%d\t%s\t",
v.name,
v.dist,
(v.path != null) ? v.path.name : "null");
// 打印路径
List<Vertex> 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) {
// 创建顶点
Vertex v1 = new Vertex("图书馆");
Vertex v2 = new Vertex("教学楼A");
Vertex v3 = new Vertex("教学楼B");
Vertex v4 = new Vertex("食堂");
Vertex v5 = new Vertex("体育馆");
Vertex v6 = new Vertex("宿舍");
Vertex v7 = new Vertex("校门");
// 构建校园地图的无向图
v1.addNeighbor(v2, v4); // 图书馆连接教学楼A和食堂
v2.addNeighbor(v1, v3, v5); // 教学楼A连接图书馆、教学楼B和体育馆
v3.addNeighbor(v2, v6); // 教学楼B连接教学楼A和宿舍
v4.addNeighbor(v1, v5, v7); // 食堂连接图书馆、体育馆和校门
v5.addNeighbor(v2, v4, v6); // 体育馆连接教学楼A、食堂和宿舍
v6.addNeighbor(v3, v5, v7); // 宿舍连接教学楼B、体育馆和校门
v7.addNeighbor(v4, v6); // 校门连接食堂和宿舍
List<Vertex> campus = Arrays.asList(v1, v2, v3, v4, v5, v6, v7);
// 从图书馆出发计算最短路径
unweighted(v1);
// 打印结果
printResults(campus);
// 额外测试：从图书馆到校门的最短路径
System.out.println("\n从图书馆到校门的最短路径:");
List<Vertex> pathToGate = reconstructPath(v7);
for (Vertex v : pathToGate) {
System.out.print(v.name + (v != v7 ? " → " : ""));
}
}
}
测试结果分析
运行上述程序，我们可以得到以下结果：
顶点 距离 前驱 路径 -------------------------------------- 图书馆 0 null 图书馆 教学楼A 1 图书馆 图书馆 → 教学楼A 教学楼B 2 教学楼A 图书馆 → 教学楼A → 教学楼B 食堂 1 图书馆 图书馆 → 食堂 体育馆 2 教学楼A 图书馆 → 教学楼A → 体育馆 宿舍 3 教学楼B 图书馆 → 教学楼A → 教学楼B → 宿舍 校门 2 食堂 图书馆 → 食堂 → 校门 从图书馆到校门的最短路径: 图书馆 → 食堂 → 校门
BFS算法是解决单源无权最短路径问题的最佳选择，它利用队列按层级遍历图结构，保证最先找到的路径就是最短路径。本文介绍了算法的理论基础、实现思路，并提供了完整的Java实现代码。该算法在网络路由、社交网络分析、游戏开发等领域有广泛应用，是图论中最基础且重要的算法之一。