图
最短路径
最短路径问题问的是：从一个顶点出发，把沿途经过的边的权重加起来，到达另一个顶点最便宜的走法是什么？这就是导航软件为你规划最快回家路线、网络选择延迟最低的路由、游戏角色寻找穿越地形最省代价路径背后的数学。这里的“最短”指总权重最小，并不总是边数最少。
如果图是无权的（每条边都算作一步），答案就是边数最少，而广度优先搜索已经能以 O(V + E) 解决它。一旦各条边带有不同权重，就需要一种总是优先考虑“当前已知最便宜前沿”的算法。Dijkstra 算法正是这样做的：它逐步扩大一个最短距离已经确定的顶点集合，每次挑出尚未确定、暂定距离最小的那个顶点，并松弛它的出边（若经由这个顶点更便宜，就更新邻居的距离）。
Dijkstra 算法假设边权非负——一条负权边会破坏它的贪心推理，那种情况下需要换用别的方法，例如 Bellman-Ford。用优先队列（二叉堆）实现时，Dijkstra 的运行时间约为 O((V + E) log V)，足以应付大型路网，是实践中应用最广的单源最短路径算法。
// pq holds {distance, vertex}, smallest first
auto [d, v] = pq.top(); pq.pop();
if (d > dist[v]) continue; // stale entry
for (auto [nb, w] : adj[v])
if (dist[v] + w < dist[nb]) {
dist[nb] = dist[v] + w;
pq.push({dist[nb], nb});
}弹出最近的顶点，再改进任何经由它能更便宜到达的邻居。
无权图用 BFS，非负权用 Dijkstra，可能出现负权边时用 Bellman-Ford。
又称
另见