问题标题：
最短路径法如何计算
问题描述：
最短路径法如何计算
李寅东回答：
最短路径算法有三种,Floyd,dijkstra,Bellman_Ford.其中,Floyd适合用于计算每两点间的路径,dijkstra适合稀疏图,bellman则适合稠密图中的已知起点终点,计算最短路径的问题.时间复杂度,floyd算法为n立方,dijk为n平方,bellman为n平方,其中n是点数.dijk可用堆维护,时间复杂度可减至nlogn,而bellman可用队列维护,此方法于1994年被国人提出,命名比较土鳖叫SPFA(shortestpathfasteralgorithm.).至于如何计算,有了名字,搜一下就ok.
查看更多
