精华内容
下载资源
问答
  • 网络图论中floyd算法matlab实现
  • 弗洛伊德(Floyd)算法是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 基本思想 通过Floyd计算图G=(V,E)中...

    弗洛伊德(Floyd)算法是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。


    基本思想

         通过Floyd计算图G=(V,E)中各个顶点的最短路径时,需要引入一个矩阵S,矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。

         假设图G中顶点个数为N,则需要对矩阵S进行N次更新。初始时,矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值;如果i和j不相邻,则a[i][j]=∞。 接下来开始,对矩阵S进行N次更新。第1次更新时,如果"a[i][j]的距离" > "a[i][0]+a[0][j]"(a[i][0]+a[0][j]表示"i与j之间经过第1个顶点的距离"),则更新a[i][j]为"a[i][0]+a[0][j]"。 同理,第k次更新时,如果"a[i][j]的距离" > "a[i][k]+a[k][j]",则更新a[i][j]为"a[i][k]+a[k][j]"。更新N次之后,操作完成!

         matlab代码函数如下:

    function [dist,mypath]=myfloyd(a,sb,db);
    % 输入:a—邻接矩阵(aij)是指i 到j 之间的距离,可以是有向的
    % sb—起点的标号;db—终点的标号
    % 输出:dist—最短路的距离;% mypath—最短路的路径
    n=size(a,1); path=zeros(n);
    for i=1:n
    for j=1:n
    if a(i,j)~=inf
    path(i,j)=j; %j 是i 的后续点
    end
    end
    end
    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)=path(i,k);
    end
    end
    end
    end
    dist=a(sb,db);
    mypath=sb; t=sb;
    while t~=db
    temp=path(t,db);
    mypath=[mypath,temp];
    t=temp;
    end
    return
    

      

    转载于:https://www.cnblogs.com/renqiqiang/p/5791225.html

    展开全文
  • Floyd算法Matlab实现

    2021-01-24 20:44:49
    计算赋权图的最短路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程序,数学建模的使用
  • 基于 matlabfloyd 算法 matlab 计算最短路径 function [d,path]=floyd(a,sp,ep) % floyd - 最短路问题 % % Syntax: [d,path]=floyd(a,sp,ep) % % Inputs: % a - 距离矩阵是指 i 到 j 之间的距离可以是有向的 % ...
  • 代码来源:《图论算法及其matlab实现》(北京航空航天出版社) P22 此代码返回第一个点和最后一个点之间最短路径,以及最短路径的长度。... 4 %u表示最短路的权和 5 n=length(W); 6 U=W; 7 ...

    代码来源:《图论算法及其matlab实现》(北京航空航天出版社)

    P22

     

     

     

    此代码返回第一个点和最后一个点之间最短路径,以及最短路径的长度。

    代码如下:

     

     1 function [P,u ] = Floyd(W)
     2 %W表示权值矩阵
     3 %P表示最短路径
     4 %u表示最短路的权和
     5 n=length(W);
     6 U=W;
     7 m=1;
     8 
     9 while m<=n   %判断是否满足停止条件
    10     for i=1:n
    11         for j=1:n
    12             if U(i,j)>U(i,m)+U(m,j)
    13                 U(i,j)=U(i,m)+U(m,j);   %更新dij
    14             end
    15         end
    16     end
    17     m=m+1;
    18 end
    19 u=U(1,n);
    20 
    21 %输出最短路的顶点
    22 P1=zeros(1,n);
    23 k=1;
    24 P1(k)=n;
    25 V=ones(1,n)*inf;
    26 kk=n;
    27 while kk~=1
    28     for i=1:n
    29         V(1,i)=U(1,kk)-W(i,kk);
    30         if V(1,i)==U(1,i)
    31             P1(k+1)=i;
    32             kk=i;
    33             k=k+1;
    34         end
    35     end
    36 end
    37 k=1;
    38 wrow=find(P1~=0);
    39 for j=length(wrow):(-1):1
    40     P(k)=P1(wrow(j));
    41     k=k+1;
    42 end                               
    43 
    44 end

    验证:

    n=12;
    a=ones(n)+inf;
    for i=1:n
    a(i,i)=0;
    end
    a(1,2)=5;
    a(2,3)=8;
    a(2,6)=5;
    a(3,4)=3;
    a(3,9)=10;
    a(4,5)=5;
    a(4,7)=3;
    a(5,6)=2;
    a(7,8)=2;
    a(8,9)=4;
    a(8,11)=6;
    a(9,10)=3;
    a(10,11)=5;
    a(10,12)=3;
    
    [P u ] = Floyd(a)

    运行结果:

    P =
    
         1     2     3     9    10    12
    
    
    u =
    
        29

     

    转载于:https://www.cnblogs.com/this-is-bbh/p/7475748.html

    展开全文
  • 是关于matlab图论问题求最短路floyd算法实现,还有具体的例题!很好很强大!呵呵。。。
  • 引言在研究路径选择和流量分配等交通问题时,常常会用到最短路算法。用最短路算法解决交通问题存在两个难点:一、算法的选择和程序的编写。最短路算法有很多种改进算法和启发式算法,这些算法的效率不同,适用的网络...

    引言

    在研究路径选择和流量分配等交通问题时,常常会用到最短路算法。用最短路算法解决交通问题存在两个难点:

    一、算法的选择和程序的编写。最短路算法有很多种改进算法和启发式算法,这些算法的效率不同,适用的网络也不相同。

    二、构建一个算例网络很简单,但由于实际路网具有高度复杂性,因此将真实的拓扑路网导入最短路算法变得困难。

    4f9fc5847b44d34bf650ef88c8a55c34.png

    本期介绍floyd算法,并分享一些思路和实战案例。


    Floyd算法是一个经典的动态规划算法。是解决任意两点间的最短路径(称为多源最短路径问题)的一种算法,可以正确处理有向图或负权的最短路径问题。

    算法思想:

    从任意节点i到任意节点j的最短路径只2种可能:

    (1)直接从节点i到节点j;

    (2)从节点i经过若干个节点k到节点j。

    所以,我们假设arcs(i,j)为节点i到节点j的最短路径的距离,对于每一个节点k,我们检查arcs(i,k) + arcs(k,j) < arcs(i,j)是否成立。如果成立,则从节点i到节点k再到节点j的路径比节点i直接到节点j的路径短。设置arcs(i,j) = arcs(i,k) + arcs(k,j),当遍历完所有节点k时,arcs(i,j)中记录的便是节点i到节点j的最短路径的距离。

    实例分析:

    构建一个名为dijkstra()的函数,其功能是用floyd算法计算最短路。函数的参数分别设置为路网连通图(graph)、起点(start)和终点(end)。由于floyd算法解决的是所有点只间的最短路径。因此,最后六行代码特地用于计算任意给定OD间的最短路径。

    def floyd(graph, start, end):
        points = len(graph)
        # 初始化一个空矩阵用来存放所经过的节点
        prior = [[0 for i in range(points)] for j in range(points)]   
        for i in range(points):
            for j in range(points):
                prior[i][j] = j
    
        for m in range(points):      # i相当于是中间点
            for i in range(points):      # j相当于是起始点
                for j in range(points):      # m相当于是终点
                    if (graph[i][j] > graph[i][m] + graph[m][j]):
                        graph[i][j] = graph[i][m] + graph[m][j]
                        prior[i][j] = prior[i][m]
                    else:
                        continue
        # 添加中间节点导出路径
        x = prior[start][end]
        roads = [x]
        while (prior[x][end] != end):
            x = prior[x][end]
            roads.append(prior[x][end])
        return graph[start][end], roads
    

    在简单的算例网络上测试一下我们的代码!

    我们构造一个包含6个节点和9条边的算例网络。输入起点和终点(用空格隔开),用dijkstra算法计算最短路,并输出最短路径和最短距离的代码如下:

    在简单的算例网络上测试一下我们的代码!

    我们构造一个包含6个节点和9条边的算例网络。输入起点和终点(用空格隔开),用dijkstra算法计算最短路,并输出最短路径和最短距离的代码如下:

    fcbccb4e5e314d259c401369c28ca0cb.png
    # 定义路网连通图
    _ = float('inf')  # 定义不可达距离
    graph=[[_, 2, _, 4, 7, _],
           [_, _, 2, _, 5, _],
           [_, _, _, _, _, 3],
           [_, _, _, _, 4, _],
           [_, _, 3, _, _, 1],
           [_, _, _, _, _, _],
           ]
    # 输入起点和终点
    r, s = input("输入起点和终点:").split()
    dis, road = dijkstra(graph, int(r), int(s))
    # 输出最短路结果
    print("最短路径:", road)
    print("最短距离:", dis)
    

    程序的运行结果如下:

    >>>
    输入起点和终点:0 5
    最短路径: [0, 1, 2, 5]
    最短距离: 7
    >>>
    输入起点和终点:1 5
    最短路径: [1, 2, 5]
    最短距离: 5
    >>>
    输入起点和终点:3 5
    最短路径: [3, 4, 5]
    最短距离: 5
    

    Floyd算法适用于计算多源最短路径 (All Pairs Shortest Paths,APSP),是一种动态规划算法,在稠密图中的效果最佳,边权可正可负。此算法简单有效,由于三重循环结构紧凑,对于稠密图的效率要高于Dijkstra算法。但由于该算法的时间复杂度比较高,因此不适合计算大量数据。

    下期为大家介绍如何在北京市地铁线路图上运行最短路算法!

    展开全文
  • Matlab_Floyd算法求解最短路

    千次阅读 2019-06-06 20:15:50
    最短路问题(short-path problem)是网络理论解决的典型问题之一,可用来解决管路铺设、线路安装、厂区布局和设备...解决最短路问题的Floyd算法Floyd算法: 又称为插点法,是一种利用动态规划的思想寻找给定的...
  • 参数都一样,这个改了一下能算出两点之间所有的最短路,算复杂网络的时候用到的,改了半天,算出的路由矩阵是cell,path给出一个每列记录一条路径,列数等于最短路数的矩阵,如果一个如果一条最短路经过的点较少,就...
  • MATLAB Floyd算法最短路

    万次阅读 2016-01-26 17:14:56
    在该算法中,我们用邻接矩阵的形式来存储该图。 因为在本次建模过程中,我们已经把数据输入到excel中, 而matlab是可以编程来读取excel和写入excel的。若你的图的 邻接矩阵在txt中,也可以直接将txt拖入excel中读取...
  • 不过,不能用这个算法来构造最短路,同时不能用来计算带有负权回路的最短路。 2.引入 2.1邻接矩阵和路由矩阵 ①邻接矩阵:邻接矩阵的元素即点vi到vj的权值,即A(i,j)=w(i,j); 若vi到vj之间无边相连,则为Inf...
  • Floyd算法 Floyd算法

    2010-10-28 19:34:49
    中国数学建模-数学工具-Floyd最短路算法MATLAB程序 wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> Matlab,Mathematica,maple,几何画板,word,sas,spss......
  • floyd算法matlab实现

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

    2011-03-18 00:16:56
    MATLAB 实现floyd最短路算法
  • Floyd算法及其MATLAB实现

    千次阅读 多人点赞 2020-04-14 16:18:31
    问题介绍:若网络中的每条边都有一个数值(长度、成本、时间等),则找出两节点之间总权和最小的路径就是网络最短路问题。该问题可用来解决管路铺设、...本文主要介绍网络最短路问题的FloydFloydFloyd算法及其MATLABMA...
  • Matlab实现的Floyd算法

    2021-04-14 20:22:26
    输入初始距离矩阵,可以计算出最短距离矩阵及最短路由矩阵,并可以展示任意两点间的最短距离及路由
  • Floyd最短路

    2018-01-03 17:11:22
    Floyd最短路matlab算法,经典的运筹学问题。hiuhoojjljljpiojupo
  • Floyd算法

    2014-06-17 09:11:06
    求图中任意两点间的最短路径(Floyd算法,Matlab程序) Floyd算法描述: 设A = (aij )n×n为赋权图G = (V, E, F)的权矩阵, dij表示从vi到vj点的距离, rij表示从vi到vj点的最短路中一个点的编号.   ①赋初值. ...
  • 内容来源:《图论算法及其matlab实现》(北京航空航天出版社) P34 【算法用途】 求图中两顶点间的最大可靠路。 代码如下: 1 %最大可靠路的算法 2 %调用Floyd文件 3 function [P p f]=...
  • Matlab十大算法

    2018-09-03 20:54:50
    十大算法\Floyd算法\中国数学建模-数学工具-Floyd最短路算法的MATLAB程序.txt 十大算法\免疫算法.txt 十大算法\分治算法 十大算法\分治算法\c程序.txt 十大算法\分治算法\中国数学建模-编程交流-分治算法_1.txt ...
  • 实验8 最短路的求解成 绩实验类型:◆验证性实验 ◇综合性实验 ◇设计性实验实验目的:学会使用Matlab求解最短路。实验内容:1.Floyd算法;2.利用Matlab编程实现最短路的计算。例:已知有6个村子,相互间道路如图所...
  • Matlab_图论一些算法

    2013-10-24 23:20:01
    计算有向图的可达矩阵 两点间最短路的Dijkstra算法 关联矩阵和邻接矩阵相互转换 Floyd算法 Kruskal算法 Prim算法 求联通图最短距离矩阵 等
  • 各种常见算法问题的代码总结,全部是用matlab语言编写。代码包括:Floyd最短路算法、hamilton回路、背包问题_遗传算法解决、旅行商TSP问题、最小费用流、聚类分析等等。
  • 文章目录1 二分图1.1 最大匹配1.2 最优匹配2 网络流2.1 最大流2.2 最小费用最大流3 最短路3.1 Dijkstra3.2 Floyd3.3 Ford4 最小生成树 1 二分图 1.1 最大匹配 %图论二部图最大匹配匈牙利算法 m=5;%X中有5个元素 n=5;...
  • 文章目录实验目的:学会使用Matlab求解最短路。实验内容:1.Floyd算法;2.利用Matlab编程实现最短路的计算。需要word文件请关注该公众号,回复对应内容即可。 实验目的:学会使用Matlab求解最短路。 实验内容:1....

空空如也

空空如也

1 2
收藏数 36
精华内容 14
关键字:

最短路floyd算法matlab

matlab 订阅