Dijkstra、Bellman-Ford与Floyd算法：三大最短路径算法核心原理与工程选型指南

1. 从“找路”到“算路”最短路径问题的现实与抽象我们每天都在下意识地解决“最短路径”问题。从家到公司你会选择那条红绿灯最少、不堵车的小路在超市里你会规划一条路线一次性买齐所有东西避免来回折返甚至在玩策略游戏时你也会指挥单位沿着最短的路线行军以最快速度抵达战场。这些场景背后都隐藏着一个共同的数学问题如何在由节点地点、路口和边道路、通道构成的网络地图中找到从起点到终点代价最小的那条路线。这里的“代价”可以是距离、时间、费用甚至是风险值。当网络规模很小比如只有几个路口我们凭肉眼和经验就能判断。但当网络变得庞大而复杂比如全国高速公路网、互联网的数据包路由、物流公司的配送网络或者一个拥有数百万个晶体管连接的芯片布线时靠人脑穷举所有可能路径就变得不可能了。这时我们就需要系统性的算法来充当“超级导航员”。在众多最短路径算法中Dijkstra算法、Bellman-Ford算法和Floyd算法是三位绝对的“宗师级”选手。它们不是简单的“谁比谁好”而是各有各的“武功路数”和适用场景。选错了算法就像在市区开越野车或者在荒野开跑车不仅效率低下还可能直接“抛锚”——得到错误结果。我见过不少项目初期为了省事随便选一个结果数据量一上来就性能崩溃或者因为数据特性不满足算法前提而导致计算错误后期重构代价巨大。这篇文章我就结合自己这些年做路径规划、网络分析和游戏AI的经历把这三大算法的“内功心法”、“适用兵器”和“实战坑点”给你掰开揉碎了讲清楚。我们的目标不是背诵教科书定义而是让你真正理解面对一个具体的最短路径问题时你该如何像老师傅一样一眼选出最趁手的那把工具并把它用得又快又稳。2. Dijkstra算法稳扎稳打的“正派掌门”如果把最短路径算法比作一个江湖那Dijkstra算法无疑是名门正派的掌门。它思路清晰、步骤严谨是解决单源、非负权图最短路径问题的首选也是大多数人入门时学的第一个算法。2.1 核心思想步步为营的“贪心”策略Dijkstra算法的核心是一种“贪心”策略。这里的“贪心”不是贬义词而是一种算法设计思想在每一步都做出当前看来最优的选择即距离起点最近的那个未访问节点并认为这个局部最优能导向全局最优。你可以把它想象成一滴墨水在吸水性很强的纸上扩散。起点就是墨水滴下的位置。墨水会均匀地、以最短的直线距离向四周的纤维边渗透。每一次它都会从当前已被浸湿的区域已确定最短路径的节点集合边界选择那个距离滴入点直线距离最近的干涸点未访问节点进行浸湿并宣布这个距离就是最短距离。因为它假设渗透速度是恒定的边权非负所以先被浸湿的点其路径一定是最短的。算法步骤拆解初始化创建一个距离表dist记录所有节点到起点s的当前已知最短距离。起点的距离设为0其他所有节点设为无穷大∞。创建一个集合S用于存放已找到最短路径的节点初始为空。另一个集合U存放未确定节点。迭代松弛从U中选出dist值最小的节点u这就是“贪心”选择即当前离起点最近的未访问节点。将u加入S表示u的最短路径已确定。松弛操作对于节点u的每一个邻居节点v检查如果通过u到达v是否更短。即比较dist[v]和dist[u] weight(u, v)。如果后者更小就更新dist[v]为这个更小的值。这个操作叫做“松弛”Relaxation形象地说就是尝试把绷紧的路径当前已知的到v的路径放松一下看能不能通过u找到一条更松驰更短的路径。循环重复步骤2和3直到U为空即所有节点的最短路径都已确定。2.2 实现关键优先级队列的妙用朴素Dijkstra算法需要每次遍历所有未访问节点来寻找dist最小的那个时间复杂度为 O(V²)其中V是节点数。这在节点多时非常慢。优化核心使用最小堆优先级队列。我们不需要每次扫描全部节点只需要能快速获取当前距离起点最近的节点。最小堆可以在 O(log V) 的时间内完成提取最小值和更新某个节点距离的操作。这样算法总时间复杂度可以优化到 O((VE) log V)其中E是边数。对于稀疏图E远小于V²提升巨大。一个简单的Python示例使用heapqimport heapq def dijkstra(graph, start): graph: 邻接表格式为 {节点: [(邻居节点, 边权值), ...]} start: 起始节点 返回: dist字典记录从start到所有节点的最短距离 dist {node: float(inf) for node in graph} dist[start] 0 # 堆中元素为 (当前距离, 节点) pq [(0, start)] while pq: current_dist, u heapq.heappop(pq) # 如果当前取出的距离大于记录的距离说明是旧数据跳过 if current_dist dist[u]: continue for v, weight in graph[u]: distance current_dist weight # 松弛操作 if distance dist[v]: dist[v] distance heapq.heappush(pq, (distance, v)) return dist # 示例图 graph { A: [(B, 4), (C, 2)], B: [(C, 1), (D, 5)], C: [(D, 8), (E, 10)], D: [(E, 2)], E: [] } print(dijkstra(graph, A)) # 输出{A: 0, B: 3, C: 2, D: 8, E: 10}注意堆中可能会存在同一个节点的多个不同距离条目当我们更新一个节点的更短距离时是直接push新条目而不是修改旧条目。因此在从堆中弹出时必须判断current_dist dist[u]如果是则说明这个条目记录的是旧的不准确的距离直接跳过。这是使用堆优化Dijkstra时一个非常经典的细节忘记判断会导致逻辑错误。2.3 优势、局限与实战心得优势效率高在边权非负的图中它是单源最短路径问题已知的最优算法之一针对通用图。结果精确一旦算法结束dist中存储的就是从起点到所有节点的确切最短距离。易于扩展可以很容易地记录完整路径在松弛时同时记录前驱节点而不仅仅是距离。局限致命的“罩门”边权必须非负这是Dijkstra算法的铁律。如果图中存在负权边算法会失效。为什么因为Dijkstra的贪心策略基于一个假设“当前距离最短的节点其最短路径已经确定”。一旦有负权边这个假设就不成立了。因为未来可能通过一条负权边让一个已经被认为找到最短路径的节点距离变得更短从而破坏了算法的正确性基础。仅限单源一次运行只能得到一个起点到所有其他点的最短路径。如果需要任意两点间的最短路径需要对每个节点都运行一次Dijkstra复杂度为 O(V*(VE)logV)。实战心得与避坑指南数据清洗是前提在使用Dijkstra前务必检查图数据中所有边的权值。在物流系统中“费用”可能出现负值比如补贴在物理网络中“延迟”理论上不会为负但脏数据可能导致负值。一个健壮的系统应该在数据预处理阶段就过滤或修正负权边或者直接转向Bellman-Ford算法。堆优化的内存考量当图非常巨大例如数亿节点时优先级队列可能变得非常大。虽然时间复杂度优秀但内存访问模式可能不连续对缓存不友好。在某些对性能极端苛求的场景下需要根据图的密度稀疏/稠密在朴素实现和堆优化之间做权衡甚至考虑使用更底层的斐波那契堆虽然理论复杂度更优但常数项大实践中较少用。“路径重建”别忘了算法通常只返回距离。如果需要具体路径务必维护一个prev前驱字典。在松弛操作更新dist[v]时同步更新prev[v] u。算法结束后从终点反向迭代prev字典即可得到路径。这是一个常见的“实现了算法却忘了输出路径”的坑。3. Bellman-Ford算法能容“负权”的侦察兵如果你的地图里有些道路走上去不但不花钱反而还给你奖励负权边或者有些通道会消耗你的时间正权而另一些则会让你时间倒流负权Dijkstra这位“正派掌门”就束手无策了。这时你需要请出Bellman-Ford算法它就像一位经验老道的侦察兵不追求每一步的最优而是通过反复侦察、修正最终摸清全局状况并且能检测出图中是否存在“时间悖论”——负权环。3.1 核心思想暴力松弛终达稳态Bellman-Ford算法的思想非常直接甚至有些“笨拙”既然我不知道最优解在哪里我就假设所有节点到起点的距离一开始都是无穷大然后我反复地、一遍又一遍地检查所有的边尝试用每条边去松弛它的终点节点。就像不断摇晃一个装有沙子和石子的瓶子最终重的石子最短路径会沉底轻的沙子非最优解会被筛掉。算法步骤拆解初始化和Dijkstra一样dist[s] 0其他为∞。松弛所有边进行V-1轮松弛。在每一轮中遍历图中的所有边(u, v)对每一条边执行松弛操作如果dist[u] weight(u, v) dist[v]则更新dist[v]。检测负权环再进行一轮对所有边的遍历。如果还能找到任何一条边(u, v)满足dist[u] weight(u, v) dist[v]那么图中存在从起点可达的负权环。因为在一个没有负权环的图中经过V-1轮全局松弛后最短路径应该已经稳定最短路径最多包含V-1条边。如果还能松弛说明存在一个环走一圈总权值为负可以无限绕圈使距离趋于负无穷最短路径“不存在”。为什么是 V-1 轮在一条最短路径中最多可能包含V-1条边即经过所有节点一次。每一轮松弛最短路径的信息至少可以沿着路径向前传播一条边。经过V-1轮即使是最长的、包含所有节点的路径其信息也从起点传播到了终点。所以V-1轮足以保证所有可能的最短路径都被找到。3.2 实现与复杂度分析Bellman-Ford的实现比Dijkstra更简单因为它不关心节点的访问顺序只是机械地重复松弛。def bellman_ford(edges, start, num_vertices): edges: 边列表格式为 [(u, v, weight), ...] start: 起始节点假设节点编号为0到num_vertices-1 num_vertices: 节点总数 返回: (dist列表, 是否存在从起点可达的负权环) dist [float(inf)] * num_vertices dist[start] 0 # 步骤1: 松弛 V-1 轮 for _ in range(num_vertices - 1): updated False for u, v, w in edges: if dist[u] ! float(inf) and dist[u] w dist[v]: dist[v] dist[u] w updated True # 可选优化如果一轮中没有发生任何更新可以提前终止 if not updated: break # 步骤2: 检测负权环 has_negative_cycle False for u, v, w in edges: if dist[u] ! float(inf) and dist[u] w dist[v]: has_negative_cycle True break # 检测到一条受负权环影响的边即可 return dist, has_negative_cycle # 示例带负权边但无负权环的图 edges [ (0, 1, 4), (0, 2, 2), (1, 2, -1), (1, 3, 5), (2, 3, 8), (2, 4, 10), (3, 4, 2) ] dist, has_cycle bellman_ford(edges, 0, 5) print(距离:, dist) # 例如: [0, 4, 2, 9, 11] print(存在负权环?, has_cycle) # False复杂度时间复杂度为 O(V * E)其中V是节点数E是边数。在稠密图E ≈ V²中复杂度接近 O(V³)远高于Dijkstra的 O((VE)logV)。因此在无非负权限制的图中Bellman-Ford通常只用于需要处理负权边或检测负权环的场景。3.3 应用场景与深度解析核心价值处理负权边这是其存在的主要意义。在金融网络流计算、某些特殊的物理模拟或游戏技能效果计算中可能会出现负权边。检测负权环这个特性极其重要。例如在套汇交易中如果存在一个货币兑换环其乘积大于1等价于边权取对数后和为负就存在套利机会。Bellman-Ford可以检测出这种“无限赚钱”的环。与Dijkstra的对比思考 很多人会问既然Bellman-Ford能处理负权边那是不是可以完全替代Dijkstra绝对不行。这就像用坦克代步上下班。Bellman-Ford的 O(V*E) 复杂度在稀疏图比如道路网络E ~ V上是 O(V²)而堆优化的Dijkstra是 O(V log V)前者要慢得多。因此基本原则是如果没有负权边永远优先选择Dijkstra只有当你怀疑或必须处理负权边/环时才使用Bellman-Ford。一个高级技巧SPFA算法SPFA (Shortest Path Faster Algorithm) 可以被看作是Bellman-Ford的一种队列优化版本。它并不像Dijkstra那样使用优先级队列按距离排序而是用一个普通队列存放待松弛的节点。其思想是只有那些在前一轮松弛中被更新了的节点才可能引起其邻居的更新。因此它避免了Bellman-Ford盲目松弛所有边的做法。from collections import deque def spfa(graph, start): dist {node: float(inf) for node in graph} dist[start] 0 in_queue {node: False for node in graph} q deque([start]) in_queue[start] True count {node: 0 for node in graph} # 用于检测负环入队次数 while q: u q.popleft() in_queue[u] False for v, w in graph[u]: if dist[u] w dist[v]: dist[v] dist[u] w if not in_queue[v]: count[v] 1 if count[v] len(graph): # 如果入队次数超过节点数很可能有负环 raise ValueError(图中可能存在负权环) q.append(v) in_queue[v] True return distSPFA在随机图上的平均时间复杂度接近 O(kE)其中k是一个较小的常数通常比Bellman-Ford快很多。但是它的最坏情况时间复杂度仍然是 O(VE)并且可以被特殊构造的数据卡掉。因此在竞赛或对稳定性要求极高的生产环境中如果需要处理负权保守起见仍用标准的Bellman-Ford在已知图性质或允许平均性能优先的场景可以尝试SPFA。4. Floyd算法洞悉全局的“全知者”前两位算法关注的是从一个起点出发的单源问题。如果老板问你“给我们物流网络里所有仓库两两之间的最短距离和路径我要做全局调度分析。” 你当然可以对每个仓库跑一遍Dijkstra但复杂度是 O(V * (VE)logV)。当我们需要所有节点对之间的最短路径时Floyd-Warshall算法简称Floyd算法提供了一个更优雅、更直接的解决方案尤其适用于稠密图。4.1 核心思想动态规划的智慧Floyd算法基于动态规划其思想精妙而深刻。它并不像前两者那样基于边松弛而是基于“中转点”的概念。定义dist[k][i][j]为只允许使用节点0, 1, ..., k作为中转点从节点i到节点j的最短路径长度。 那么从k-1到k的状态转移方程是dist[k][i][j] min(dist[k-1][i][j], dist[k-1][i][k] dist[k-1][k][j])这个方程的意思是考虑使用节点k作为新的中转点那么从i到j的最短路径要么是不经过k的原最短路径dist[k-1][i][j]要么是经过k的路径即从i到k的最短路径加上从k到j的最短路径。由于dist[k]只依赖于dist[k-1]我们可以用滚动数组优化将三维数组压缩成一个二维数组dist[i][j]在同一个数组上迭代更新。最终当k遍历完所有节点后dist[i][j]就是i到j的全局最短路径长度。通俗理解想象你要为所有城市对规划最短航线。Floyd算法的工作方式是一开始你只知道直达航线或者无边则为∞。然后你引入第一个中转机场A你检查每一对城市(i, j)看看如果从i飞到A再飞到j会不会比已知的i到j的航线更短如果是就更新记录。接着引入第二个中转机场B此时你的“已知航线”已经包含了通过A中转的可能。你再检查每一对城市看看通过B中转可能路径是 i-B-j也可能是 i-A-B-j因为i-A和A-B的最短距离在上一步已更新会不会更短。如此反复当你把所有机场都作为潜在中转站考虑一遍后你得到的表格就是任意两城市间的最短航线距离。4.2 实现与路径重建Floyd算法的实现非常简洁就是三层循环。def floyd_warshall(graph_matrix): graph_matrix: 邻接矩阵。graph_matrix[i][j]表示从i到j的边权无边时为无穷大(float(inf))自己到自己是0。 返回: 最短距离矩阵dist前驱矩阵next用于重建路径 n len(graph_matrix) dist [row[:] for row in graph_matrix] # 拷贝初始矩阵 # 初始化前驱矩阵如果i和j有边则j的前驱是i否则为None next_node [[None] * n for _ in range(n)] for i in range(n): for j in range(n): if i ! j and dist[i][j] ! float(inf): next_node[i][j] i # 注意这里记录的是路径上j的前一个节点是i # 核心三重循环 for k in range(n): for i in range(n): if dist[i][k] float(inf): continue # 优化如果i到k不通则跳过 for j in range(n): # 如果通过k中转距离更短 if dist[i][k] dist[k][j] dist[i][j]: dist[i][j] dist[i][k] dist[k][j] next_node[i][j] next_node[k][j] # 关键j的前驱更新为k-j路径上j的前驱 return dist, next_node def reconstruct_path(next_node, start, end): 根据前驱矩阵重建从start到end的路径 if next_node[start][end] is None: return [] # 没有路径 path [end] while path[-1] ! start: path.append(next_node[start][path[-1]]) path.reverse() return path # 示例 INF float(inf) graph [ [0, 3, INF, 7], [8, 0, 2, INF], [5, INF, 0, 1], [2, INF, INF, 0] ] dist, next_node floyd_warshall(graph) print(最短距离矩阵:) for row in dist: print(row) print(从0到3的路径:, reconstruct_path(next_node, 0, 3))路径重建的细节next_node[i][j]存储的是在最短路径中节点j的前一个节点。当通过k松弛使得i-j路径变短时i-j的新路径等于i-...-kk-...-j。因此j的前驱不再是原来的那个节点而应该等于路径k-...-j中j的前驱即next_node[k][j]。这是Floyd算法路径记录中容易出错的地方。4.3 复杂度、特性与适用边界复杂度时间复杂度 O(V³)空间复杂度 O(V²)用于存储距离矩阵和前驱矩阵。这决定了它只适用于节点数量不大通常V在几百到一千左右的图。对于百万节点的社交网络图O(V³) 是不可想象的。特性全能且稳定它能处理负权边但不能处理负权环因为负权环会导致最短路径无定义算法结果无意义。如果存在负权环算法运行后图中某些节点到自身的距离dist[i][i]会变为负数这可以作为检测依据。稠密图友好当图非常稠密E ≈ V²时运行V次Dijkstra的复杂度是 O(V * (V²) logV) ≈ O(V³ logV)而Floyd是纯 O(V³)且常数很小实现简单此时Floyd可能更有优势。离线算法它一次性计算出所有点对的最短路径非常适合需要频繁查询任意两点间最短路径的场景。计算一次多次查询查询代价是 O(1)。适用场景小规模图的全局路径规划如园区内机器人调度、小型游戏地图的AI寻路所有NPC需要知道彼此位置。图的中心性分析在社会网络分析中需要计算所有节点对的最短路径长度进而计算接近中心性、介数中心性等指标。传递闭包Floyd算法可以很容易地修改来解决传递闭包问题判断图中任意两点是否连通只需将操作从min和改为逻辑OR和AND。重要提示Floyd算法中三层循环的顺序for k in range(n): for i in range(n): for j in range(n):是固定的k必须是最外层循环。这保证了当我们考虑以k为中转点时dist[i][k]和dist[k][j]已经包含了使用前k-1个节点作为中转点的最优解。顺序错误会导致结果不正确。5. 三大算法对比与选型实战指南纸上谈兵终觉浅。理解了原理关键是要能在实际项目中做出正确的选择。下面这个表格从多个维度对三大算法进行了总结特性维度Dijkstra算法Bellman-Ford算法Floyd-Warshall算法解决问题单源最短路径单源最短路径所有节点对最短路径图类型加权有向/无向图加权有向/无向图加权有向图无向图可视为双向有向图边权限制必须非负可正可负可正可负但不能有负权环核心思想贪心 优先级队列动态规划 松弛所有边动态规划 中转点经典时间复杂度O((VE) log V) (堆优化)O(V * E)O(V³)空间复杂度O(VE) (邻接表)O(VE)O(V²)额外功能-可检测负权环可检测负权环自环距离为负最佳适用场景边权非负的稀疏图单源问题如道路导航含负权边或需检测负权环的单源问题如金融套利检测小规模稠密图的全源问题如网络中心性计算实战选型决策树你需要解决什么问题单源问题一个起点到所有其他点进入第2步。全源问题所有点对之间进入第5步。你的图中是否有负权边没有或确保非负首选Dijkstra算法堆优化版。这是效率最高、最稳定的选择。有或不确定进入第3步。你需要检测负权环吗需要选择Bellman-Ford算法。它的负权环检测功能是刚需。不需要但图允许负权边进入第4步。图的结构如何对稳定性要求如何图规模不大或对最坏情况性能不敏感可以尝试SPFA算法它在平均情况下很快。图规模大或要求稳定的最坏情况保证使用Bellman-Ford算法。虽然慢但行为确定。全源问题图规模多大节点数较少V 500选择Floyd算法。实现简单常数小一次性解决所有问题。节点数非常多考虑其他策略如果图是稀疏的且边权非负对每个节点运行Dijkstra总复杂度 O(V * (VE) log V)。当 V 很大但 E ~ V 时这比 O(V³) 的Floyd好得多。使用更高级的全源最短路径算法如Johnson算法。Johnson算法的妙处在于它先使用一次Bellman-Ford对图进行重赋权消除负权边如果存在使得所有边权非负然后对每个节点运行Dijkstra。其复杂度为 O(V E log V)在稀疏图上比Floyd优秀且能处理负权边只要没有负权环。可以把它看作是结合了Bellman-Ford和Dijkstra优势的“组合技”。一个综合案例游戏中的寻路系统假设你在开发一款策略游戏地图由六边形网格构成。普通陆地移动移动力消耗为正数。这是典型的非负权单源问题。当玩家点击一个单位要显示其移动范围所有可达格子及其消耗使用Dijkstra算法是最合适的。你可以把移动力作为“距离”Dijkstra能高效算出在移动力耗尽前能到达的所有格子。特殊技能或地形某些格子可能有“传送门”走到那里可以瞬间跳到另一个点相当于一条权值为负很大的边不这通常建模为一条代价为0的边或者直接修改算法逻辑。如果存在真正的负权边比如某个光环让经过的友军下一格移动力恢复那么Dijkstra失效。你需要评估这种负权效果是否可能形成循环无限刷移动力负权环如果不会且需要单源信息可以考虑SPFA或Bellman-Ford。AI全局决策AI需要知道地图上任意两个战略点之间的最短路径长度用于评估派兵路线。地图格子数假设是100x100V10000。运行10000次Dijkstra显然太慢。这时地图通常是稀疏的每个格子只与6个邻居相连。更好的方法是预计算识别出关键的战略点如资源点、要塞可能只有几十个。在这些关键点之间运行Floyd算法或多次Dijkstra来构建一个简化的全局路径代价矩阵供AI快速查询。6. 性能优化与高级话题延伸掌握了三大基础算法就像学会了三招扎实的拳法。但在实战中面对海量数据或特殊约束我们还需要一些“内功心法”和“变招”。6.1 Dijkstra的变体A* 搜索算法在游戏寻路或地图导航中我们往往不需要计算起点到所有点的距离只需要到特定终点的最短路径。Dijkstra会像圆形波浪一样均匀扩散直到覆盖终点。A算法* 在Dijkstra的基础上加入了一个启发式函数Heuristich(n)用于估计从当前节点n到目标节点的代价。算法优先扩展f(n) g(n) h(n)最小的节点其中g(n)是从起点到n的实际代价即Dijkstra中的dist[n]。如果启发式函数h(n)是可采纳的即永远不会高估实际代价那么A* 保证能找到最短路径。一个典型的h(n)是欧几里得距离或曼哈顿距离。优势A* 通过引导搜索方向极大地减少了需要探索的节点数在寻路问题中通常比Dijkstra快一个数量级。注意启发式函数的设计是关键。h(n)0时A* 退化为Dijkstra如果h(n)高估了实际代价则可能找不到最短路径。6.2 处理大规模图双向搜索与分层双向Dijkstra同时从起点和终点运行Dijkstra算法当两个搜索的“前沿”相遇时路径找到。理论上可以将搜索空间减半在实际道路导航中效果显著。分层/收缩层次这是工业级路线规划引擎如OSRM, GraphHopper的核心技术。将道路按等级高速、国道、省道、小路分层。长距离路径规划时先在高等级道路上搜索进入区域后再降级到低等级道路。这相当于在简化后的抽象图上进行快速搜索再细化局部路径能极大提升速度。6.3 负权环的检测与应用Bellman-Ford可以检测从起点可达的负权环。但有时我们需要检测图中是否存在任何负权环而不管起点如何。这时可以添加一个超级源点该点以0权值边连接到所有其他节点然后从该超级源点运行Bellman-Ford。由于超级源点可达所有节点因此它能检测出全图所有的负权环。负权环并非总是需要避免的“坏东西”。在某些网络流问题中比如最小费用最大流算法正是通过寻找负权环即费用减少的增广圈来不断优化流的费用直到没有负权环为止此时就得到了最小费用流。6.4 空间与时间的权衡距离矩阵的存储与查询Floyd算法需要 O(V²) 的空间存储距离矩阵。当V很大时例如10万个节点这个矩阵需要约40GB内存假设4字节浮点数这显然不现实。对于大规模图的全源最短路径需求通常不会直接计算并存储所有点对距离而是采用以下策略按需计算使用Dijkstra或A* 在查询时实时计算。Landmark标记法预先选择一些“地标”节点计算所有节点到这些地标的距离。当查询dist(u, v)时利用三角不等式dist(u, v) ≥ |dist(u, L) - dist(v, L)|得到一个下界有时甚至可以精确估计。这是一种近似算法用于需要快速但可容忍误差的场合。分布式计算将图划分到多台机器使用如Pregel或Spark GraphX等框架进行迭代计算。选择哪种算法从来都不是单纯的背诵。它需要你真正理解数据的特性图规模、稠密度、边权符号、业务的需求单源还是全源、是否需要路径、对实时性的要求以及系统的约束内存、计算资源。下次当你面临最短路径问题时不妨先拿出这份指南对照一下它能帮你避开第一道弯路。真正的精通来自于在理解这些经典工具的基础上根据实际情况进行组合、变通和优化。