带正权图中Johnson算法是否可跳过Bellman-Ford步骤？

你的错误根源 #

你最初的回答错在把Johnson算法里Bellman-Ford步骤的作用仅限定为检测负权环——实际上，这个步骤的核心是计算每个节点的势函数h(v)，通过重新定义边权w'(u,v) = w(u,v) + h(u) - h(v)，把原图转化为所有边权非负的图，为后续执行Dijkstra算法铺路。检测负权环只是它的附加功能，用来判断原图是否存在无法求解的情况。

正权图下的两种可行方案 #

• 直接用Dijkstra求所有点对最短路径：完全没问题。正权图里没有负权边，Dijkstra算法可以正确计算单源最短路径，对每个节点作为源点跑一次Dijkstra，就能得到所有点对的结果。时间复杂度上，用优先队列优化后是O(V(E + V log V))，和Johnson算法的O(V^2 log V + VE)在正权场景下效率相近。
• 用Johnson算法时可跳过Bellman-Ford步骤吗？：可以，但理由不能只说“无负权环”。正权图里，你可以直接把所有节点的势h(v)设为0，此时重新计算的边权w'(u,v)和原边权w(u,v)完全一致，后续依然能正常跑Dijkstra。但严格来说，Johnson算法的标准流程包含Bellman-Ford，但正权场景下可以用默认的势函数替代，不需要执行Bellman-Ford。

为什么教授判你错？ #

教授否定你的回答，是因为你没抓住Bellman-Ford在Johnson算法里的核心作用——生成势函数，而不是仅检测负权环。你用“无负权环”作为跳过步骤的理由，本质上是对Johnson算法的设计逻辑理解不到位，而不是“不能直接用Dijkstra”的问题。

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