[codevs]1077 多源最短路 --- Floyd

题目描述 Description
已知n个点(n<=100),给你n*n的方阵,a[i,j]表示从第i个点到第j个点的直接距离。
现在有Q个询问,每个询问两个正整数,a和b,让你求a到b之间的最短路程。满足a[i,j]=a[j,i];
输入描述 Input Description
第一行一个正整数n,接下来n行每行n个正整数,满足a[i,i]=0,再一行一个Q,接下来Q行,每行两个正整数a和b。
输出描述 Output Description
一共Q行,每行一个整数。
样例输入 Sample Input
3
0 1 1
1 0 3
1 3 0
1
2 3
样例输出 Sample Output
2
1.Floyd算法的简介
Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
2.Floyd的算法流程
按照题目要求,读入数据到3x3的邻接矩阵内

Y0JP04PDS_WO6}M1P2%EY)H.png

在初始化图结构时,需要注意的是,当i=j时,应当设置为0,未特别说明的数据应设置为正无穷。
接着,进入算法核心语句,先从无顶点开始寻找最短的到达路径
也就是0-0的直接路径。根据上图,1-1路径为0。
当前路径大于计算的路径,更新最短路径
floyd算法核心:对于每一对顶点 i 和 j,看看是否存在一个顶点 k 使得从 i 到 k 再到 j 比已知的路径更短。如果是更新它。
e[i][j] = e[i][k] + e[k][j];
...
当经过0-n个顶点的,更新i-j的最短路径,我们得到如下图

input.png

最后,根据题意要求,直接找到最短路径位置输出即可。
具体实现代码如下

#include<iostream>
#include<cstdio>
using namespace std;
int e[1100][1100], k, i, j, n; int a, b;
int inf = 99999999;//用inf(infinity的缩写)存储一个我们认为的正无穷值   
int main() {
    //n*n的矩阵 
    scanf("%d", &n);
    //初始化   
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            if (i == j) e[i][j] = 0;
            else e[i][j] = inf;
            //读入邻接矩阵信息
            for (i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    cin >> e[i][j];
            }
            //Floyd-Warshall算法核心语句   (生成最小路径图)
            for (k = 0; k < n; k++)//附加顶点(1=n)遍历,判断哪个路径短
                for (i =0; i < n; i++)
                    for (j = 0; j < n; j++)
                        if (e[i][j]>e[i][k] + e[k][j])//选择最小值
                            e[i][j] = e[i][k] + e[k][j];//更新较小节点
            //输出最终的结果
            int q;
            cin >> q;
            int s, t;
            for (int i = 1; i <= q; i++) {
                cin >> s >> t;//输入欲查找的最短路径的位置
                printf("%d\n", e[s-1][t-1]);
            }
            return 0;
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 树形动态规划,顾名思义就是树+DP,先分别回顾一下基本内容吧:动态规划:问题可以分解成若干相互联系的阶段,在每一个...
    Mr_chong阅读 1,522评论 0 2
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • 从那以后,我向往大学生活; 从那以后,我知道了西北还有座小江南; 从那以后,我才发现,校园里的女生多是事实,但空气...
    胡子崔阅读 793评论 0 50
  • 对这里的记忆是关于 一个女子和一本经书 和一匹布帛 那个沉睡在大汉盛世的女子 千年的不朽 因情亦或因爱 唯此长久永...
    宁久微初心不改阅读 365评论 0 0
  • 今天给大家讲一则笑话。 前几天在街上,我偶遇一位虽然一直都有电话号码,但从未拨通过的同学。然后不免就多聊了几句,临...
    琴瑟沉香阅读 307评论 0 1