最短路径

最短路径用于计算从一个起点到其他顶点的最小代价。Baseline 中包含两个版本：无权最短路径和 Dijkstra。两者都输出 dist[] 和 prev[]，但适用场景不同。

场景	边的代价	推荐算法
每一步代价相同	所有边权等价	无权最短路径
每条边有非负权重	权重可能不同	Dijkstra
存在负权边	本章 Baseline 不处理	不使用 Dijkstra

无权最短路径

无权最短路径可以直接建立在 BFS 上。因为 BFS 按层推进，所以第一次访问到某个顶点时，经过的边数一定最少。

无权最短路径：初始化起点

1/7

对应过程：

1. 起点 A 的距离设为 0，前驱设为 -1。
2. 从 A 可以直接发现终点 F，因此无权最短路径会认为 F 的距离是 1。
3. 后续从 B 或 C 展开时，即使存在另一条多边路径，也不能把已经发现的更少边数结果改掉。
4. 从 C 可以继续发现 D。
5. 从 D 可以继续发现 E。
6. 队列为空后，dist[] 记录最少边数，prev[] 记录一棵最短路径树。
7. 这个例子刻意与 Dijkstra 的带权图形成对比：边数少不代表总代价低。

Baseline 中需要补全 ShortestPath(graph, src, dist, prev)。不可达顶点保持 dist[v] = -1、prev[v] = -1。

输入格式：

case_count
vertex_count edge_count directed source
from to
...

输出格式：

CASE 1
DIST ...
PREV ...

公开测试覆盖有向图、无向图、不可达顶点、单顶点图，以及 dist[] 和 prev[] 的一致性。运行方式：

make test-shortest-path

Dijkstra

Dijkstra 用于非负权图。它每轮选择当前已知距离最小、尚未确定的顶点，然后用这个顶点的出边更新其他顶点的距离。这个更新过程称为松弛。

Dijkstra 过程：初始化距离

1/9

对应过程：

1. 起点 A 的距离设为 0，其他顶点先视为不可达。
2. 当前最小的未确定顶点是 A，它会先给出一条直达 F 的高代价路径。
3. 确定 B 后，F 的距离从 30 改进到 21。
4. 确定 C 后，D 的距离变为 6。
5. 确定 D 后，E 的距离变为 9。
6. 确定 E 后，F 的距离进一步改进为 12。
7. 最后确定 F。
8. 最低代价路径是 A -> C -> D -> E -> F，虽然它经过更多条边。
9. 得到最终的 dist[] 和 prev[]。

松弛公式：

if dist[u] + weight(u, v) < dist[v]:
    dist[v] = dist[u] + weight(u, v)
    prev[v] = u

Baseline 中需要补全 Dijkstra(graph, src, dist, prev)。不可达顶点保持 dist[v] = -1、prev[v] = -1。本模块只处理非负权边。

输入格式：

case_count
vertex_count edge_count directed source
from to weight
...

输出格式：

CASE 1
DIST ...
PREV ...

公开测试覆盖有向非负权图、无向非负权图、松弛后选择更短路径、不可达顶点、单顶点图，以及 dist[] 和 prev[] 的一致性。运行方式：

make test-dijkstra

调试重点

• 初始化时是否把起点设为 0，把不可达顶点设为 -1 或内部无穷大。
• 每轮是否选择了当前未确定顶点中距离最小的一个。
• 是否正确跳过不可达顶点。
• 松弛成功时是否同步更新 prev[]。
• prev[] 是否能还原一条合法最短路径。
• 是否能说明为什么 Dijkstra 不适用于负权边。

运行与作业指导

本页对应无权最短路径与 Dijkstra 模块。完成相关 TODO 后，建议运行 make test-shortest-path 和 make test-dijkstra。

完整的 Baseline、Project、输入输出规范和报告要求见：运行与作业指导。