精华内容
下载资源
问答
  • Floyd算法matlab实现

    2012-08-24 15:39:48
    Floyd算法matlab实现 经调试 可实现 Floyd算法 matlab
  • 基于 matlabfloyd 算法 matlab 计算最短路径 function [d,path]=floyd(a,sp,ep) % floyd - 最短路问题 % % Syntax: [d,path]=floyd(a,sp,ep) % % Inputs: % a - 距离矩阵是指 i 到 j 之间的距离可以是有向的 % ...
  • Floyd算法Matlab实现

    2021-01-24 20:44:49
    计算赋权图的最短路Floyd算法
  • floyd算法matlab实现

    2018-12-17 00:48:10
    floyd多源最短路径算法matlab实现,可返回代价图和下一跳图
  • Dijkstra、Floyd算法Matlab,Lingo代码的实现。
  • 网络图论中floyd算法matlab实现
  • floyd算法MATLAB实现

    2021-01-16 16:18:01
    floyd算法,简单的来说,就是算出n个点任意两个点之间的最短距离,类似于三角形任意两边之和大于第三边,画了个图,(图咋不好看,注意领会精神) 然后就可以,算出从a到b的所有距离,留下最优的那一组(即最小的...

    floyd算法,简单的来说,就是算出n个点任意两个点之间的最短距离,类似于三角形任意两边之和大于第三边,画了个图,(图咋不好看,注意领会精神)

    cc

    然后就可以,算出从a到b的所有距离,留下最优的那一组(即最小的)储存,同样,a和c以及b和c之间的距离也可以输出,最后就可以得到3x3的一个矩阵(3个地点,主对角线为自己到自己的距离),以此类推,当n个点时原理相同。

    function [S, P]=FloydSPR(AdjMax)
    N=min(length(AdjMax(:,1)),length(AdjMax(1,:)));
    P=-1*ones(N,N);
    S=AdjMax;
    for k=1:N
        for i=1:N
            for j=1:N
                if S(i,k)==inf
                    continue;
                end
                if S(k,j)==inf
                    continue;
                end
                if S(i,j)>S(i,k)+S(k,j)
                    if P(i,k)==-1
                        P(i,j)=k;
                    else
                        P(i,j)=P(i,k);
                    end
                    S(i,j)=S(i,k)+S(k,j);
                end
            end
        end
    end

     

    展开全文
  • 本代码是floyd算法的通用matlab程序,代码写的十分经典,是数模比赛的利器
  • Floyd算法matlab程序

    2011-08-14 02:00:29
    Floyd算法适用于APSP(All Pairs Shortest Paths),是一种动态规划算法,稠密图效果最佳,边权可正可负。此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra算法。
  • FLOYD算法 MATLAB程序

    2013-03-12 16:36:46
    数学建模中最短路径问题必备算法MATLAB语言编写
  • 是关于matlab图论问题求最短路的floyd算法实现,还有具体的例题!很好很强大!呵呵。。。
  • Floyd算法问题的提出:已知一个有向网(或者无向网),对每一对定点vi!=vj,要求求出vi与vj之间的最短路径和最短路径的长度。解决该问题有以下两种方法:(1)轮流以每一个定点为源点,重复执行Dijkstra算法或者Bellman-...

    Floyd算法

    问题的提出:已知一个有向网(或者无向网),对每一对定点vi!=vj,要求求出vi与vj之间的最短路径和最短路径的长度。

    解决该问题有以下两种方法:

    (1)轮流以每一个定点为源点,重复执行Dijkstra算法或者Bellman-Ford算法n次,就可以求出每一对顶点之间的最短路径和最短路径的长度,总的时间复杂度为O(n^3)。

    (2)采用Floyd算法,时间复杂度也是O(n^3),但是形式更为直接。

    1.介绍

    floyd算法只有五行代码,代码简单,三个for循环就可以解决问题,所以它的时间复杂度为O(n^3),可以求多源最短路问题。

    2.思想:

    Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎2种可能,1是直接从A到B,2是从A经过若干个节点X到B。所以,我们假设Dis(AB)为节点A到节点B的最短路径的距离,对于每一个节点X,我们检查Dis(AX) + Dis(XB) 

    举个例子:已知下图,

    87bd620b3ec2bcf8aeac8decfa83add5.png

    如现在只允许经过1号顶点,求任意两点之间的最短路程,只需判断e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。e[i][1]+e[1][j]表示的是从i号顶点先到1号顶点,再从1号顶点到j号顶点的路程之和。其中i是1~n循环,j也是1~n循环,代码实现如下。

    1 for(i=1; i<=n; i++)2 {3 for(j=1; j<=n; j++)4 {5 if ( e[i][j] > e[i][1]+e[1][j] )6 e[i][j] = e[i][1]+e[1][j];7 }8 }

    接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。在只允许经过1号顶点时任意两点的最短路程的结果下,再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短。即判断e[i][2]+e[2][j]是否比e[i][j]要小,代码实现为如下。

    1 //经过1号顶点

    2 for(i=1; i<=n; i++)3 for(j=1; j<=n; j++)4 if (e[i][j] > e[i][1]+e[1][j])5 e[i][j]=e[i][1]+e[1][j];6 //经过2号顶点

    7 for(i=1; i<=n; i++)8 for(j=1; j<=n; j++)9 if (e[i][j] > e[i][2]+e[2][j])10 e[i][j]=e[i][2]+e[2][j];

    最后允许通过所有顶点作为中转,代码如下:

    1 for(k=1; k<=n; k++)///Floyd-Warshall算法核心语句

    2 {3 for(i=1; i<=n; i++)4 {5 for(j=1; j<=n; j++)6 {7 if(map[i][j]>map[i][k]+map[k][j] )8 {9 map[i][j]=map[i][k]+map[k][j];10 }11 }12 }13 }

    这段代码的基本思想就是:最开始只允许经过1号顶点进行中转,接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转,求任意两点之间的最短路程。与上面相同

    3.代码模板:

    1 #include

    2 #define inf 0x3f3f3f3f

    3 int map[1000][1000];4 intmain()5 {6 int k,i,j,n,m;///n表示顶点个数,m表示边的条数

    7 scanf("%d %d",&n,&m);8 for(i=1; i<=n; i++)///初始化

    9 {10 for(j=1; j<=n; j++)11 {12 if(i==j)13 map[i][j]=0;14 else

    15 map[i][j]=inf;16 }17 }18 inta,b,c;19 for(i=1; i<=m; i++)///有向图

    20 {21 scanf("%d %d %d",&a,&b,&c);22 map[a][b]=c;23 }24 for(k=1; k<=n; k++)///Floyd-Warshall算法核心语句

    25 {26 for(i=1; i<=n; i++)27 {28 for(j=1; j<=n; j++)29 {30 if(map[i][j]>map[i][k]+map[k][j] )31 {32 map[i][j]=map[i][k]+map[k][j];33 }34 }35 }36 }37 for(i=1; i<=n; i++)///输出最终的结果,最终二维数组中存的即使两点之间的最短距离

    38 {39 for(j=1; j<=n; j++)40 {41 printf("%10d",map[i][j]);42 }43 printf("\n");44 }45 return 0;46 }

    展开全文
  • 题目: 某公司在六个城市 c 1 , c 2 , L , c 6 中有分公司,从 c i 到 c ...算法思想: 先从第一项即出发点c1看起。 1.在第一行找从出发点c1到各个目标点的距离,并把距离最小的点记下(该题为城市c6最小,距离为1...

    题目:
    某公司在六个城市 c 1 , c 2 , L , c 6 中有分公司,从 c i 到 c j 的直接航程票价记在
    下述矩阵的 ( i , j ) 位置上。
    ( ∞ 表示无直接航路),请帮助该公司设计一张城市 c 1 到其它城市间的票价最便宜的路线图。
    在这里插入图片描述
    Dijkstra算法思想:
    先从第一项即出发点c1看起。
    1.在第一行找从出发点c1到各个目标点的距离,并把距离最小的点记下(该题为城市c6最小,距离为10)
    2.在城市c6出发,查找从c6到各个目标城市的距离,并将c1到c6的路程(10)加上,对比直接从c1到各个城市的距离,将较小值放入第一行中。
    3.再回到第一行,除去第一起始点c1,将c6作为起始点,回到第一步,重复步骤,知道遍历所有点。

    代码(来自姜守奎——数学建模算法与应用):

    clc,clear
    a=zeros(6);
    a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10;
    a(2,3)=15;a(2,4)=20;a(2,6)=25;
    a(3,4)=10;a(3,5)=20;
    a(4,5)=10;a(4,6)=25;
    a(5,6)=55;
    a=a+a';
    a(a==0)=inf;
    pb(1:length(a))=0;pb(1)=1;
    index1=1;index2=ones(1,length(a));
    d(1:length(a))=inf;d(1)=0;
    temp=1;
    while sum(pb)<length(a)
        tb=find(pb==0);
        d(tb)=min(d(tb),d(temp)+a(temp,tb));
        tmpb=find(d(tb)==min(d(tb)));
        temp=tb(tmpb(1));
        pb(temp)=1;
        index1=[index1,temp];
        temp2=find(d(index1)==d(temp)-a(temp,index1));
        index2(temp)=index1(temp2(1));
    end
    d,index1,index2
    

    Floyd算法思想
    每次以不同顶点作为顶点,重复使用Dijkstra算法算出每个顶点之间最短距离
    形象的理解成画十字架:

    在这里插入图片描述
    然后矩阵中的点在这个十字架上取对应的两点之和

    若和比原数小,则替换
    重复以上几步,直至遍历整个矩阵

    EG:第二个十字架
    在这里插入图片描述

    展开全文
  • Floyd算法matlab程序)
  • floyd算法-matlab

    2020-08-05 20:01:41
    floyd算法-matlab 对582*582的距离矩阵进行查找最优路径 path = zeros(size(data,1),size(data,1)); for v = 1:582 for i = 1:582 for j = 1:582 if dis(i,j)>dis(i,v)+dis(v,j) dis(i,j) = dis(i,v)+dis(v,...

    floyd算法-matlab


    对582*582的距离矩阵进行查找最优路径

    path = zeros(size(data,1),size(data,1));
    for v = 1:582
        for i = 1:582
            for j = 1:582
                if dis(i,j)>dis(i,v)+dis(v,j)
                    dis(i,j) = dis(i,v)+dis(v,j);
                    path(i,j) = v;
                end
            end
        end
    end
    

    遍历输出路径

    function[add] = findmin(u,v,path,add,dis)
    
        add = add+dis(u,v);
        if path(u,v) == 0
            disp([num2str(u),'-',num2str(v),'-']);
        else
           
            mid = path(u,v);
            findmin(u,mid,path,add,dis);
            findmin(mid,v,path,add,dis);
        end
            
    end
    
    展开全文
  • 这是图论中用来求解有向赋权图最短路径的Floyd算法Matlab文件,已经封装成了函数,函数接口在代码中有说明。
  • Floyd算法_MATLAB

    2019-09-22 07:19:04
    2 %floyd算法通用程序,输入a为赋权邻接矩阵 3 %输出为距离矩阵D,和最短路径矩阵path 4 5 function D=floyd(a) 6 n=size(a,1);%行数 7 D=a; 8 path=zeros(n,n);%全0阵n*n 9 10 for k=1:n 11 fo.....
  • Floyd弗洛伊德算法matlab仿真代码。跑过几遍,代码是可以运行的,下载后可以直接在matlab打开运行。
  • 最短路径-Floyd算法matlab实现.md

    万次阅读 多人点赞 2018-09-28 16:56:03
    最短路径-Floyd算法matlab实现 ​ 弗洛伊德算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或有向图或负权(但不可存在负权回路)的最短路径问题。 ​ 在Floyd算法中一般有两个矩阵,一个距离矩阵D...
  • floyd算法matlab实现

    2020-10-23 23:35:01
    floyd算法 经过计算后得到的可行的算法,可以算出任意两点间的最短路程 function [dist,path]=myfloyd(a) %寻找i,j两点最短路径 % 输入:a—邻接矩阵,元素(aij)是顶点i到j之间的直达距离,可以是有向的 % sb—起点...
  • Floyd算法及其MATLAB实现

    千次阅读 多人点赞 2020-04-14 16:18:31
    问题介绍:若网络中的每条边都有一个数值(长度、成本、时间...常用算法:FloydFloydFloyd算法、DijkstraDijkstraDijkstra算法、SPFASPFASPFA算法等。 本文主要介绍网络最短路问题的FloydFloydFloyd算法及其MATLABMA...
  • Floyd算法 算出距离矩阵、路由矩阵,很好使 Matlab中运行
  • floyd算法+matlab计算,对数学建模爱好者有很大的好处~~~~
  • 最短路问题(short-path problem)是网络理论解决的典型问题之一,可用来解决管路铺设、...解决最短路问题的Floyd算法Floyd算法:又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的...
  • matlab实现的floyd算法

    2010-03-29 11:30:10
    matlab实现的floyd算法,matlab实现的floyd算法
  • function [D,R]=floyd(A) %用floyd算法实现求任意两点之间的最短路程可以有负权 %参数D为连通图的权矩阵 % A=[0 2 8 1 inf inf inf inf % 2 0 6 inf 1 inf inf inf % 8 6 0 7 5 1 2 inf % 1 inf 7 0 inf inf 9 inf %...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 185
精华内容 74
关键字:

floyd算法matlab

matlab 订阅