graph - 取图中 2 个节点之间的多个加权边的最小值是最优的吗？

Question

在加权图中，如果要求计算最短路径 .. 并且任何 2 个节点都可能具有多个连接它们的权重不同的边。

---

关于应用 Floyd-Warshall 算法或 Dijkstra 算法：如果 2 个节点之间有多个边，我们可以取最小加权边并忽略其他边吗？

如果是这样，任何人都可以证明这一点吗？提前致谢

Answer 1

是的，你可以采取最低限度。想象一下，您没有采用最小边并找到了一条路线，现在如果您用较短的边替换该边，则新路线将更短。

Answer 2

这得看情况。所有权重是否代表相同的标准？例如）考虑自动驾驶汽车中的最短路径规划问题。需要注意的标准可能不止一个，例如

• 到达目的地所需时间
• 中间点之间的通行费数量
• 道路质量或安全系数[该路线发生事故的历史]

所以这取决于问题陈述。