最短路径（Dijkstra、Floyd、A*）

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

最短路径问题：在带权图 $G=(V,E)$ 中，从起点 $s$ 到终点 $t$（或到所有点）找一条总权最小的路径。权可以是距离、时间、费用、风险等，只要能合理加总。

三种常用算法定位不同：

算法	直观角色
Dijkstra	从起点像「水波」一样向外扩张，每次确定离起点最近的下一个点；适合非负权单源。
Floyd–Warshall	允许中转点集合逐步扩大，一次算出所有点对最短路；适合小图、多次查询。
A*	在 Dijkstra 思路上加入启发式「估计剩余距离」，优先扩张更有希望到终点的方向；适合大地图点对查询。

网络优化题应优先专用最短路算法，而不是一上来整数规划枚举路径。

二、适用场景与优缺点

类型	说明
适用场景	交通导航、管线铺设、物流路径、通信路由、状态图上的最小代价转移；权可加且结构是图。
核心优点	复杂度清晰；非负权下 Dijkstra 正确高效；Floyd 实现极简；A* 有好启发式时显著更快。
局限与缺点	负权边 Dijkstra 失效（需 Bellman–Ford）；负环使「最短」无定义；A* 启发式不可采纳会损最优性；稠密全源时 Floyd 为 $O(n^3)$ 仅适小 $n$。

使用前确认：

1. 有向还是无向，权是否非负；
2. 单源、单对还是全源；
3. $n=|V|,\ m=|E|$ 规模；
4. 是否需要还原路径而不只是距离。

三、核心原理

1. Dijkstra（非负权单源）

维护每个点的暂定距离 $d(v)$，初始 $d(s)=0$，其余 $+\infty$。集合 $S$ 为已确定最短距离的点。每次取 $V\setminus S$ 中 $d$ 最小者 $u$ 加入 $S$，并松弛所有边 $u\to v$：

$$d(v)\leftarrow\min\bigl(d(v),\, d(u)+w(u,v)\bigr)$$

非负权保证：第一次出堆/加入 $S$ 时 $d(u)$ 已是最终最短距。二叉堆实现 $O((n+m)\log n)$，斐波那契堆理论 $O(m+n\log n)$。

2. Floyd–Warshall（全源）

$d_{ij}^{(k)}$ 表示中转点仅来自 $\{1,\ldots,k\}$ 时 $i$ 到 $j$ 的最短路：

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

三重循环 $O(n^3)$。可同步维护前驱矩阵以重构路径。若某 $d_{ii}<0$，则存在负环。

3. A*（单对，带启发）

节点优先级用

$$f(v)=g(v)+h(v)$$

其中 $g(v)$ 为从 $s$ 到 $v$ 的已知代价，$h(v)$ 为到 $t$ 的估计。若 $h$ 可采纳（不低估真距离）且满足一致性，A* 保证最优，并通常比 Dijkstra 扩展更少节点。

常见 $h$：欧氏距离、曼哈顿距离（网格）、全源预计算到 $t$ 的下界等。$h\equiv 0$ 时 A* 退化为 Dijkstra。

4. 负权

含负权但无负环：Bellman–Ford $O(nm)$。建模时应先检查权是否真能为负（例如「收益」边）。

四、关键决策

1. 算法选型

情形	选择
非负权，单源/单对，中大图	Dijkstra
$n\le$ 数百，需任意点对	Floyd
大地图，已知坐标，单对	A*
有负权	Bellman–Ford / SPFA（注意最坏）

2. 图的存储

稀疏图用邻接表；Floyd 用矩阵。MATLAB 稀疏图也可用 graph/digraph 与 shortestpath。

3. 路径还原

松弛时记录 prev(v)=u，从 $t$ 回溯到 $s$。

4. 多准则

时间+费用不能直接当标量最短路时，应标量化、约束最短路或多目标标签算法，而不是假装单一权。

五、MATLAB 示例

例 1：Dijkstra（邻接表 + 数组实现，小图清晰版）

% 有向图非负权：1->2 (2), 1->3 (5), 2->3 (1), 2->4 (4), 3->4 (1)
n = 4; s = 1; t = 4;
edges = [
    1, 2, 2;
    1, 3, 5;
    2, 3, 1;
    2, 4, 4;
    3, 4, 1
];
adj = cell(n, 1);
for e = 1:size(edges, 1)
    u = edges(e, 1); v = edges(e, 2); w = edges(e, 3);
    adj{u}(end+1, :) = [v, w]; %#ok<SAGROW>
end

INF = 1e18;
dist = INF * ones(n, 1);
prev = zeros(n, 1);
vis = false(n, 1);
dist(s) = 0;

