用来求解加权有向图的最短路径的算法是什么算法

2024-12-27 19:25:32
推荐回答(1个)
回答1:

单元最短路径:
1.如果没有负权环的稀疏图,可以用SPFA,时间复杂度O(KM)
M是边数,K是平均入队列的次数
2.如果没有负权环的稠密图,建议用Dijkstra O(N^2),用二叉堆可优化到
O(NlogN),斐波那契堆编程复杂度太高,不易于实现
3.如果有负权环,可以尝试floyd,O(n^3)

任两点最短路径:floyd较好实现,基于重标号johnson也不错(稀疏图效率高)
具体程序可以上网查