图论最短路 · 深度手册

分类：优化类 ｜难度：★☆☆ 入门｜编号：dijkstra

一、这是什么（一句话用途）

网络中最短路径（交通 / 通信 / 管网）

二、核心思想

Dijkstra 算法是单源最短路的经典解法，适用于边权非负的网络。它的核心是一个贪心策略加"已确定"集合：每次从未确定节点中挑出当前距离源最短的那个，把它"钉死"为最终最短距离，再用它去松弛（缩短）邻居的距离。由于边权非负，一个节点一旦被钉死，它经其他未确定节点绕路只可能更长——这一步的贪心选择是全局正确的。用优先队列实现可降到 $O((V+E)\log V)$ 。

三、数学原理与推导

初始化： $\mathrm{dist}(s)=0$ ，其余 $\mathrm{dist}(v)=\infty$ ，集合 $S=\varnothing$ （已确定）。

每轮：

取未确定节点中 $u=\arg\min_{v\notin S}\mathrm{dist}(v)$ ；
将 $u$ 加入 $S$ （其距离已最终确定）；
对 $u$ 的每个邻点 $v$ 松弛：

$\mathrm{dist}(v)=\min\big(\mathrm{dist}(v),\ \mathrm{dist}(u)+w(u,v)\big),\quad \mathrm{pred}(v)=u$

重复 $|V|$ 轮。正确性依据：边权非负时，首个被选出的未确定节点 $u$ 的当前距离已是全局最短（任何经其他未确定节点的路径都更长），故可永久确定——这是最优子结构与贪心选择性质的体现。回溯 pred 指针得最短路径。负权边须改用 Bellman-Ford。

四、建模 / 求解步骤

初始化 dist(源=0,余=∞)
选未访问最小 dist 点
松弛其邻边
标记访问
重复至目标

五、关键公式速查

dist(v)=min(dist(u)+w(u,v))

六、典型示例

城市路网两点间最短驾车距离。

完整算例（数字演示，照着算一遍）

场景：无向图边权：A-B=4, A-C=2, B-C=1, B-D=5, C-D=8, D-E=3。求 A→E 最短路。

过程：A(0)→C(2)→B(3)→D(8)→E(11)。

结论：A-C-B-D-E 总长 11 为最短路。

七、Python 实现示例

import os, numpy as np
import pandas as pd, heapq
HERE = os.path.dirname(os.path.abspath(__file__))
df = pd.read_csv(os.path.join(HERE,"..","datasets","dijkstra.csv"))
nodes=pd.unique(df[["from","to"]].values.ravel())
idx={n:i for i,n in enumerate(nodes)}
G={i:[] for i in range(len(nodes))}
for _,r in df.iterrows():
    G[idx[r["from"]]].append((idx[r["to"]], r["weight"]))
src=0; dist={i:1e18 for i in range(len(nodes))}; dist[src]=0
pq=[(0,src)]
while pq:
    d,u=heapq.heappop(pq)
    if d>dist[u]: continue
    for v,w in G[u]:
        if d+w<dist[v]: dist[v]=d+w; heapq.heappush(pq,(dist[v],v))
print("到各点最短距离:", {nodes[i]:round(dist[i],1) for i in range(len(nodes))})

配套文件：py_dijkstra.py（需 numpy / pandas；与下方数据集配套练习）

八、MATLAB 实现示例

%% Dijkstra 最短路示例（MATLAB/Octave）
df = readtable('..\datasets\dijkstra.csv');
edges = table2array(df(:,1:3));
nodes = unique([edges(:,1); edges(:,2)]);
n=length(nodes); G=zeros(n);
for k=1:height(df)
  i=find(nodes==edges(k,1)); j=find(nodes==edges(k,2)); G(i,j)=edges(k,3);
end
D=inf(1,n); D(1)=0; vis=false(1,n);
for s=1:n
  [~,u]=min(D+vis*1e18); vis(u)=true;
  for v=1:n, if G(u,v)>0, D(v)=min(D(v),D(u)+G(u,v)); end, end
end
disp(D)

配套文件：m_dijkstra.m（基础 MATLAB / Octave 即可运行）

九、练手数据集（可下载）

有向图边表（起点、终点、权重），含 7 个节点。用于 Dijkstra 求单源最短路。

字段：from, to, weight
行数：18 行
下载：dijkstra.csv

十、常见误区与避坑清单

边权非负(负权用 Bellman-Ford)
无向 / 有向要分清
大图用优先队列

十一、结果怎么解读

dist 即最短距离，回溯得路径。

十二、常与谁搭配

全源用 Floyd。

十三、论文写作技巧（怎么把它写进论文）

把 图论最短路 写进论文，核心不是堆公式，而是讲清「为什么用它、结果怎么呈现、如何对比」三件事。

1. 动机怎么写（为什么用它而不是别的）

先把问题「数学化」：决策变量、目标函数、约束条件——这一步写清楚比算法本身更重要。再说明为何用图论最短路求解：连续可导用梯度 / 解析法，组合 / 非凸 / 黑箱用启发式（GA / PSO / SA）。

2. 结果怎么写（图表与指标）

放「收敛曲线（迭代 vs 目标值）」+「最优解参数表」+「约束是否满足」三件套。若是多目标，放 Pareto 前沿散点图。

3. 可直接套用的写作话术

中文模板：针对<问题>，本文采用 图论最短路 进行网络中最短路径（交通 / 通信 / 管网）。该方法能够自动刻画<优势>，在处理<场景>时相较<对比方法>更具<特点>。
英文模板：To address , we adopt 图论最短路 to 网络中最短路径（交通 / 通信 / 管网）. Benefiting from its ability to , it outperforms on .

4. 同类易踩的写作坑

务必说明约束是否全部满足、是否陷入局部最优（可多次随机初始化对比）；别把无约束结果当约束最优报。

5. 典型论文段落范例（可直接参考 / 改写）

下面是一段可直接套用的论文表述，已按本算法定制，填空处（…）替换成你的真实数值即可。

将配送中心选址建模为带容量约束的总成本最小化问题，本文采用图论最短路求解，得到 5 个选址及其服务分配方案，目标值较贪婪启发式降低 12.4%，且全部约束满足。

We formulate the distribution center location as a total-cost minimization problem with capacity constraints and solve it via 图论最短路, yielding 5 sites and their service assignments. The objective is 12.4% lower than a greedy heuristic while satisfying all constraints.

十四、相关手册（延伸阅读）

（暂无直接关联手册，可前往手册库浏览其它算法）

十五、本手册导航

上一篇：线性规划 · 优化类
下一篇：K-Means 聚类 · 聚类分类
返回：算法深度手册库｜资料站首页

本手册由「算法深度手册生成器」自动产出，配套提供 Python / MATLAB 双版本示例与可下载练手数据集。