我正在尝试通过此链接解决问题:
(这不是作业题)
Consider a weighted directed graph G with n vertices and e edges, and the weights are integers. Suppose that G contains no negative cycles, and for every pair of vertices u and v in G, the distance from u to v falls in the range [-2d, 2d] for some positive integer d. We are going to fix a particular edge (x,y) in G, and consider what happens to the distances in G as we change the weight associated with that edge (and leave all other edge weights fixed).
Design an algorithm that takes G as input, as well as a specified edge (x,y) in G. The output of the algorithm should be an integral range of values that the weight of this edge (x,y) could take such that all of the distances in G would remain the same. Note that this range will be non-empty, as it must include the original weight of the edge (x,y). Also note that infinity may occur as an endpoint of your range (i.e. the range may not be finite). For this, you may return “∞” as an endpoint. The running time of your algorithm must be polynomial in n,e, and d (so your running time should not have any of these parameters appearing as exponents). Prove why the algorithm is correct.
我一直在思考以下几行: 由于距离在一个范围内，权重也应该在一个范围内。一种选择是我们多次运行 Djkstra。我们如何优化它？
最佳答案
是的，你可以运行 Dijkstra n 次。或者，您可以运行专为这些问题设计的 Floyd-Warshall。总体而言，它们具有相似的复杂性界限。
关于algorithm - 加权图和所有对路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36587124/