精华内容
下载资源
问答
  • 最短路Floyd算法和Dijkstra算法实验报告1.问题问题实例问题实例2.解析Floyd算法具体步骤Dijkstra算法具体步骤3.设计Floyd算法Dijkstra算法:4.分析Floyd算法Dijkstra算法5.源码 实验报告 课程名称 《算法分析与设计...

    实验报告

    课程名称 《算法分析与设计》
    实验日期 2021年 3月15日
    实验名称 最短路Floyd算法和Dijkstra算法
    实验地点 勤园13-208

    1.问题

    [描述算法问题,首选形式化方式(数学语言),其次才是非形式化方式(日常语言)]

    用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵(顶点之间的最短距离矩阵)
    在这里插入图片描述

    问题

    若∃n个点,m条单向边,设dis[i][j]为i点到j点的距离,使用Floyd算法求各点之间的最短距离,并绘制矩阵。

    实例

    存在4个点,如上图各点之间存在单向路径,使用Floyd算法求取各点之间的最短距离并绘制矩阵。

    对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。
    在这里插入图片描述

    问题

    若∃n个点,m条单向边,设dis[i][j]为i点到j点的距离,使用Dijkstra算法求顶点a到顶点h的最短路径。

    实例

    存在4个点,如上图各点之间存在单向路径,使用Dijkstra算法求顶点a到顶点h的最短路径。

    2.解析

    [问题的理解和推导,可用电子版直接在此编写,也可用纸笔推导,拍照嵌入本文档]

    Floyd算法

    Floyd算法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。对于每一对顶点<u,v>查询是否存在顶点w使得u到w再到v的距离比原本距离更近,并进行状态转移,更新矩阵。在算法问题中,首先绘制路径矩阵记录点与点之间的距离,然后从任一点出发,对于每一对顶点进行查询,设dis[i][j]为i到j的最短距离,那么比较dis[i][j]和dis[i][k]+dis[k][j]即可完成路径压缩,最终实现目标。

    具体步骤

    1.初始化路径矩阵,所有两点之间的距离为边的权值,如果两点之间没有边相连,则权值无穷大。
    2.对于每一对顶点u和v,看看是否存在一个顶点w使得从u到w再到v比已知的路径更短,如果是则更新它。

    在这里插入图片描述

    (以点1为例)

    Dijkstra算法

    Dijkstra算法采用贪心策略,使用数组dis保存初始路径矩阵,数组len来保存源点到各个顶点的最短距离(len[i] = 0),数组path记录路径。从len数组选择最小值,则该值为当前源点到其他点的最短路径,并且把该点加入到path中,然后对其他点进行路径压缩,最后重复步骤。

    具体步骤

    1.初始化路径矩阵,所有两点之间的距离为边的权值,如果两点之间没有边相连,则权值无穷大。
    2.从len数组选择最小值,则该值为当前源点到其他点的最短路径,并且把该点加入到path中,然后对其他点进行路径压缩。
    3.重复步骤2。
    在这里插入图片描述

    3.设计

    [核心伪代码]

    Floyd算法

    E(u,v)为u点到v点的距离;
    For(每一个点k)
    	For(每一个点i)
    		For(每一个点j)
     			IFE(i,j)>E(i,k)+E(k,j))
    				E(i,j)=E(i,k)+E(k,j);
    

    Dijkstra算法

    MST = {s};
    while (1) {
    	V = 未收录顶点中距离最小者;
    	if ( V不存在 )
    		break;
    	elseV收录进MST;
    	V被收录;
    	for ( 每个点 W )
    		if ( W未被收录 )
    			if ( 最短路径到W的距离 <最短路径到V的距离 +VW的距离 ){
    				最短路径到W的距离 <最短路径到V的距离 +VW的距离 ;
    				记录W的前一个点位V}
    }
    

    4.分析

    [算法复杂度推导]

    Floyd算法

    遍历每一个点,总共三层循环,总复杂度为O(N^3)

    Dijkstra算法

    每次找边的时候需要枚举所有点,并且将最小的出边更新,时间复杂度为O(N),共需要重复进行n-1次,找n-1个点,总复杂度为O(N^2)

    5.源码

    [github源码地址]
    链接: github源码地址

    展开全文
  • HDU 2544 最短路 Floyd

    2019-04-07 21:04:55
    HDU 2544 最短路 Floyd 题目:http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?pid=1000&ojid=0&cid=13029&hide=0 Problem Description 在每年的校赛里,所有进入决赛的同学都会获得一件很...

    HDU 2544 最短路 Floyd

    题目:http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?pid=1000&ojid=0&cid=13029&hide=0
    Problem Description
    在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?

    Input
    输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。

    Output
    对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间

    Sample Input
    2 1
    1 2 3
    3 3
    1 2 5
    2 3 5
    3 1 2
    0 0

    Sample Output
    3
    2
    思路:大概就是套模板的,学长比较坑,给我们的pppt有bug ,然后我问了大佬,帮忙解决的,O(∩_∩)O哈哈哈~
    特别要注意的是1-n,而不是0-n…

    #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include <cstring>
    #define maxn 1020
    #define INF 0x3f3f3f3f
    using namespace std;
    int dis[maxn][maxn];
    int n,m;
    void Floyd()
    {
        int i,j,k;
        for(k=1; k<=n; k++)
        {
            for(i=1; i<=n; i++)
            {
                for(j=1; j<=n; j++)
                {
                    dis[i][j]=dis[i][j]<=(dis[i][k]+dis[k][j])?dis[i][j]:(dis[i][k]+dis[k][j]);
                }
            }
        }
    }
    int main()
    {
        int a,b,c;
        int i,j;
        while(scanf("%d %d",&n,&m)!=EOF&&n!=0&&m!=0)
        {
            memset(dis,INF,sizeof(dis));
            for(i=0; i<m; i++)
            {
                scanf("%d %d %d",&a,&b,&c);
                dis[a][b]=c;
                dis[b][a]=c;
            }
            Floyd();
            cout << dis[1][n] << endl;
        }
        return 0;
    }
    
    

    来源:https://i.csdn.net/

    展开全文
  • kuangbin 最短路专题 - POJ - 2240 Arbitrage (最短路 Floyd算法) Floyd原理推荐可以看看这篇:https://blog.csdn.net/m0_46272108/article/details/108919125 感觉没什么好讲的。理解Floyd算法就可以了… 这道...

    kuangbin 最短路专题 - POJ - 2240 Arbitrage (最短路 Floyd算法)

    [kuangbin带你飞] 题单 最短路问题 + 并查集问题模板题及简单题
    https://blog.csdn.net/m0_46272108/article/details/108923142

    在这里插入图片描述
    在这里插入图片描述
    Floyd原理推荐可以看看这篇:https://blog.csdn.net/m0_46272108/article/details/108919125
    感觉没什么好讲的。理解Floyd算法就可以了…
    这道题是:判断图中是否存在变大环
    感觉还可以用其他方法做,下次一定!!!(有空一定更新)

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<cmath>
    #include<algorithm>
    
    #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
    #define ll long long
    //#define int ll
    #define inf 0x3f3f3f3f
    using namespace std;
    int read()
    {
    	int w = 1, s = 0;
    	char ch = getchar();
    	while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); }
    	while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0';    ch = getchar(); }
    	return s * w;
    //最大公约数
    }int gcd(int x,int y) {
        if(x<y) swap(x,y);//很多人会遗忘,大数在前小数在后
        //递归终止条件千万不要漏了,辗转相除法
        return x % y ? gcd(y, x % y) : y;
    }
    int lcm(int x,int y)//计算x和y的最小公倍数
    {
        return x * y / gcd(x, y);//使用公式
    }
    //------------------------ 以上是我常用模板与刷题几乎无关 ------------------------//
    
    const int N = 1010;
    double Map[N][N];
    int n, m,a,b,cnt = 0;
    char money[N][N];
    char money1[N],money2[N];
    //纯floyd 算法
    void floyd()
    {
        
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (Map[i][k] * Map[k][j] > Map[i][j]) {
                        Map[i][j] = Map[i][k] * Map[k][j];
                    }
                }
            }
        }
        
    }
    int main()
    {
        double t;
        while (~scanf("%d",&n) && n) {
            ++cnt;
            memset(Map, inf, sizeof(Map));
            for (int i = 0; i < n; ++i) {
                scanf("%s", money[i]);
                //一开始的汇率为1
                Map[i][i] = 1.0 ;
            }
            int m = read();
            for (int i = 0;i < m; ++i) {
                scanf("%s %lf %s", money1, &t, money2);
                int j;
                for (j = 0; j < n; ++j) {
                    //如果不同就跳
                    if (!strcmp(money1, money[j])) {
                        break;
                    }
                }
                int k;
                for (k = 0 ; k < n; ++k) {
                    //如果不同就跳
                    if (strcmp(money2, money[k]) == 0) {
                        break;
                    }
                }
                Map[j][k] = t;
            }
            int flag = 0;
            floyd();
            for (int i = 0 ; i < n ; ++i) {
                //如果自身汇率大于1,说明可以套利
                if (Map[i][i] > 1.0) {
                    flag = 1 ;
                    break;
                }
            }
            if(flag)
                printf("Case %d: Yes\n",cnt);
            else
                printf("Case %d: No\n",cnt);
        }
        return 0;
    }
    
    展开全文
  • 4图-6多源最短路Floyd

    2018-12-04 14:14:49
    4图-6多源最短路Floyd
    #include<bits/stdc++.h>
    using namespace std;
    int v,e,d[100][100];                //点数,边数,两点间距离
    int main(){
        //距离数组初始化
        for(int i=0;i<100;i++)          //起点
            for(int j=0;j<100;j++)      //终点
                if(i==j)d[i][j]=0;      //到自己距离0
                else d[i][j]=10000;     //距离最大化
        cin>>v,e;                       //输入点数,边数
        for(int i=0;i<v;i++){           //逐个
            int a,b,c;cin>>a>>b>>c;     //读入三个值
            d[a][b]=c;                  //由A点到B点距离为C
        }
        //计算任意两点间最短路
        for(int k=0;k<v;k++)            //中间点
            for(int i=0;i<v;i++)        //起点
                for(int j=0;j<v;j++)    //终点
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);//自更新
        //输出最短距离数组
        for(int i=0;i<v;i++){           //起点
            for(int j=0;j<v;j++)        //终点
                cout<<d[i][j]<<' ';     //距离
            cout<<endl;                 //换行
        }
        return 0;
    }
    /***
    Floyd多源最短路
    证明:对某对ij,中间有几个k就要几轮得出,证完
    ***/
    
    
    展开全文
  • kuangbin 最短路专题 - POJ - 3259 Wormholes (最短路 Floyd算法) Floyd原理推荐可以看看这篇:https://blog.csdn.net/m0_46272108/article/details/108919125 #include<cstdio> #include<iostream>...
  • 最短路Floyd算法

    2014-04-04 13:32:51
    在计算有环有方向的最短路时,可以用Floyd算法计算出任意两点之间的最短路
  • 最短路 Floyd算法 问题描述: 给出一张带权的的图,边的权值可以理解为两点之间的距离。一张图中任意两点间会有不同的路径相连。最短路就是指连接两点的这些路径中最短的一条。 算法思路: Floyd: 一个有n个点,...
  • POJ 3165 最短路 floyd

    2012-07-04 13:45:20
    POJ 3165 最短路 floyd http://poj.org/problem?id=3615 dp方程(f[i][j]>MAX(f[i][k],f[k][j])) f[i][j]=MAX(f[i][k],f[k][j]); 此题为有向图。 n=300 o(n^3)   #include #include #define MAXN 310 ...
  • Floyd 多源最短路
  • 图论 最短路 floyd

    2019-10-01 00:10:55
    任意两点间短距离 每两点间遍历所有节点,更新短距离 复杂度O(n^3) 板子 #include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<...
  • 最短路 floyd模板

    2018-08-03 10:15:32
    多源最短路 简单 但复杂度高  #include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;queue&gt; #...
  • 最短路 floyd 算法模板

    2020-05-10 00:37:59
    设i,j最短路两端点之间最大编号节点为k,设i,k之间最大编号节点为k1,设k,j之间最大节点为k2 那么显然有k>k1且k>k2 而k1和k2在k之前肯定被dp过了 根据数学归纳 初始边界为当i,j之间是原子距离 无中间点时候 视频...
  • 最短路 floyd算法

    2017-04-03 21:49:31
    动态规划#include #include #define max 99999999 #define min(a,b) a(){ int n,m,i,j,a,b,v,k; scanf("%d%d",&n,&m); int dp[n][n]; for(i=0;i;i++){ for(j
  • 网络图论中floyd算法的matlab实现
  • 模板-最短路FLoyd

    2019-03-04 08:34:34
    void floyd(){ for(int k=0;k&lt;n;k++){//遍历中间节点 for(int i=0;i&lt;n;i++){ for(int j=0;j&lt;n;j++){ if(mp[i][j]&gt;mp[i][k]+mp[k][j]){ //如果i-&gt;k-&gt;j比i-&gt;j.....
  • 图论最短路Floyd

    2008-09-12 20:38:10
    用编好的Floyd程序求最短路径,只要画出点和路线,就可以自动计算出最短路径
  • 题目:http://acm.hdu.edu.cn/showproblem.php?pid=2544 代码: #include #include #include using namespace std; #define MAX 0x3f3f3f3f int maps[105][105]; int main() ... while(scanf("%d%d
  • bzoj4956: [Wf2017]Secret Chamber at ...最短路floyd 比较难想到标算 想到了就很简单 可以通过很多次变化来求值 也就是可以有很多个中转点来求起点到终点是否能够到达 不就是floyd的基本思想 #include &...
  • // 最短路floyd算法,复杂度N^3,在求解的点数不超过200个点的时候好用,全源最短路问题,能计算出来每一对点之间的最短路#include &lt;stdio.h&gt;//初始化的方法注意一下//比较的时候是ans[i][j]&gt;...
  • 最短路 Floyd算法

    2015-08-17 22:33:29
    //构造的矩阵函数 #define inf 10000000 class Matrix { public: Matrix(int n);//构造函数 ~Matrix();//析构函数 int row;//矩阵行数与列数 int** p; }; Matrix::Matrix(int n) { row=n;... p=
  • 就是一道Floyd求两点最短路的模板题... 先说一说Floyd吧: 假设有三个点A,B,C,位置如下: A->B就可以选择直接走(AB)或间接走(AC->BC) 由此可以得出一个类似DP的方程:dp[A,B]=min(dp[A,C]+dp[B,C],dp[A,B]); ...
  • 题解 一道深入理解Floyd本质的题目 ...正好对应Floyd算法的思维:求出顶点x到顶点y在前k个时间内的最短路 大佬博客,真的很棒,必看 #include <bits/stdc++.h> using namespace std; co...
  • 最短路Floyd、Dijkstra

    2017-10-11 21:45:47
    floyd() { for ( int k= 1 ;k;k++) //中间点 { for ( int i= 1 ;i;i++) { for ( int j= 1 ;j;j++) { pri[i][j]=min(pri[i][j],pri[i][k]+pri[k][j]); } } } } void dijkstra() { memset ...
  • 原题链接 ... 1: 问从 x 到 y 的最短路(x,y和经过的点都必须被 标记过),如果x,或y没有被标记过输出“ERROR! At path x to y”,如果没有路输出“No such path”。 对于这个题Floyd就非常适用...
  • 裸的Floyd,单纯三重循环,比较好理解 有负权边,一起处理即可。 #include #include #include #include #define ll long long #define ld long double #define INF 0x3f3f3f3f using namespace std; int G[502]...
  • 个人模板 最短路floyd

    2017-03-27 19:03:22
    #include #define inf 0x3f3f3f using namespace std; int a[101][101]; int main() { int m,n; while(scanf("%d%d",&n,&m)==2) ... printf("%d点到%d的短距离为%d%c",i,j,a[i][j],j); } } } }

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,338
精华内容 2,135
关键字:

最短路floyd