Mar*_*izh 2 algorithm tree graph dijkstra
我研究贪心算法.总结了Dijkstra算法的一些重要方面,这将是正确的.我怀疑(4)和(1),有人可以帮助我吗？
I)如果所有边缘权重都为负,那么Dijkstra算法效果很好.
II)如果在图中我们有一个负循环,Dijkstra进入一个无限循环而永远不会结束.
III)如果图形具有负权重的一个边缘但没有负周期,则该算法不能很好地工作.
IV)如果图形没有负循环,则算法运行良好.
Pet*_*vaz 5
Dijkstra算法仅适用于具有非负边的图.这是因为它假设第一次从队列中弹出一个节点,我们找到了到该节点的最短路径,一旦你有一个负权重,这就不一定正确.
因此我是假的,II是假的(因为负循环可能不一定是可达的),III是真的,IV是假的(即使没有负循环,它仍然可能有负边缘).
归档时间：
11 年，2 月 前
查看次数：
1746 次
最近记录：