使用Dijkstra算法求解有向图最短路径竞速场景的获胜者问题

给定边权为正的有向图 $G=(V,E)$，边权映射 w:E→R+ 代表道路长度（单位：英里），节点 $t∈V$ 为奖品放置位置。给定玩家起点集合 $A⊆V$，速度映射 s:A→R+ 对应该节点玩家的恒定行进速度。
所有玩家均选择从起点到t的最短路径行进，玩家v经过任意边e的耗时为 w(e)/s(v)，需要给出高效算法找出最先到达t的获胜玩家。

你原来的思路时间复杂度过高：假设图的节点数为n、边数为m、玩家数量为k。如果对每个玩家起点单独跑一次Dijkstra，总时间复杂度为 $O(k(m + n\log n))$，当k接近n时，算法效率会非常差。另外第二步遍历最短路径累加耗时属于冗余操作，拿到起点到t的最短路径总长度后，直接除以速度就能得到总耗时，不需要逐边计算。

核心思路 #

所有玩家都需要计算到t的最短路径长度，我们可以通过反向建图的方式，仅跑一次Dijkstra就得到所有节点到t的最短路径总长度，后续仅需遍历一次玩家集合就能找到获胜者。

实现步骤 #

• 构造原图的反向图G'：将原图中每条有向边 u→v（权重w）替换为 v→u（权重w）
• 以t为源点，在反向图G'上运行一次Dijkstra算法，得到距离数组d，其中d[v]就是原图中节点v到t的最短路径总长度
• 初始化最小耗时为无穷大，获胜节点为空
• 遍历所有玩家起点v∈A：
  • 计算当前玩家总耗时 time_v = d[v] / s(v)
  • 如果time_v小于当前最小耗时，更新最小耗时为time_v，同时记录当前v为获胜节点
• 遍历完成后返回记录的获胜节点即可

复杂度分析 #

用优先队列实现的Dijkstra时间复杂度为 $O(m + n\log n)$，遍历玩家集合的时间为O(k)，整体时间复杂度为 $O(m + n\log n)$，和玩家数量无关，不管k多大都能稳定运行，效率远高于原有方案。

内容的提问来源于stack exchange，提问作者CalculusLover