Bellman-Ford算法与另一个非常著名的Dijkstra算法一样,用于求解单源点最短路径问题。Bellman-ford算法除了可求解边权均非负的问题外,还可以解决存在负权边的问题(意义是什么,好好思考),而Dijkstra算法只能处理边权非负的问题,因此 Bellman-Ford算法的适用面要广泛一些。但是,原始的Bellman-Ford算法时间复杂度为 O(VE),比Dijkstra算法的时间复杂度高,所以常常被众多的大学算法教科书所忽略,就连经典的《算法导论》也只介绍了基本的Bellman-Ford算法,…

2015年8月20日 0条评论 10点热度 阅读全文