单源最短路：Dijkstra与Bellman-Ford

考点定位

本课深化 单源最短路：Dijkstra与Bellman-Ford。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

Dijkstra要求边权非负；Bellman-Ford可处理负边并检测可达负环。松弛是两者共同的核心操作。

算法推演

松弛边(u,v,w)：若dist[u]+w<dist[v]则更新。Dijkstra每次确定未确定点中dist最小者，其距离在非负边条件下不再改变。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

已确定集合中每个点的dist都等于真实最短距离。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：存在负权边时不能继续用Dijkstra的贪心确定性结论。

随课应用

无向图边A-B=2、A-C=5、B-C=1，从A到C的最短距离是多少？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。