西安城乡建设网站,近期网络营销的热点事件,网站备案年限,深圳学校网站建设有多种最短路径的应用场景#xff0c;它们需要用到不同的算法来解决。除了贪心最优搜索之外#xff0c;其他都是最优性算法#xff0c;即得到的解都是最短路径。其中m是边的数量#xff0c;n是点的数量。
问题边权算法时间复杂度一个起点#xff0c;一个终点非负数#…有多种最短路径的应用场景它们需要用到不同的算法来解决。除了贪心最优搜索之外其他都是最优性算法即得到的解都是最短路径。其中m是边的数量n是点的数量。
问题边权算法时间复杂度一个起点一个终点非负数无边权或边权为1A*算法O((mn)logn)双向搜索O((mn)logn)贪心最优搜索O(mn)一个起点到其他所有点无边权或边权为1BFSO(mn)非负数Dijkstra堆优化O((mn)logn)允许有负数SPFAO(mn)所有点对之间允许有负数FloydO(n^3)
应该在不同的场景下有选择地使用。
1图的规模小并且要求多源最短路那么使用Floyd如果边权有负数则需要判断负环。
2图的规模大且边的权值非负用DijkstraSPFA虽然在Bellman-Ford算法上进行了很大的优化但是最坏情况下依然是O(mn)不稳定比赛时有的题目可能故意利用SPFA的不稳定性如果一道题目的图规模很大并且边的权值为非负数它可能会故意设置不利于SPFA的测试数据此时使用SPFA将会超时要使用更稳定的Dijkstra。
3图的规模很大且边的权值有负数用SPFA并且需要判断负环。
