data-structures - 在最短路径变化的图形的情况下是真的吗？

Question

在图中，两个节点之间存在最短路径。现在，如果我为图的每个边权重添加一个常数值，这条最短路径会改变吗？

标签： data-structuresgraph-theory

Answer 1

如果加权最短路径不是未加权最短路径，它可以改变。这是一个简单的例子。

在 1 和 3 之间有两条路径：
1-> 2 -> 3 的权重为 2
1-> 3 的权重为 3
，因此最短路径是 1->2->3。

但是，如果将每条路径的权重加 10，则权重变为
1-> 2 -> 3 的权重为 22
1-> 3 的权重为 13
，因此最短路径为 1->3。