最短路径

一、直观理解：在地图上找总代价最小的走法

最短路径问题：在带权图 $G=(V,E,w)$ 中，找从起点 $s$ 到终点 $t$（或到所有点）的一条路径，使边权之和最小。

权可以是距离、时间、费用、风险等。只要能把“代价可加”写清楚，就能落到最短路。

常见算法族：

算法	场景	要点
Dijkstra	单源，非负权	优先队列高效
Bellman–Ford	单源，可负权	可检测负环
Floyd–Warshall	全源，稠密小图	$O(n^3)$ DP
A*	单源，有启发信息	可采纳启发保证最优

二、适用场景与优缺点

类型	说明
适用场景	导航与物流基线；管网/电路布线；状态空间中的最小代价转移；建模中“最优路线”子问题。
核心优点	问题清晰；算法成熟；可给出可检验的路径与长度；易与时间窗等扩展结合（需改模型）。
局限与缺点	经典最短路不含资源约束；负权与负环要特殊处理；动态路况需重算或动态算法；多目标需改标量或 Pareto。

三、核心原理

1. 最优子结构

最短路上的任何子段也是最短路。这是松弛（relax）操作的基础：

$$\mathrm{dist}[v]>\mathrm{dist}[u]+w(u,v)\Rightarrow \text{更新}$$

2. Dijkstra

维护已确定最短路的集合 $S$。每次取 $\mathrm{dist}$ 最小的未确定点入 $S$ 并松弛出边。非负权保证“第一次取出即确定”。

复杂度：二叉堆约 $O((n+m)\log n)$。

3. Bellman–Ford

对所有边做 $n-1$ 轮松弛；若第 $n$ 轮仍更新，则存在从源可达负环。

4. Floyd

$$d_{ij}^{(k)}=\min\{d_{ij}^{(k-1)}, d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\}$$

允许中间节点集合逐步扩大到 $\{1,\ldots,k\}$。

5. A*

优先扩展 $f(n)=g(n)+h(n)$ 最小节点，$g$ 为已走代价，$h$ 为启发。若 $0\le h(n)\le h^*(n)$（可采纳）且一致，则得最优。

四、关键决策

1. 选哪算法

• 非负 + 单源：Dijkstra；
• 有负权：Bellman–Ford；
• 多次查询全源且 $n$ 小：Floyd；
• 网格/地图有启发：A*。

2. 图如何建

单向路、禁止转向、换乘惩罚都要进边权或图层（状态展开）。

3. 验证

小图手算；检查路径连通且权之和等于 dist；有负权时报告无负环。

五、MATLAB 示例

% 有向带权图
s = [1 1 2 3 3 4];
t = [2 3 4 2 4 5];
w = [2 5 2 1 1 3];
G = digraph(s, t, w);
% 自动 Dijkstra
[path, d] = shortestpath(G, 1, 5);
fprintf("最短路: %s, 长度=%g\n", mat2str(path), d);

figure;
plot(G, "EdgeLabel", G.Edges.Weight, "NodeColor", "k");
title("示例网络");

% ---- 手写 Dijkstra（稠密数组）----
n = 5;
W = inf(n);
for e = 1:numel(s)
    W(s(e), t(e)) = w(e);
end
dist = inf(1,n); prev = zeros(1,n);
dist(1) = 0; vis = false(1,n);
for it = 1:n
    u = 0; best = inf;
    for i = 1:n
        if ~vis(i) && dist(i) < best
            best = dist(i); u = i;
        end
    end
    if u==0, break; end
    vis(u) = true;
    for v = 1:n
        if W(u,v) < inf && dist(v) > dist(u) + W(u,v)
            dist(v) = dist(u) + W(u,v);
            prev(v) = u;
        end
    end
end
fprintf("手写 Dijkstra dist(1->5)=%g\n", dist(5));

% 回溯路径
v = 5; p = v;
while prev(v) ~= 0
    v = prev(v); p = [v p];
end
disp(p);

% Floyd 全源（小图）
D = W; D(1:n+1:end) = 0;
for k = 1:n
    D = min(D, D(:,k) + D(k,:));
end
disp("Floyd 距离矩阵:"); disp(D);

六、如何解释结果

1. 图的含义、方向与权单位；
2. 算法选择理由；
3. 路径顶点序列与总权；
4. 若多解，说明并列最优；
5. 敏感性：关键边权 ±10% 是否改路；
6. 与实际约束差距（拥堵、限行未建模则声明）。

七、常见误区

1. 负权仍用 Dijkstra

可能错误。

2. 把“站点数最少”当最短路

那是无权 BFS；有权必须用上述算法。

3. 不检查不连通

dist=inf 要解释为不可达。

4. 启发式 h 高估仍声称最优

A* 失去保证。

八、小结

最短路径的核心是：

在可加边权上，用松弛与最优子结构计算最小代价路径。

按权符号与查询类型选 Dijkstra / Bellman–Ford / Floyd / A*，并把建图与验证写清楚，是图论建模最基本也最常用的能力。