导航 App 是怎么算出最短路径的？

导航 App 是怎么算出最短路径的？

你在导航里输入目的地，几百毫秒内它就给出路线——背后是几十万个路口节点、上百万条道路的图搜索。这个"瞬间算最短路"的算法叫 Dijkstra，1956 年由荷兰计算机科学家 Edsger Dijkstra 用 20 分钟设计出来。今天讲透它。

一、把地图变成"图"

路径规划的第一步是建模：路口 = 节点，道路 = 边，距离/时间 = 边权。于是"找最快路线"变成图论问题：求两点间的最短路径。

二、Dijkstra 的核心思想：贪心扩展

算法思路非常直观——从起点向外"扩散"，每次选当前最近的未访问节点：

为什么贪心是对的？ 因为所有边权非负——当某个节点的距离是当前最小时，不可能再有更短的路径绕过其他节点到达它。这个"非负权"前提是 Dijkstra 成立的关键。

三、为什么用优先队列？

朴素实现每轮都要"扫描所有点找最小"——O(V²)。用**优先队列（最小堆）**把"找最小"降到 O(log V)，总复杂度 O(E log V)。这就是导航能实时计算的原因。

四、代码演示：手写 Dijkstra

import heapq

graph = {
'A': {'B': 4, 'C': 2},
'B': {'C': 5, 'D': 10},
'C': {'E': 3},
'D': {'F': 11},
'E': {'D': 4},
'F': {},
}

def dijkstra(graph, start):
dist = {n: float('inf') for n in graph}
dist[start] = 0
pq = [(0, start)] # 最小堆：(距离, 节点)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: # 过期条目，跳过
continue
for v, w in graph[u].items():
if d + w < dist[v]: # 松弛
dist[v] = d + w
heapq.heappush(pq, (d + w, v))
return dist

d = dijkstra(graph, 'A')
print("从 A 出发到各点最短距离:")
for k, v in d.items():
print(f" A -> {k}: {v}")

运行输出：

从 A 出发到各点最短距离:
A -> A: 0
A -> B: 4
A -> C: 2
A -> D: 9
A -> E: 5
A -> F: 20

注意 A→D：直达没有边，绕道 A→C→E→D 得到 2+3+4=9，比 A→B→D（4+10=14）更短——算法自动找到了最优绕行方案。导航 App 处理的是百万节点的放大版，原理完全一样。

五、避坑清单

六、想系统学图算法？

本文精选自 ima 知识号【Kruptos】《数据结构与算法详解》订阅库（第 075 期图的表示、第 077 期 BFS、第 079 期 Dijkstra、第 080 期 Bellman-Ford 等 100 期系统教程，从数组、链表、树到排序、动态规划与图论，每期配可运行代码）。

📚 完整系列 100 期 + 配套代码，已在 ima 知识号发布

本文只是系列的一个切片。完整系列（100 期系统教程 + 每期可运行代码）在 ima 知识号【Kruptos】持续更新中：

• 🗂 68+ 技术知识库：信号与系统、SDR 软件无线电、数字信号处理、操作系统、AI Agent、大模型微调……几乎覆盖全部软硬件技术栈
• 🧠 8 款 AI 技能：系列生产、知识库管理、CMMI 受管开发、自进化 Agent 等，已在 ima 技能广场上架，即装即用
• ✅ 全部免费订阅，后续更新自动推送

🔍 订阅方式：打开 ima（腾讯智能工作台）→ 搜索「Kruptos」→ 一键订阅。或在 ima 内直接搜索《数据结构与算法详解》等知识库名称。

💬 你面试遇到过图算法题吗？A* 用过吗？评论区聊聊——想看 Bellman-Ford 还是 A*，点赞高的安排。

作者：Kruptos（西电毕业，13 年无线通信/DSP/嵌入式科研）｜原创内容，转载注明出处