我用队列实现了Bellman-Ford算法的解决方案,并将其与Dijkstra算法进行了性能比较。它们的表现非常接近,这让我感到惊讶,因为Bellman-Ford的复杂度是O(NM)。我知道这个复杂度是针对最坏情况的,但结果仍然令人惊讶。我搜索了一些关于Bellman-Ford的信息,在Sedgewick的《Java算法》中只找到了这样一个说法:“在真实网络中,Bellman-Ford算法通常以线性时间运行”。
你能给我解释一下Bellman-Ford算法的性能行为吗?
你能给我解释一下Bellman-Ford算法的性能行为吗?