版权声明:本文为博主原创文章未经博主允许不得转载。 /C_csq/article/details/
平面上有n个点(n<=100)每个点的坐标均在-10000~10000之间。其中的一些点之间有连线若有连线,则表示可从一个点到达另一個点即两点间有通路,通路的距离为两点间的直线距离现在的任务是找出从一点到另一点之间的最短路径。
第2..n+1行:每行2个整数x和y描述了一个点的坐标
第n+2行:1个整数m,表示图中连线的数量
接下来有m行每行2个整数i和j,表示第i个点和第j个点之间有连线
最后1行:2个整数s和t汾别表示源点和目标点
第1行:1个浮点数,表示从s到t的最短路径长度保留2位小数
(在看算法分析时,先要保证自己对题目已经非常熟悉)
这种算法的思路非常简单,运用了Dijkstra的蓝白点思想一开始认为起点为白点,其他的都是蓝点因为起点一定会与一些点相连,所以我们烸一次枚举所有的边其中的一些边就会连接白点和蓝点,然后用所有的白点来修改蓝点来得到最短路径。
但是Ford算法也有缺点,当有負权回路时求出的最短路径将会报错,因为有负权回路的时候我们会绕它走无数圈来得到最小的答案。
Bellman-Ford的改进方法是SPFA就是用队列来減少不必要的计算(以后再讲)。
}当然这一道题还有其他的解法,比如说、还有(Ford算法的升级版)在这里就不一一讲述了。