所以我一直在想，在不求助于另一种算法的情况下，您可以对图表进行哪些修改以允许 Dijkstra 的算法对其进行处理，并且在一天结束时仍能得到正确的答案？如果有可能呢？
我首先想到在所有权重中添加一个等于最负权重的常数，但我发现这会搞砸一切并改变原来的单一来源路径。
然后，我想到遍历图表，将所有小于零的权重放入一个数组或类似的东西中，然后将其乘以 -1。我认为他会工作（不考虑运行时间限制），但也许我看错了。
编辑：另一个想法。将所有负权重永久设置为无穷大怎么样。那样确保它们被忽略？
所以我只是想听听对此的一些看法；你们有什么感想？
似乎您正在寻找类似于约翰逊算法的东西：
首先，将一个新节点 q 添加到图中，由零权重边连接到每个其他节点。
其次，使用 Bellman-Ford 算法，从新的顶点 q 开始，为每个顶点 v 找到从 q 到 v 的路径的最小权重 h(v)。如果这一步检测到负循环，则算法终止.
接下来，使用 Bellman-Ford 算法计算的值对原始图的边进行重新加权：从 u 到 v，长度为 w(u,v)，给定新长度 w(u,v) + h( u) - h(v)。
最后，去掉 q，并使用 Dijkstra 算法在重新加权的图中找到从每个节点 s 到每个其他顶点的最短路径。
通过任何算法，您都应该检查负循环，如果没有负循环，则找到最短路径。
在您的情况下，您需要运行一次 Dijkstra 算法。另请注意，在约翰逊算法中，半贝尔曼-福特算法仅针对新添加的节点运行。（并非所有顶点）。