精华内容
下载资源
问答
  • floyd算法matlab
    千次阅读
    2021-01-16 16:18:01

    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实现

    2018-12-17 00:48:10
    floyd多源最短路径算法matlab实现,可返回代价图和下一跳图
  • MATLAB中计算已知有向图、邻接矩阵情况下的最短路径
  • 本代码是floyd算法的通用matlab程序,代码写的十分经典,是数模比赛的利器
  • Floyd算法Matlab程序.txt

    2022-05-18 19:14:34
    Floyd算法Matlab程序.txt
  • 基于 matlabfloyd 算法 matlab 计算最短路径 function [d,path]=floyd(a,sp,ep) % floyd - 最短路问题 % % Syntax: [d,path]=floyd(a,sp,ep) % % Inputs: % a - 距离矩阵是指 i 到 j 之间的距离可以是有向的 % ...
  • 【老生谈算法】Dijkstra、Floyd算法Matlab-Lingo实现.docx
  • Floyd算法Matlab实现

    2021-01-24 20:44:49
    计算赋权图的最短路Floyd算法
  • 基于matlabfloyd算法 matlab计算最短路径.doc
  • matlab
  • FLOYD算法 MATLAB程序

    2013-03-12 16:36:46
    数学建模中最短路径问题必备算法MATLAB语言编写
  • Dijkstra、Floyd算法Matlab_Lingo实现.doc
  • 这是图论中用来求解有向赋权图最短路径的Floyd算法Matlab文件,已经封装成了函数,函数接口在代码中有说明。
  • Floyd算法matlab程序

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

    2014-05-14 20:37:20
    基于MATLABFloyd算法,计算网络中任意结点间的最小距离!
  • 是关于matlab图论问题求最短路的floyd算法实现,还有具体的例题!很好很强大!呵呵。。。
  • Floyd最短路径算法MATLAB程序,经过测试
  • MATLAB】最短路径Floyd算法

    千次阅读 多人点赞 2021-07-31 11:41:36
    代码2.1floyd函数2.2调用函数 1.Floyed算法 1.1适用范围 ∙\bullet∙ 求每队顶点的最短路径 ∙\bullet∙ 有向图、无向图和混合图 1.2算法思想 直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D...



    1.Floyed算法

    1.1适用范围

    ∙ \bullet 求每队顶点的最短路径

    ∙ \bullet 有向图、无向图和混合图

    1.2算法思想

    直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1),D(2)…D(n)(每次加入一个点然后更新最短路径矩阵D),D(n)是图的最短距离矩阵,同时引入一个后继点矩阵path记录两点间的最短路径。

    1.3实例

    对于如下无向图:
    在这里插入图片描述
    我们可以得如下带权邻接矩阵:
    [ 0 7 9 i n f i n f 14 7 0 10 15 i n f i n f 9 10 0 11 i n f 2 i n f 15 11 0 6 i n f i n f i n f i n f 6 0 9 14 i n f 2 i n f 9 0 ] \begin{bmatrix} 0 & 7 & 9 & inf & inf & 14\\ 7 & 0 & 10 &15 & inf & inf\\ 9 & 10 & 0 & 11 & inf & 2\\ inf & 15 & 11 & 0 & 6 & inf\\ inf & inf & inf & 6 & 0 & 9\\ 14 & inf & 2 & inf & 9 & 0\\ \end{bmatrix} 079infinf14701015infinf910011inf2inf151106infinfinfinf60914inf2inf90


    实现步骤

    ∙ \bullet 变量:输入变量与输出变量

    输入变量含义
    w矩阵带权邻接矩阵
    start初始点
    terminal终止点
    输出变量含义
    D矩阵D(i,j)表示i到j的最短路径
    path矩阵path(i,j)表示i到j之间的最短路径上顶点i的后继点
    min1start与terminal之间的最短距离
    path1start与terminal之间的最短路径

    ∙ \bullet 赋初值:对所有的i、j, D ( i , j ) = w ( i , j ) , p a t h ( i , j ) = j , k = 1 ( k 表 示 加 入 的 顶 点 个 数 ) D(i,j)=w(i,j),path(i,j)=j,k=1(k表示加入的顶点个数) D(i,j)=w(i,j),path(i,j)=j,k=1(k)

    ∙ \bullet 更新D(i,j)、path(i,j),对于所有i、j,若 D ( i , k ) + D ( k , j ) < D ( i , j ) D(i,k)+D(k,j)<D(i,j) D(i,k)+D(k,j)<D(i,j)
    则: D ( i , j ) = D ( i , k ) + D ( k , j ) , p a t h ( i , j ) = p a t h ( i , k ) , k = k + 1 D(i,j)=D(i,k)+D(k,j), path(i,j)=path(i,k),k=k+1 D(i,j)=D(i,k)+D(k,j),path(i,j)=path(i,k),k=k+1

    ∙ \bullet 每次插入一个顶点重复进行更新操作,直到 k=n+1 终止。


    2.代码

    2.1floyd函数

    function [D,path,min1,path1]=floyd(a,start,terminal)
    %D(i,j)表示i到j的最短路径,path(i,j)表示i到j之间的最短路径上顶点i的后继点。
    %min1返回start和terminal之间的最短距离,path1返回start和terminal之间的最短路径
    %a为带权邻接矩阵,start、terminal分别是起始点和终止点
    
    D=a;n=size(D,1);path=zeros(n,n);
    %n为顶点个数,生成D、path矩阵
    
    %遍历一遍矩阵,初始化path矩阵,先将可以直接相连的点的path进行补充
    for i=1:n
        for j=1:n
            if D(i,j)~=inf
                path(i,j)=j;
            end  
        end
    end
    
    %三重遍历,查找是否有中继点可以使得路径缩短,若有则更新D、path矩阵
    for k=1:n
        for i=1:n
            for j=1:n
                if D(i,k)+D(k,j)<D(i,j)
                    D(i,j)=D(i,k)+D(k,j);
                    path(i,j)=path(i,k);
                end 
            end
        end
    %这里演示了每一步的调整过程
    k,D,path
    end
    
    %判断输出参数是否为三个
    if nargin==3
        min1=D(start,terminal);
        m(1)=start;
        i=1;
        path1=[ ];   
        %根据path路径一步一步跳转找到具体路径,返回path1
        while   path(m(i),terminal)~=terminal
            k=i+1;                                
            m(k)=path(m(i),terminal);
            i=i+1;
        end
        m(i+1)=terminal;
        path1=m;
    end   
    
    
    

    2.2调用函数

    w = [0,7,9,inf,inf,14;
         7,0,10,15,inf,inf;
         9,10,0,11,inf,2;
         inf,15,11,0,6,inf;
         inf,inf,inf,6,0,9;
         14,inf,2,inf,9,0];
     start=1;terminal=5;
    [D,path,min,path1]=floyd(w,start,terminal);
    D,path,min,path1
    

    结果
    在这里插入图片描述
    这里介绍一下如何看path矩阵查找最短路径:比如说要查找1到5的最短路径

    ∙ \bullet 那么我们就要找 path(1,5)=3,所以目前路径为1->3

    ∙ \bullet 接着我们就要找 path(3,5)=6,所以目前路径为1->3->6

    ∙ \bullet 接着我们就要找 path(6,5)=5,到达终点,所以最终路径为1->3->6->5

    注意:调用floyd函数的时候,同时还会输出每次插入一个顶点之后D矩阵和path矩阵的变化。



    展开全文
  • Floyd算法及其MATLAB实现

    万次阅读 多人点赞 2020-04-14 16:18:31
    问题介绍:若网络中的每条边都有一个数值(长度、成本、时间...常用算法:FloydFloydFloyd算法、DijkstraDijkstraDijkstra算法、SPFASPFASPFA算法等。 本文主要介绍网络最短路问题的FloydFloydFloyd算法及其MATLABMA...

    一、最短路问题

    1、定义
    • P ( u , v ) P(u,v) P(u,v)是网络加权图中从结点 u u u v v v的路径,该路径上的边权之和称为该路径的权,记为 W ( P ) W(P) W(P)。从结点 u u u v v v的路径中边权最之和小者 P ∗ ( u , v ) P^*(u,v) P(u,v)称为 u u u v v v的最短路径。
    2、用途
    • 最短路问题(short-path problem)是网络理论解决的典型问题之一,其基本内容是:若网络中的每条边都有一个数值(长度、成本、时间等),则找出两结点(通常是源结点和阱结点)之间总权和最小的路径就是最短路问题。该问题可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。
    3、常用算法
    • 最短路问题常用的算法有Floyd算法、Dijkstra算法、SPFA算法等。本文主要介绍网络最短路问题的Floyd算法及其MATLAB实现。

    二、理论准备

    1、网络弧集和权矩阵

    为了论述方便,本文借助下图,介绍网络弧集 E E E和网络权矩阵 W W W的概念。
    网络图
    (上述网络图上标的数字为各段弧的权值,该图左侧为无向网络图,右侧为有向网络图。)
    对于上述无向网络图而言,网络弧集 E 1 = [ ( v 1 , v 2 ) , ( v 1 , v 4 ) , ( v 2 , v 1 ) , ( v 2 , v 4 ) , ( v 2 , v 3 ) , ( v 3 , v 2 ) , ( v 3 , v 4 ) , ( v 4 , v 1 ) , ( v 4 , v 2 ) , ( v 4 , v 3 ) ] E_1=[(v_1,v_2),(v_1,v_4),(v_2,v_1),(v_2,v_4),(v_2,v_3),\\(v_3,v_2),(v_3,v_4),(v_4,v_1),(v_4,v_2),(v_4,v_3)] E1=[(v1,v2),(v1,v4),(v2,v1),(v2,v4),(v2,v3),(v3,v2),(v3,v4),(v4,v1),(v4,v2),(v4,v3)]
    对于上述有向网络图而言,网络弧集 E 2 = [ ( v 1 , v 2 ) , ( v 1 , v 4 ) , ( v 2 , v 3 ) , ( v 2 , v 4 ) , ( v 3 , v 4 ) ] E_2=[(v_1,v_2),(v_1,v_4),(v_2,v_3),(v_2,v_4),(v_3,v_4)] E2=[(v1,v2),(v1,v4),(v2,v3),(v2,v4),(v3,v4)]
    由此可见,集合 E E E就是网络图的所有弧集合。
    网络权矩阵 W = ( W i j ) n × n W=(W_{ij})_{n×n} W=(Wij)n×n,其中,
    ( v i , v j ) ∈ E (v_i,v_j)∈ E (vi,vj)E时, W i j = L i j W_{ij}=L_{ij} Wij=Lij L i j L_{ij} Lij为弧 ( v i , v j ) (v_i,v_j) (vi,vj)的权;
    W i i = 0 , i = 1 , 2 , … , n W_{ii}=0,i=1,2,…,n Wii=0,i=1,2,,n;
    ( v i , v j ) ∉ E (v_i,v_j)∉E (vi,vj)/E i ≠ j i≠j i=j时, W i j = i n f W_{ij}=inf Wij=inf,( i n f inf inf为无穷大, n n n为网络节点个数)
    则按上述规定,上面无向网络图和有向网络图的权矩阵分别为
    W 1 = [ 0 4 i n f 5 4 0 3 5 i n f 3 0 2 5 5 2 0 ] W_1=\begin{bmatrix} 0 & 4 & inf & 5 \\ 4 & 0 & 3 & 5 \\ inf & 3 & 0 & 2 \\ 5 & 5 & 2 & 0\end{bmatrix} W1=04inf54035inf3025520
    W 2 = [ 0 4 i n f 5 i n f 0 3 1 i n f i n f 0 2 i n f i n f i n f 0 ] W_2=\begin{bmatrix} 0 & 4 & inf & 5 \\ inf & 0 & 3 & 1 \\ inf & inf & 0 & 2 \\ inf & inf & inf & 0 \end{bmatrix} W2=0infinfinf40infinfinf30inf5120
    由于上述网络图均只有4个结点,故网络的权矩阵均为4阶矩阵。

    2、Floyd算法
    1.使用范围

    ①求任意两结点的最短路径;
    ②有向图、无向图、混合图。

    2.基本思想

    直接在网络图的权矩阵 W W W中用插入顶点的方法依次递推地构造出 n n n个矩阵 D ( 1 ) , D ( 2 ) , … , D ( n ) D(1),D(2),…,D(n) D(1)D(2)D(n) D ( n ) D(n) D(n)是网络图的最短距离矩阵,同时引入一个路由矩阵记录任意两点之间的最短路径。

    3.算法步骤

    D i j D_{ij} Dij为结点 v i v_i vi v j v_j vj的距离; P i j P_{ij} Pij为结点 v i v_i vi v j v_j vj路径上 v i v_i vi的后继点; W W W为权矩阵。

    • 第1步: ∀ i , j , D i j = W i j , P i j = j , k = 1 {\forall}i,j,D_{ij}=W_{ij},P_{ij}=j,k=1 ijDij=Wij,Pij=jk=1;(赋初值)
    • 第2步: ∀ i , j , 若 D i k + D k j < D i j {\forall}i,j,若D_{ik}+D_{kj}<D_{ij} ijDik+Dkj<Dij,则 D i j = D i k + D k j , P i j = P i k , k = k + 1 D_{ij}=D_{ik}+D_{kj},\\P_{ij}=P_{ik},k=k+1 Dij=Dik+DkjPij=Pikk=k+1;(更新 D , P D,P DP)
    • 第3步:重复第2步,直到 k = n + 1 k=n+1 k=n+1

    三、实例求解

    1、程序实现

    下面给出一个例子,网络图如下:
    在这里插入图片描述
    可以看出,上图为无向网络图,其结点个数 n = 7 n=7 n=7,权矩阵为:
    W = [ 0 4 6 5 i n f i n f i n f 4 0 1 i n f 7 i n f i n f 6 1 0 2 5 4 i n f 5 i n f 2 0 i n f i n f i n f i n f 7 5 i n f 0 1 6 i n f i n f 4 5 1 0 8 i n f i n f i n f i n f 6 8 0 ] W=\begin{bmatrix} 0 & 4 & 6 & 5 & inf & inf & inf \\ 4 & 0 & 1 & inf & 7 & inf & inf \\ 6 & 1 & 0 & 2 & 5 & 4 & inf \\ 5 & inf & 2 & 0 & inf & inf & inf \\ inf & 7 & 5 & inf & 0 & 1 & 6 \\ inf & inf & 4 & 5 &1 & 0 & 8 \\ inf & inf & inf & inf &6 & 8 & 0 \end{bmatrix} W=0465infinfinf401inf7infinf610254inf5inf20inf5infinf75inf016infinf4inf108infinfinfinf680

    下面利用MATLAB编写程序求其最短距离矩阵、路由矩阵以及任给两结点之间的最短距离和路径。

    %% FileName:Floyd.m
    %% Date:2020-4-13
    %% Writer:Yida
    %% Function:输出网络图的最短距离矩阵和路由矩阵,指定两结点间的最短距离及其路径
    
    %%
    function [D, P, dis, path] = Floyd(W, start, stop) %start为指定起始结点,stop为指定终止结点
    D = W; %最短距离矩阵赋初值
    n = length(D); %n为结点个数
    P = zeros(n,n); %路由矩阵赋初值
    
    for i = 1:n
        for j = 1:n
            P(i,j) = j;
        end
    end
    
    for k = 1:n
        for i = 1:n
            for j = 1:n
                if D(i,k) + D(k,j) < D(i,j)
                    D(i,j) = D(i,k) + D(k,j);   %核心代码
                    P(i,j) = P(i,k);
                end
            end
        end
    end
                      
    if nargin ~= 3
        errordlg('参数个数输入有误!', 'Warning!')
    else
        dis = D(start, stop); %指定两结点间的最短距离
        m(1) = start;
        i = 1;
    
        while P(m(i),stop) ~= stop
            k = i + 1;
            m(k) = P(m(i),stop);
            i = i + 1;
        end
        m(i+1) = stop;
        path = m; %指定两结点之间的最短路径
    end
    %%
    

    调用上述函数求该网络图的最短距离矩阵,并确定结点 v 1 v_1 v1 v 7 v_7 v7的最短距离对应的路径,程序如下:

    W = ones(7) * inf; %权矩阵初始化
    for i = 1:7
        W(i,i) = 0;
    end
    W(1,2) = 4; W(1,3) = 6; W(1,4) = 5;
    W(2,1) = 4; W(2,3) = 1; W(2,5) = 7;
    W(3,1) = 6; W(3,2) = 1; W(3,4) = 2; W(3,5) = 5; W(3,6) = 4;
    W(4,1) = 5; W(4,3) = 2; W(4,6) = 5;
    W(5,2) = 7; W(5,3) = 5; W(5,6) = 1; W(5,7) = 6;
    W(6,3) = 4; W(6,4) = 5; W(6,5) = 1; W(6,7) = 8;
    W(7,5) = 6; W(7,6) = 8; %修改元素后W为权矩阵
    
    pre_path = {'v1', 'v2', 'v3', 'v4', 'v5', 'v6', 'v7'}; %本例中网络图结点
     
    start = 1; %起始节点为v1
    stop = 7; %终止结点为v7
    
    [D, P, dis, path] = Floyd(W, start, stop); %调用函数求解
    fprintf('\n最短距离矩阵 D =\n\n')
    disp(D)
    fprintf('\n路由矩阵 P =\n\n')
    disp(P)
    fprintf('结点%s到%s的最短距离为:%f\n\n', pre_path{start}, pre_path{stop}, dis)
    
    fprintf('结点%s到%s的最短路径为:\n\n', pre_path{start}, pre_path{stop}) %输出两给定结点间的最短路径
    
    for i = 1:length(path)-1
        fprintf('%s', pre_path{path(i)})
        fprintf(' -> ')
    end
    fprintf('%s.\n', pre_path{path(length(path))})
    

    程序运行结果如下:

    
    最短距离矩阵 D =
    
         0     4     5     5    10     9    16
         4     0     1     3     6     5    12
         5     1     0     2     5     4    11
         5     3     2     0     6     5    12
        10     6     5     6     0     1     6
         9     5     4     5     1     0     7
        16    12    11    12     6     7     0
    
    
    路由矩阵 P =
    
         1     2     2     4     2     2     2
         1     2     3     3     3     3     3
         2     2     3     4     5     6     5
         1     3     3     4     6     6     6
         3     3     3     6     5     6     7
         3     3     3     4     5     6     5
         5     5     5     5     5     5     7
    
    结点v1到v7的最短距离为:16.000000
    
    结点v1到v7的最短路径为:
    
    v1 -> v2 -> v3 -> v5 -> v7.
    

    由程序运行结果知,该无向网络图的最短距离矩阵为:
    D = [ 0 4 5 5 10 9 16 4 0 1 3 6 5 12 5 1 0 2 5 4 11 5 3 2 0 6 5 12 10 6 5 6 0 1 6 9 5 4 5 1 0 7 16 12 11 12 6 7 0 ] D=\begin{bmatrix} 0&4&5&5&10&9&16 \\ 4&0&1&3&6&5&12 \\ 5&1&0&2&5&4&11 \\ 5&3&2&0&6&5&12 \\ 10&6&5&6&0&1&6 \\ 9&5&4&5&1&0&7 \\ 16&12&11&12&6&7&0 \end{bmatrix} D=04551091640136512510254115320651210656016954510716121112670
    结点 v 1 v_1 v1 v 7 v_7 v7的最短距离为16,其最短路径为: v 1 − > v 2 − > v 3 − > v 5 − > v 7 v_1->v_2->v_3->v_5->v_7 v1>v2>v3>v5>v7

    2、一个思考

    值得注意的是,上述由结点 v 1 v_1 v1 v 7 v_7 v7的最短距离确实为16,但是,由 v 1 v_1 v1 v 7 v_7 v7的最短距离对应的路径却不止一条(另一条为: v 1 − > v 2 − > v 3 − > v 6 − > v 5 − > v 7 v_1->v_2->v_3->v_6->v_5->v_7 v1>v2>v3>v6>v5>v7),这是为什么呢?让我们回到上述算法步骤第2步,要求 ∀ i , j , 若 D i k + D k j < D i j {\forall}i,j,若D_{ik}+D_{kj}<D_{ij} ijDik+Dkj<Dij,则 D i j = D i k + D k j D_{ij}=D_{ik}+D_{kj} Dij=Dik+Dkj,而 D 35 = 5 , D 36 = 4 , D 65 = 1 , 所 以 D 35 = D 36 + D 65 , D_{35}=5,D_{36}=4,D_{65}=1,所以D_{35}=D_{36}+D_{65}, D35=5D36=4D65=1D35=D36+D65但是,由于此时 P 35 = 5 P_{35}=5 P35=5,而不能改为 P 35 = 6 P_{35}=6 P35=6,所以在程序运行结果的最短路径中没有结点 v 6 v_6 v6。由此可见,上述算法只能确定一条最短路径,如果某两结点之间的最短路径不止一条,该算法并不能完全找出。那么,是不是任意两结点之间必定有一条最短路径呢?答案是否定的,下面给出一个反例。

    3、一个反例

    下图就不存在1号顶点到3号顶点的最短路径,因为在 1 − > 2 − > 3 − > 1 − > 2 − > 3 − > … 1 − > 2 − > 3 1->2->3->1->2->3->…1->2->3 1>2>3>1>2>3>1>2>3这样的路径中,每绕一次 1 − > 2 − > 3 1->2->3 1>2>3这样的环,最短路径就会减少1,永远找不到最短路径。所以,Floyd算法不能解决带有"负权回路"(或者叫"负权环")的网络图,因为带有"负权回路"的网络图没有最短路径。
    在这里插入图片描述

    结束语:本文根据理解编写,如有错误或不妥之处,请指正!

    声明:更详细介绍请看本人简文弗洛伊德(Floyd)算法详解 | MATLAB实现

    觉得不错?关注一下,点个赞呗!

    展开全文
  • Floyd算法matlab实现

    2012-08-24 15:39:48
    Floyd算法matlab实现 经调试 可实现 Floyd算法 matlab
  • 求最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd
  • 网络图论中floyd算法matlab实现
  • Dijkstra、Floyd算法Matlab,Lingo代码的实现。
  • 最短路问题的Floyd算法MATLAB程序实现.pdf
  • MATLAB 图论 Dijkstra算法以及Floyd算法

    千次阅读 2020-07-22 22:17:12
    Dijkstra算法代码来源于 作者:无名小卒...Floyd算法,来源于 小石老师课程资源 视频学习 Dijkstra算法原理 https://www.bilibili.com/video/BV1QK411V7V4?from=search&seid=16592423916000157660 Floyd算法原理 ...

    Dijkstra算法代码来源于 作者:无名小卒1990

    Floyd算法,来源于 小石老师课程资源

    视频学习

    Dijkstra算法原理

    https://www.bilibili.com/video/BV1QK411V7V4?from=search&seid=16592423916000157660

    Floyd算法原理

    https://www.bilibili.com/video/BV1Mt411x7CH?t=594&p=6

    Dijkstra

    在这里插入图片描述

    例如上图,从D出发,到各点的距离:

    D[5 9 inf 0 15 6 inf], (ACDEFG排序)

    找出矩阵D[ ]中最小的值,离D最近的是A节点,再从A节点出发,到B节点的

    距离为7,而5+7>9,所以D[5 9 inf 0 15 6 inf]不需要更新。A节点标记已经遍

    历,并给其赋值为inf,即D[inf 9 inf 0 15 6 inf]。

    继续重复找出矩阵D[ ]中最小值,重复上述操作,直到所有节点都遍历过。

    Dijkstra源程序:

    主函数 tulun1.m

    weight = input('please enter the weight:');
    start = input('please enter the start:');
    terminal = input('please enter the terminal:');
              [dis, path]= Dijk(weight,start, terminal)
    

    Dijkstra函数 Dijk.m

    %% Dijkstra算法函数
    function [ distance path] = Dijk( W,st,e )
    %DIJK Summary of this function goes here
    %   W  权值矩阵   st 搜索的起点   e 搜索的终点
    n=length(W);%计算节点数
    D = W(st,:);%记录起点到各点距离,此时,为初始时刻,起点到各点的距离
    visit= ones(1:n); %设置visit判断节点是否访问
    visit(st)=0;  %我称其为预遍历
    parent = zeros(1,n);%记录每个节点的上一个节点
    path =[]; %用于记录路径
    for i=1:n-1 %将除了起点之外的节点都遍历一遍
        temp = []; %用于存储矩阵D的数据,并将距离本为0的换成inf,即无穷大,以免后面求最小值时,出现问题
    %% 从起点出发,找最短距离的下一个点,每次不会重复原来的轨迹,设置visit判断节点是否访问
        for j=1:n
           if visit(j)
               temp =[temp D(j)]; %如果换成temp = [D(j)],将只能存储一个数据,即循环一次,数据变一次
           else
               temp =[temp inf];
           end
        end
     [value,index] = min(temp); %求temp的最小值以及最小值的位置
    
     visit(index) = 0;
        
    %% 更新 如果经过index节点,从起点到每个节点的路径长度更小,则更新,记录前趋节点,方便后面回溯循迹
    %比如从起点(1,1)出发,到达(1,2)最短距离为L1,再从(1,2)找(2,3),(2,4)的距离分别为L2、L3,若L1+L2小于从(1,1)直达(1,3)的距离,则更新
        for k=1:n
            if D(k)>D(index)+W(index,k)
               D(k) = D(index)+W(index,k);
               parent(k) = index;
            end
        end
    end
    
    %% 以下为获取最短距离,及获得路径
    
    distance = D(e);%最短距离
    %回溯法  从尾部往前寻找搜索路径
    t = e;
    while t~=st && t>0
     path =[t,path];
      p=parent(t);t=p;
    end
    path =[st,path];%最短路径
    end
    

    输入:
    计算从D点到C点的最短路径

    [0 7 inf 5 inf inf inf;
    7 0 8 9 7 inf inf;
    inf 8 0 inf 5 inf inf;
    5 9 inf 0 15 6 inf;;
    inf 7 5 15 0 8 9;
    inf inf inf 6 8 0 11;
    inf inf inf inf 9 11 0]

    起点:4
    终点:3

    输出结果:
    在这里插入图片描述

    Floyd算法

    依旧以上图为例
    在这里插入图片描述
    邻接矩阵

    描述的是,各个节点之间的直接距离,如若没有直接距离,则为inf(无穷大),到自己的距离为0;
    在这里插入图片描述

    路由矩阵

    描述的是节点到另一个节点的路径,需要经过的路径。
    在这里插入图片描述
    如上图,如果,需要找从A点到F点的距离,按照ABCDEF排序,A为1,F为

    6,则看path(1,6)的值,为4,到达第四节点,则从第四个节点找,即从第四

    行找path(4,6),其值为6,则可知到达第六节点,即到达F节点,故其路径为

    A——D——F

    那么问题就在于如何求路由矩阵

    Floyd 被称为“ 3 * for ”算法,即 用3个for循环求得,至于原理咋样,看一下代

    码,自己理解一下,推理一下,大概就能了解,主要是在这解释有点麻烦。

    Floyd源代码

    主程序 tulun2.m

    function [D,path,min1,path1]=floyd(a,start,terminal)
    D=a;n=size(D,1);path=zeros(n,n);
    for i=1:n
       for j=1:n
          if D(i,j)~=inf
             path(i,j)=j; %初始路由矩阵
          end
       end
    end
    %% 3*for 程序的开始
    
    for k=1:n
       for i=1:n
          for j=1:n
             if D(i,k)+D(k,j)<D(i,j)
                D(i,j)=D(i,k)+D(k,j);
                path(i,j)=path(i,k);
             end
          end
       end
    end
    
    %% 计算最短距离,以及查找最短路径
       min1=D(start,terminal);
       m(1)=start;
       i=1;
       path1=[ ];   
       while   path(m(i),terminal)~=terminal
          k=i+1;                                
          m(k)=path(m(i),terminal);
          i=i+1;
       end
       m(i+1)=terminal;
       path1=m;
    

    输入:
    计算从D点到C点的最短路径

    [0 7 inf 5 inf inf inf;
    7 0 8 9 7 inf inf;
    inf 8 0 inf 5 inf inf;
    5 9 inf 0 15 6 inf;;
    inf 7 5 15 0 8 9;
    inf inf inf 6 8 0 11;
    inf inf inf inf 9 11 0]

    起点:4
    终点:3

    输出

    在这里插入图片描述

    展开全文
  • 学校留了数模作业,让我们用Floyd算法求解最短路径问题,算法本身很简单,但是这个输出路径我看了很多文章都没有好好具体的写出来怎么输出,无非就是给一个路径矩阵放那里了。这里放一个我自己写的算法, ...
  • 首先用Floyd算法求出距离矩阵,在考虑出警次数和人口密度的前提下找出已知距离图的15个重心点,数值最小点即为新建消防站点。若要在2021-2029年每隔3年新建1个消防站,则根据所求的15个顶点从最优到次优进行排序...
  • 资源名:Floyd算法_floyd最短路算法_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有一定...
  • 详解floyd算法 及<MATLAB>实现

    千次阅读 多人点赞 2019-05-09 16:13:12
    function [D,path,min1,path1]=floyd(a,start,terminal) % a 邻接矩阵 start 起始点 terminal 终点 % D为得到的距离矩阵 path 路径矩阵 min1 最小距离 path1 路径 D=a;n=size(D,1);path=zeros(n,n); for i=1:n for...

空空如也

空空如也

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

floyd算法matlab

matlab 订阅