修改Dijkstra算法求无正环有向图单源最长路径是否正确？

问题描述 #

给定无正长度环的有向图 G = (V,E)，对Dijkstra算法做如下修改，尝试求解从源点s出发的最长路径长度：

• 初始化：d(s) = 0，所有 v ∈ V \ {s} 的 d(v) = int_min；
• 每次迭代：选取当前d(u)值最大的节点u；
• 松弛操作：若 d(v) < d(u) + c(uv)，则更新 d(v) := d(u) + c(uv)。

请问该算法能否正确求解上述最长路径问题？若不能，请给出反例。

结论与反例 #

该算法无法正确求解无正环有向图的最长路径问题，以下是具体反例：

反例图结构 #

• 节点集合：V = {s, a, b, t}
• 边及权重：
  • s → a，权重 1
  • s → b，权重 2
  • a → t，权重 3
  • b → t，权重 1

算法执行过程模拟 #

1. 初始化：d(s)=0，d(a)=int_min，d(b)=int_min，d(t)=int_min；所有节点均未访问。
2. 第一次迭代：选取d(u)最大的节点s，处理邻接节点：
   • 更新 d(a) = max(int_min, 0+1) = 1
   • 更新 d(b) = max(int_min, 0+2) = 2
     标记s为已访问。
3. 第二次迭代：选取d(u)最大的节点b（d(b)=2 > d(a)=1），处理邻接节点t：
   • 更新 d(t) = max(int_min, 2+1) = 3
     标记b为已访问。
4. 第三次迭代：选取d(u)最大的节点t（d(t)=3 > d(a)=1），标记t为已访问，不再处理其邻接节点（无出边）。
5. 第四次迭代：选取节点a，处理邻接节点t，但t已被标记为已访问，算法不执行更新操作。

结果对比 #

算法最终得到d(t)=3，但实际上从s到t的最长路径是s→a→t，路径长度为1+3=4，与算法结果不符，证明该变种算法无效。

失效原因 #

Dijkstra原算法的贪心策略成立的核心是边权非负，一旦节点被选取，其最短路径就已确定，无需后续更新。但最长路径问题中，即使无正环，后续处理其他节点时仍可能发现更长的路径指向已被选取的节点，而该变种算法将节点标记为已访问后不再更新，导致错过最优解。

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