我研究贪心算法.总结了Dijkstra算法的一些重要方面,这将是正确的.我怀疑(4)和(1),有人可以帮助我吗？
I)如果所有边缘权重都为负,那么Dijkstra算法效果很好.
II)如果在图中我们有一个负循环,Dijkstra进入一个无限循环而永远不会结束.
III)如果图形具有负权重的一个边缘但没有负周期,则该算法不能很好地工作.
IV)如果图形没有负循环,则算法运行良好.
假设我们有一个有向图,每个边都有一个正容量.如果C是正常数,我说,如果我们将C加到或减去所有边缘容量,最大流量就会改变,(可能增加或减少).我的问题是,为什么如果我们将所有边缘容量乘以C,最大流量是C乘积？
为什么这是真的？