我遇到了这个问题，我不知道如何证明。任何帮助，将不胜感激。
Q) 证明跨图的最短路径是无环的
网络路由和什么使网络循环免费
网络工程
路由
网络核心
2022-02-12 03:10:34
1个回答
矛盾的是：假设p是图上的最短路径，并且p有一个循环。删除循环。图上的新无环路径比p短。我们已经实现了矛盾，所以我们最初的假设一定是错误的。
（这仅适用于“最短”表示“边权重的最小总和”并且没有负边权重的情况。）
其它你可能感兴趣的问题