精华内容
下载资源
问答
  • 网络图论中floyd算法matlab实现
  • 最短路问题(short-path problem)是网络理论解决的典型问题之一,可用来解决管路铺设、...解决最短路问题的Floyd算法Floyd算法:又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的...

    最短路问题(short-path problem)是网络理论解决的典型问题之一,可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。基本内容是:若网络中的每条边都有一个数值(长度、成本、时间等),则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。

    解决最短路问题的Floyd算法:

    Floyd算法:

    又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。

    算法步骤:

    (1)从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。

    (2)对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是,更新它。把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i][j]=d,d表示该路的长度;否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息,D[i][j]表示从Vi到Vj需要经过的点,初始化D[i][j]=j。把各个顶点插入图中,比较插点后的距离与原来的距离,G[i][j] = min( G[i][j], G[i][k]+G[k][j] ),如果G[i][j]的值变小,则D[i][j]=k。在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。

    例:已知有6个村子,相互间道路如图所示。欲合建一所小学,已知A处有小学生50人,B处40人,C处60人,D处20人,E处70人,F处90人,问学校应建在哪个村子,使得学生上学最方便。

    54688f949a9157ce5bbb729e015149e0.png

    程序代码:

    (1)road函数的m文件:

    functionminroad=road(u,s,begin_node,end_node)

    minroad=[];

    S=s;

    k=S(begin_node,end_node);

    if(k~=begin_node)&&(k~=end_node)

    minroad=[begin_node,k];

    end

    if(k==begin_node)||(k==end_node)

    fprintf('输入错误!');

    end

    while(k~=end_node)

    k=S(k,end_node);

    minroad=[minroad,k];

    end

    end

    (2)Floyd算法的m文件:

    d=[0    2    7    Inf  Inf  Inf

    2    0    4    6    8    Inf

    7    4    0    1    3    Inf

    Inf  6    1    0    1    6

    Inf  8    3    1    0    3

    Inf  Inf  Inf  6    3    0];

    n=length(d);

    U=d;

    S=zeros(n,n);

    fori=1:n

    forj=1:n

    S(i,j)=j;

    end

    end

    fori=1:n

    forj=1:n

    form=1:n

    ifU(i,j)>U(i,m)+U(m,j)

    S(i,j)=S(i,m);

    U(i,j)=U(i,m)+U(m,j);

    end

    end

    end

    end

    people=[50 40 60 20 70 90];

    distance=[inf inf inf inf inf inf];

    fori=1:n

    distance(i)=U(i,:)*people';

    end

    S

    U

    people

    distance

    [min_distance,village]=min(distance)

    begin_node=input('输入起始节点:begin=')

    end_node=input('输入终止节点:end=')

    minroad=road(U,S,begin_node,end_node)

    运行结果:

    >> Floyd

    S =

    1     2     2     2     2     2

    1     2     3     3     3     3

    2     2     3     4     4     4

    3     3     3     4     5     5

    4     4     4     4     5     6

    5     5     5     5     5     6

    U =

    0     2     6     7     8    11

    2     0     4     5     6     9

    6     4     0     1     2     5

    7     5     1     0     1     4

    8     6     2     1     0     3

    11     9     5     4     3     0

    people =

    50    40    60    20    70    90

    distance =

    2130        1670        1070        1040        1050        1500

    min_distance =

    1040

    village =

    4

    输入起始节点:begin=1

    begin_node =

    1

    输入终止节点:end=6

    end_node =

    6

    minroad =

    1     2     3     4     5     6

    综上所述,学校应建在D村,最短路为1040。

    展开全文
  • MATLAB实现Floyd最短路算法

    千次阅读 2020-06-14 10:16:22
    不过,不能用这个算法来构造最短路,同时不能用来计算带有负权回路的最短路。 2.引入 2.1邻接矩阵和路由矩阵 ①邻接矩阵:邻接矩阵的元素即点vi到vj的权值,即A(i,j)=w(i,j); 若vi到vj之间无边相连,则为Inf...

    1.算法作用及适用范围

    可以求出加权连通图(有向图、无向图)中所有顶点之间最短路的长度;不过,不能用这个算法来构造最短路,同时不能用来计算带有负权回路的最短路。

    2.引入

    2.1邻接矩阵和路由矩阵

    ①邻接矩阵:邻接矩阵的元素即点vi到vj的权值,即A(i,j)=w(i,j);
    若vi到vj之间无边相连,则为Inf。

    ②路由矩阵:通俗的解释,路由矩阵的元素实际上就是求vi到vj的传递闭包(前提存在两个点之间的传递闭包)的中间过渡点,其对应的r(i,j)就是过渡点;
    例:路由矩阵
    可以看到,对应元素r(2,1)= 3;我们就可以知道,从2号顶点到1号顶点的路径为2~ 3 ~1;

    2.2代码及注释

    a:初始权值矩阵
    r:路由矩阵
    d:最终结果

    function [d,r]=floyd(a)
    n=size(a,1); %a的行
    d=a;% 初始化距离矩阵
    r=zeros(size(a));% 初始化路由矩阵
    for i=1:n
        for j=1:n
            r(i,j)=j;
        end 
    end 
    % Floyd算法开始
    for k=1:n
        for i=1:n
            for j=1:n
                %(i,j)= min(d(i,j),d(i,k)+d(k,j));%若只需计算最短路矩阵,则可以使用状态转移方程来写
                if d(i,k)+d(k,j)<d(i,j)
                    d(i,j)=d(i,k)+d(k,j);
                    r(i,j)=r(i,k);%等价于求传递闭包,中间过渡的点为k
                end 
            end 
        end
        k;
        d;
        r;
    end
    %a是距离矩阵,也就是各顶点间的距离
    %r是路由矩阵,指的是找到各点之间的最短距离对应的路径,不懂得可以看一下原理
    %例如
    %a=[0 4 11;6 0 2;3 inf 0];
    

    2.3例子及运行结果

    1.初始矩阵
    初始矩阵
    2.结果矩阵
    结果矩阵
    3.路由矩阵
    路由矩阵

    展开全文
  • Floyd算法Matlab实现

    2021-01-24 20:44:49
    计算赋权图的最短路Floyd算法
  • 最短路问题的Floyd算法MATLAB程序实现.pdf
  • 最短路Floyd算法

    2014-04-04 13:32:51
    在计算有环有方向的最短路时,可以用Floyd算法计算出任意两点之间的最短路
  • ( ∞ 表示无直接航路),请帮助该公司设计一张城市 c 1 到其它城市间的票价便宜的路线图。 算法思想: 先从第一项即出发点c1看起。 1.在第一行找从出发点c1到各个目标点的距离,并把距离最小的点记下(该题为...

    题目:
    某公司在六个城市 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实现)

    千次阅读 2021-03-26 16:03:05
    Floyd算法 Folyd算法主要是解决每对顶点之间的最短路径 从直观上进行分析,从任意顶点ViV_iVi​到任意顶点VjV_jVj​的最短路径有两种情况。 从ViV_iVi​直接到VjV_jVj​的距离就是最短路径。 从ViV_iVi​经过...

    Floyd算法

    Folyd算法主要是解决每对顶点之间的最短路径


    从直观上进行分析,从任意顶点 V i V_i Vi到任意顶点 V j V_j Vj的最短路径有两种情况。

    • V i V_i Vi直接到 V j V_j Vj的距离就是最短路径。
    • V i V_i Vi经过若干个顶点到 V j V_j Vj的距离是最短路径。
    function [dist,mypath]=myfloyd(a,sb,db);
    %输入:a——邻接矩阵;元素a(i,j)——顶点i到j之间的直达距离,可以是有向的。
    %sb——起点的标号;db——终点的标号;
    %输出:dist——最短路的距离;mypath——最短路的路径
    
    n=size(a,1);path=zeros(n);
    for k=1:n
    	for i=1:n
    		for j=1:n
    			if a(i,j)>a(i,k)+a(k,j)
    				a(i,j)=a(i,k)+a(k,j);
    				path(i,j)=k;
    			end
    		end
    	end
    end
    dist=a(sb,db);
    parent=path(sb,:);%从起点sb到终点db的最短路上各顶点的前驱顶点
    parent=(parent==0)=sb;%path中的分量为0,表示该顶点的前驱是起点
    mypath=db;t=db;
    while t~=sb
    	p=parent(t);mypath=[p,mypath];
    	t=p;
    end
    
    展开全文
  • Floyd算法及其MATLAB实现

    千次阅读 多人点赞 2020-04-14 16:18:31
    问题介绍:若网络中的每条边都有一个数值(长度、成本、时间等),则找出两节点之间总权和最小的路径就是网络最短路问题。该问题可用来解决管路铺设、...本文主要介绍网络最短路问题的FloydFloydFloyd算法及其MATLABMA...
  • Floyd最短路算法MATLAB程序,数学建模的使用
  • function [d,path]=floyd(a,sp,ep)% floyd - 最短路问题%% Syntax: [d,path]=floyd(a,sp,ep)%% Inputs:% a - 距离矩阵是指i到j之间的距离,可以是有向的% sp - 起点的标号% ep - 终点的标号%% Outputs:% d - 最短路...
  • 所以我决定还是深度解析这个floyd算法Floyd-warshall1.摆出问题先摆出简单问题,给你图,询问a,b求a,b间最短路不会floyd的时候,,我是扎扎实实的对每个点求单源最短路。。。后来学了floyd。。。floyd就是求任意两...
  • 基于 matlabfloyd 算法 matlab 计算最短路径 function [d,path]=floyd(a,sp,ep) % floyd - 最短路问题 % % Syntax: [d,path]=floyd(a,sp,ep) % % Inputs: % a - 距离矩阵是指 i 到 j 之间的距离可以是有向的 % ...
  • 最短路径-Floyd算法matlab实现.md

    万次阅读 多人点赞 2018-09-28 16:56:03
    最短路径-Floyd算法matlab实现 ​ 弗洛伊德算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或有向图或负权(但不可存在负权回路)的最短路径问题。 ​ 在Floyd算法中一般有两个矩阵,一个距离矩阵D...
  • 最短路问题之Floyd算法 最短路性质 算法步骤 例题 Python代码 Matlab代码 最短路性质 在图 GGG中,记 (vi,vj)k(v_i,v_j)_k(vi​,vj​)k​为点 vi,vjv_i, v_jvi​,vj​之间的第 kkk条路径, ∣(vi,vj)k∣|(v_i,v_j)_k...
  • 基于matlab算最短路径--floyd算法.doc 基于matlab算最短路径-----Floyd算法在讲程序之前先看一个例子。例子:如图的交通网络,每条弧上的数字代表车辆在该路段行驶所需的时间。若有一批货物要从1号顶点运往11号顶点...
  • Floyd算法问题的提出:已知一个有向网(或者无向网),对每一对定点vi!=vj,要求求出vi与vj之间的最短路径和最短路径的长度。解决该问题有以下两种方法:(1)轮流以每一个定点为源点,重复执行Dijkstra算法或者Bellman-...
  • 动态规划 - Floyd算法求最短路径 - (Matlab建模)

    万次阅读 多人点赞 2018-07-10 14:59:16
    Floyd算法又称为弗洛伊德算法、插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授...
  • 是关于matlab图论问题求最短路floyd算法实现,还有具体的例题!很好很强大!呵呵。。。
  • Floyd 算法+例题

    千次阅读 2020-07-29 21:43:34
    众所周知,Floyd是来求最短路问题的算法 最短路径问题是图论研究中的一个经典算法问题, 指在寻找图(由结点和路径组成的)中两结点之间的最短路径。 例如: Floyd是用了DP的思想 决策需要枚举中转点,不妨考虑也以...
  • floyd算法matlab实现

    2020-10-23 23:35:01
    floyd算法 经过计算后得到的可行的算法,可以算出任意两点间的最短路程 function [dist,path]=myfloyd(a) %寻找i,j两点最短路径 % 输入:a—邻接矩阵,元素(aij)是顶点i到j之间的直达距离,可以是有向的 % sb—起点...
  • 1 Floyd算法简介及问题发现 Floyd算法作为动态规划的一种应用,通过将两两节点间的完整路径一分为二并遍历所有可能的子路径组合,来得到节点之间的最短路径,其时间复杂度为,空间复杂度为,具体的原理可以参考...
  • Matlab实现的Floyd算法

    2021-04-14 20:22:26
    输入初始距离矩阵,可以计算出最短距离矩阵及最短路由矩阵,并可以展示任意两点间的最短距离及路由
  • 先看看此篇博客,了解常规floyd算法是如何求最短路径的,搞懂D和R的意义,再往后看,否则看不懂 https://blog.csdn.net/kabuto_hui/article/details/82886826 要求所有最短路径,其实很简单。 不管有几条最短路径,...
  • floyd最短路算法

    2009-08-24 09:07:16
    floyd最短路算法 最短路程序
  • 弗洛伊德(Floyd)算法是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 基本思想 通过Floyd计算图G=(V,E)中...
  • MATLAB Floyd算法最短路

    万次阅读 2016-01-26 17:14:56
    在该算法中,我们用邻接矩阵的形式来存储该图。 因为在本次建模过程中,我们已经把数据输入到excel中, 而matlab是可以编程来读取excel和写入excel的。若你的图的 邻接矩阵在txt中,也可以直接将txt拖入excel中读取...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 245
精华内容 98
关键字:

最短路floyd算法matlab

matlab 订阅