for iter = 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 || best >= INF/2, break; end
    vis(u) = true;
    for k = 1:size(adj{u}, 1)
        v = adj{u}(k, 1); w = adj{u}(k, 2);
        if dist(v) > dist(u) + w
            dist(v) = dist(u) + w;
            prev(v) = u;
        end
    end
end

% 还原路径
path = t;
while path(1) ~= s
    if prev(path(1)) == 0
        path = []; break;
    end
    path = [prev(path(1)), path]; %#ok<AGROW>
end
fprintf("最短距离 = %g\n", dist(t));
disp("路径："); disp(path);

例 2：Floyd

n = 4;
INF = 1e9;
D = INF * ones(n);
D(1:n+1:end) = 0;
wlist = [1 2 2; 1 3 5; 2 3 1; 2 4 4; 3 4 1];
for r = 1:size(wlist,1)
    D(wlist(r,1), wlist(r,2)) = wlist(r,3);
end
nxt = repmat(1:n, n, 1); % 下一步，用于路径

for k = 1:n
    for i = 1:n
        for j = 1:n
            if D(i, k) + D(k, j) < D(i, j)
                D(i, j) = D(i, k) + D(k, j);
                nxt(i, j) = nxt(i, k);
            end
        end
    end
end
disp("全源最短路矩阵："); disp(D);

例 3：A* 于二维网格（四连通，障碍）

grid = zeros(5, 5);          % 0 可走，1 障碍
grid(2:4, 3) = 1;
start = [1, 1]; goal = [5, 5];
h = @(p) abs(p(1)-goal(1)) + abs(p(2)-goal(2));  % 曼哈顿，可采纳

dirs = [1 0; -1 0; 0 1; 0 -1];
key = @(p) p(1)+ (p(2)-1)*size(grid,1);
gScore = containers.Map("KeyType", "double", "ValueType", "double");
came = containers.Map("KeyType", "double", "ValueType", "any");
gScore(key(start)) = 0;
open = start;  % 每行一个点
fval = h(start);

while ~isempty(open)
    [~, idx] = min(fval);
    cur = open(idx, :);
    open(idx, :) = []; fval(idx) = [];
    if isequal(cur, goal), break; end
    for di = 1:4
        nb = cur + dirs(di, :);
        if nb(1)<1||nb(2)<1||nb(1)>size(grid,1)||nb(2)>size(grid,2), continue; end
        if grid(nb(1), nb(2)) == 1, continue; end
        tent = gScore(key(cur)) + 1;
        if ~isKey(gScore, key(nb)) || tent < gScore(key(nb))
            gScore(key(nb)) = tent;
            came(key(nb)) = cur;
            open(end+1, :) = nb; %#ok<SAGROW>
            fval(end+1, 1) = tent + h(nb); %#ok<SAGROW>
        end
    end
end
fprintf("A* 到达代价 g = %g\n", gScore(key(goal)));

例 4：工具箱一行

G = digraph([1 1 2 2 3], [2 3 3 4 4], [2 5 1 4 1]);
[p, d] = shortestpath(G, 1, 4);
disp(p); disp(d);

六、如何解释结果

应报告：

1. 图的类型、权含义与单位；
2. 选用算法及理由（非负？全源？）；
3. 最短距离与节点序列；
4. 复杂度与图规模；
5. A* 的启发函数及是否可采纳；
6. 敏感性：某边权变化是否改道（可选）。

业务语言：「从仓库 1 到门店 4 的最小运输时间为 4，路径 1→2→3→4。」

七、常见误区

1. 负权仍用 Dijkstra

可能错误。改 Bellman–Ford 或确认权非负。

2. 混淆「边数最少」与「权最小」

无权 BFS ≠ 有权最短路。

3. Floyd 用于 $n=5000$

$O(n^3)$ 不可行。应稀疏图多次 Dijkstra。

4. A* 启发高估仍称最优

不可采纳启发只保证次优或需修正说法。

5. 只给距离不给路径

建模答卷通常两者都要。

6. 能用网络算法却上遗传算法

除非权动态、约束极复杂且专用算法失效，否则最短路必须用图算法。

八、小结

最短路径算法的核心思想可以概括为：

在图上通过有序松弛（Dijkstra/A*）或动态规划式中转枚举（Floyd）计算最小代价路径，并回溯得到节点序列。

选型取决于权符号、查询类型与规模。写清权含义、证明/声明前提（非负、可采纳启发），并输出距离与路径。这是网络优化中最基础、也最应优先于通用智能优化的工具。