任意两点最短路径被称为多源最短路径,即给定任意两个点,一个出发点,一个到达点,求这两个点的之间的最短路径,就是任意两点最短路径问题,多源最短路径,而Floyd-Warshall算法最简单,只有5行代码,即可解决这个问题。
比如三个城市,城市1,城市2,城市3。从城市1到城市3需要10公里,从城市1到城市2需要3公里,从城市2到城市3需要4公里,如下图:
那么从城市1到城市3,如何走更近?1到3是直达,但是却10公里,而1到2到3,虽然转一下,但是距离短了,只要7公里。
这就引出了我们的观念,一个点到另一个点要变短,就要引入第三个点,甚至第四个点,第五个点。
假设在map数组里存储了点i到点j的距离map[i][j],那么我们引入第三个点k,则如果点i到点j的距离比点i到点k加点k到点j,则点i到点j的最短距离是点i到点k加点k到点j。
即如果map[i][j]<map[i][k]+map[k][j],则map[i][j]=map[i][k]+map[k][j]
这就是Floyd-Warshall算法。核心代码如下:
//只能从k中转 for(k=1; k<=cityCount; k++){ //从i出发 for(i=1; i<=cityCount; i++){ //到j结束 for(j=1; j<=cityCount; j++){ if(map[i][j] > (map[i][k] + map[k][j])){ map[i][j] = map[i][k]+ map[k][j]; } } } }
三个for循环,加一个if,加一个赋值,简简单单的五行代码,就实现了任意一个点到任意另一个点的最短距离。
显而易见,时间复杂度是O(n3).
完整代码如下
#include <stdio.h> int map[11][11] = {{0}}; int book[11] = {0}; int main(){ int i, j, k, cityCount, roadCount, length, x, y; scanf("%d %d", &cityCount, &roadCount); for(i=1; i<=cityCount; i++){ for(j=1; j<=cityCount; j++){ map[i][j] = 0; } } for(i=1; i<=roadCount; i++){ scanf("%d %d %d", &x, &y, &length); map[x][y] = length; } //只能从k中转 for(k=1; k<=cityCount; k++){ //从i出发 for(i=1; i<=cityCount; i++){ //到j结束 for(j=1; j<=cityCount; j++){ if(map[i][j] == 0 || map[i][k] == 0 || map[k][j] == 0) continue; if(map[i][j] > (map[i][k] + map[k][j])){ map[i][j] = map[i][k]+ map[k][j]; } } } } //现在的map里就是从一个点i到另一个点j的最短距离map[i][j] printf("点1到点5的最短路径是:%d", map[1][5]); }
输入
5 8
1 2 3
1 3 2
1 5 10
2 3 1
3 5 3
3 4 5
4 5 1
2 4 8
输入,5
友情提示:垃圾评论一律封号...