用来求解加权有向图的最短路径的算法是什么算法
展开全部
单元最短路径：
1.如果没有负权环的稀疏图，可以用SPFA，时间复杂度O（KM）
M是边数，K是平均入队列的次数
2.如果没有负权环的稠密图，建议用Dijkstra O（N^2），用二叉堆可优化到
O（NlogN），斐波那契堆编程复杂度太高，不易于实现
3.如果有负权环，可以尝试floyd,O(n^3)
任两点最短路径：floyd较好实现，基于重标号johnson也不错（稀疏图效率高）
具体程序可以上网查
1.如果没有负权环的稀疏图，可以用SPFA，时间复杂度O（KM）
M是边数，K是平均入队列的次数
2.如果没有负权环的稠密图，建议用Dijkstra O（N^2），用二叉堆可优化到
O（NlogN），斐波那契堆编程复杂度太高，不易于实现
3.如果有负权环，可以尝试floyd,O(n^3)
任两点最短路径：floyd较好实现，基于重标号johnson也不错（稀疏图效率高）
具体程序可以上网查
本回答由提问者推荐
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
