精华内容
下载资源
问答
  • 图的最短路径算法matlab实现(Dijkstra算法、Floyd算法、Bellman-Ford算法、Johnson 算法)
    千次阅读 多人点赞
    2020-02-02 20:26:26

    图的最短路径算法

    Dijkstra算法

    Dijkstra算法研究的是从初始点到其他任一结点的最短路径,即单源最短路径问题,其对图的要求是不存在负权值的边。

    Dijkstra算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

    举例说明:

    已知图的邻接矩阵为
    [ 0 50 ∞ 40 25 10 50 0 15 20 ∞ 25 ∞ 15 0 10 20 ∞ 40 20 10 0 10 25 25 ∞ 20 10 0 55 10 25 ∞ 25 55 0 ] \left[\begin{array}{cccccc} {0} & {50} & {\infty} & {40} & {25} & {10} \\ {50} & {0} & {15} & {20} & {\infty} & {25} \\ {\infty} & {15} & {0} & {10} & {20} & {\infty} \\ {40} & {20} & {10} & {0} & {10} & {25} \\ {25} & {\infty} & {20} & {10} & {0} & {55} \\ {10} & {25} & {\infty} & {25} & {55} & {0} \end{array}\right] 050402510500152025150102040201001025252010055102525550
    行向量 pb 、 index1、 index2 、d 分别用来存放 P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值,其中
    p b ( i ) = { 1  当i顶点已标号  0  当i顶点未标号  p b(i)=\left\{\begin{array}{ll} {1} & { \text { 当i顶点已标号 } } \\ {0} & {\text { 当i顶点未标号 } } \end{array}\right. pb(i)={10 i顶点已标号  i顶点未标号 
    $index2(i) $存放始点到第i 点最短通路中第i 顶点前一顶点的序号

    d(i)存放由始点到第i 点最短路的长度。

    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(find(a==0))=inf; %将a=0的数全部替换为无强大               
    pb(1:length(a))=0;pb(1)=1;  %当一个点已经求出到原点的最短距离时,其下标i对应的pb(i)赋1
    index1=1; %存放存入S集合的顺序
    index2=ones(1,length(a)); %存放始点到第i点最短通路中第i顶点前一顶点的序号
    d(1:length(a))=inf;d(1)=0;  %存放由始点到第i点最短通路的值
    temp=1;  %temp表示c1,算c1到其它点的最短路。
    while sum(pb)<length(a)  %看是否所有的点都标记为P标号
    tb=find(pb==0); %找到标号为0的所有点,即找到还没有存入S的点
    d(tb)=min(d(tb),d(temp)+a(temp,tb));%计算标号为0的点的最短路,或者是从原点直接到这个点,又或者是原点经过r1,间接到达这个点
    tmpb=find(d(tb)==min(d(tb)));  %求d[tb]序列最小值的下标
    temp=tb(tmpb(1));%可能有多条路径同时到达最小值,却其中一个,temp也从原点变为下一个点
    pb(temp)=1;%找到最小路径的表对应的pb(i)=1
    index1=[index1,temp];  %存放存入S集合的顺序
    temp2=find(d(index1)==d(temp)-a(temp,index1));
    index2(temp)=index1(temp2(1)); %记录标号索引
    end
    d, index1, index2
    

    运算结果为:

    
    d =
    
         0    35    45    35    25    10
    
    
    index1 =
    
         1     6     5     2     4     3
    
    
    index2 =
    
         1     6     5     6     1     1
    

    Floyd算法

    弗洛伊德算法是解决图中任意两点间的最短路径的一种算法,可以正确处理有向图的最短路径问题。

    Floyd算法要求不可存在负权回路。在Floyd算法中一般有两个矩阵,一个距离矩阵D,一个路由矩阵R,其中距离矩阵用于存储任意两点之间的最短距离,而路由矩阵则记录任意两点之间的最短路径信息。

    其思想是:任意两点间的路径存在中转和不中转两种情况,如果可以从一个点进行中转,就进行比较从这个点中转和不中转的距离,存储距离小的情况,并更新距离矩阵和路由矩阵

    从算法思想中可以发现我们要遍历n个中转点,在每个中转点进行操作的时候,需要对任意两点之间的距离进行遍历。那么算法就应该有三重循环,第一重循环是遍历中转点,第二重和第三重循环是遍历任意两个点之间的距离。而更新距离矩阵的条件就是
    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 ) D(i,j)=D(i, K)+D(K, j) D(i,j)=D(i,K)+D(K,j)

    这个时候就需要更新我们的路由矩阵: R ( i , j ) = R ( i , K ) R(i,j)=R(i,K) R(i,j)=R(i,K)

    路由矩阵很好理解,比如最开始是 R ( 4 , 3 ) = 3 R(4,3) = 3 R(4,3)=3,表示V4到V3一步就可以到达V3,如果现在可以从V2中转到达,那么 R ( 4 , 3 ) = R ( 4 , 2 ) = 2 R(4,3) = R(4,2) =2 R(4,3)=R(4,2)=2,表示V4->V3​要先经过V2才能到达。

    因此,我们就可以给出代码:

    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
    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
    if nargin==3
        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;
    end
    

    依然使用刚才的矩阵:

    a = [0,50,inf,40,25,10;
        50,0,15,20,inf,25;
        inf,15,0,10,20,inf;
        40,20,10,0,10,25;
        25,inf,20,10,0,55;
        10,25,inf,25,55,0];
    %不相连的顶点间距离设为无穷远
    [D,path]=floyd(a)
    

    可获得结果为:

    D =
    
         0    35    45    35    25    10
        35     0    15    20    30    25
        45    15     0    10    20    35
        35    20    10     0    10    25
        25    30    20    10     0    35
        10    25    35    25    35     0
    
    
    path =
    
         1     6     5     5     5     6
         6     2     3     4     4     6
         5     2     3     4     5     4
         5     2     3     4     5     6
         1     4     3     4     5     1
         1     2     4     4     1     6
    

    Bellman-Ford算法

    Dijkstra算法是处理单源最短路径的有效算法,但它局限于边的权值非负的情况,若图中出现权值为负的边,Dijkstra算法就会失效,求出的最短路径就可能是错的。此时,Bellman-Ford算法就是一种可行的方法。

    给定图G(V, E)(其中V、E分别为图G的顶点集与边集),源点s,数组Distant[i]记录从源点s到顶点i的路径长度,初始化数组Distant[n]为inf, Distant[s]为0;

    以下操作循环执行至多n-1次,n为顶点数:
    对于每一条边e(u, v),如果Distant[u] + w(u, v) < Distant[v],则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值;
    若上述操作没有对Distant进行更新,说明最短路径已经查找完毕,或者部分点不可达,跳出循环。否则执行下次循环;

    为了检测图中是否存在负环路,即权值之和小于0的环路。对于每一条边e(u, v),如果存在Distant[u] + w(u, v) < Distant[v]的边,则图中存在负环路,即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

    Bellman-Ford算法可以大致分为三个部分
    第一,初始化所有点。每一个点保存一个值,表示从原点到达这个点的距离,将原点的值设为0,其它的点的值设为无穷大(表示不可达)。
    第二,进行循环,循环下标为从1到n-1(n等于图中点的个数)。在循环内部,遍历所有的边,进行松弛计算。
    第三,遍历途中所有的边(e(u,v)),判断是否存在这样情况:
    d ( v ) > d ( u ) + w ( u , v ) d(v) > d (u) + w(u,v) dv>d(u)+w(u,v)
    若存在,则返回错误,表示途中存在从源点可达的权为负的回路。

    以下给出代码实现:

    function Bellman_Ford(d,n,s)
    %d为已知图的邻接矩阵,n为顶点数(各顶点标号为1,2,...,n),s为源点标号
    for i=1:n %初始化dist,pre
        dist(i)=inf; %dist(i)为s,i之间的最短路的长度
        pre(i)=NaN; %pre(i)为s到i的最短路上i的前一个顶点
    end
    dist(s)=0;
    for k=1:n-1
        for i=1:n 
            for j=1:n
                if d(i,j)~=inf
                    if dist(j)>dist(i)+d(i,j)
                        dist(j)=dist(i)+d(i,j);
                        pre(j)=i;
                    end
                end
            end
        end
    end
    for i=1:n
        for j=1:n
            if d(i,j)~=inf
                if dist(i)+d(i,j)<dist(j)%判断有无负权回路
                    error('Negetive WeightCircut');
                end
            end
        end
    end
    dist
    pre
    end
    
    clc;clear
    w=[0 -2 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;...
          8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;...
          inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0];
    i=1;m=8;
    
    Bellman_Ford(w,m,i)
    

    输出结果为:

    dist =
    
         0    -2     1     3    -1     2     5     8
    
    
    pre =
    
       NaN     1     1     6     2     5     4     5
    

    如果在其中添加负权回路

    clc;clear
    w=[0 -2 1 -8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;
          8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;
          inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0];
    i=1;m=8;
    
    Bellman_Ford(w,m,i)
    

    输出为

    错误使用 Bellman_Ford (line 24)
    Negetive WeightCircut
    

    Johnson 算法

    Johnson算法主要用于求稀疏图上的全源最短路径,可以处理存在负权的图,其主体思想是利用重赋权值的方法把一个带负权的图转化为权值非负的图,然后再利用N次Dijkstra算法求出全源最短路径。

    其中,对图的权值进行重赋的过程是:

    在图G中增加一个新结点S,并让其与其他结点相连,形成一幅新图G’,对G’进行Bellman-Ford算法计算从S到各结点的最短路径h,删除结点S,然后根据新权重确定公式:
    w ′ ( u , v ) = w ( u , v ) + h ( u ) − h ( v ) w'(u,v)=w(u,v)+h(u)-h(v) w(u,v)=w(u,v)+h(u)h(v)
    对原图的权重进行修改,使得权重都为正。

    然后进行n次Dijkstra算法即可。

    更多相关内容
  • Dijkstra最短路径算法Matlab实现 包括最短路径的打印子程序
  • DQN找最短路径算法MATLAB实现,含界面,可运行!
  • 最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd
  • 最短路径算法 matlab

    2018-12-31 15:25:29
    利用matlab实现了网络最短路径的搜索算法,通过输入邻接矩阵和需要输出最短路径的始节点和终节点,即可得到这连点间可行的最短路。
  • matlab实现最短路径算法Dijkstra
  • 在地图上找到从起始节点到结束节点的最短路径和距离** 2. 找出地图上从起始节点到所有其他节点的最短路径和距离** **地图应由节点和段组成,例如: 1.节点的格式为[ID XY]或[ID XYZ](ID为整数,X,Y,Z代表位置坐标...
  • 基本的matlab蚁群算法求解最短路径问题,里面另附有初始数据
  • 关于遗传算法的一个简单例子,在MATLAB实现搜寻最短路径(最优化)的目的,仅供大家参考学习,谢谢
  • 首先在m脚本文件canshuo.m中输入节点个数和路径权重 在命令窗口中输入canshu 用s=12,e=10的格式输入要求的...打开all.m,将其中的语句复制下来,贴在命令窗口中,可得到任意两点之间的最短路径,放在Muti_Cost矩阵中
  • MATLAB实现最短路径算法

    热门讨论 2009-10-26 16:25:18
    MATLAB实现最短路径算法,在图论里比较重要,可以计算出个对象之间的距离。
  • Dijkstra算法是一种贪心算法,每一次都求最短路径,但与常见的贪心算法不同的是,Dijkstra算法是一种步步为营的贪心算法,因此能求解一个顶点到另一个顶点的最短路径。 2. 算法讲解 2.1. 理论讲

    1. 按

    Dijkstra算法用于求解一个顶点到另一顶点的最短路径,它采用了非暴力的贪心思想,因此时间复杂度较低,为O(N^2)。
    Dijkstra算法是一种贪心算法,每一次都求最短路径,但与常见的贪心算法不同的是,Dijkstra算法是一种步步为营的贪心算法,因此能求解一个顶点到另一个顶点的最短路径。

    2. 算法讲解

    2.1. 理论讲解

    1. 约定AimedPathNodes为所要求解的从某一目标点HeadNode(为了便于理解,将此节点约定为HeadNode,即头结点,目标路径上开头的那个节点)到另一目标点TrailNode(为了便于理解,将此节点约定为TrailNode,即尾结点,目标路径上结尾的那个节点)的最短的目标路径。
    2. 目标路径是由多个点组成的,刚开始时目标路径AimedPathNodes仅包含起始点HeadNode
    3. 找出当前目标路径(AimedPathNodes)的最近的邻接点并将其加入到AimedPathNodes中,随后再次找出AimedPathNodes的最近邻接点,并将其加入到AimedPathNodes中,这样一直下去,直到AimedPathNodes包含结尾的那个点(TrailNode)为止。

    2.2. 实例讲解

    2.2.1. 初始化

    给每个点进行编号v1、v2 … v11,这里的v是vertex的缩写,是点的意思,因此v1是点1的意思。
    给每条边初始化一个权重,权重用数字表示,如下图中v1与v2两点间的边的权重为2。
    此例用于求解v1到v11两点间的最短路径。
    约定AimedPathNodes为一个存储目标路径上所有点的变量。
    在这里插入图片描述

    2.2.2. 执行算法

    1. 刚开始时AimedPathNodes仅包含v1
      在这里插入图片描述
    2. 此时AimedPathNodesv1
      AimedPathNodes最近的邻接点,即找v1的最近的邻接点。
      v1相邻的点为v2、v3、v4,因此v1的邻接点为v2、v3、v4
      其中v1v2的边权重位2v1v3的边权重位8v1v4的边权重位1
      易得:v1的最近邻接点为v4
      v4加入到AimedPathNodes
      在这里插入图片描述
    3. 此时AimedPathNodesv1, v4
      AimedPathNodes的最近邻接点,即先找出v1的不包含AimedPathNodes上的点的最短邻接点v2,再找出v4的不包含AimedPathNodes上的点的最近邻接点v3
      由于v1v2的距离为2v4v3的距离为7,因此v2为到此时AimedPathNodes的最近点,将v2加入到AimedPathNodes
      在这里插入图片描述
    4. 此时AimedPathNodesv1, v4, v2
      易得AimedPathNodes的最近邻接点为v5,将v5加入到AimedPathNodes
      在这里插入图片描述
    5. 此时AimedPathNodesv1, v4, v2, v5
      易得AimedPathNodes的最近邻接点为v8
      在这里插入图片描述
    6. 此时AimedPathNodesv1, v4, v2, v5, v8
      AimedPathNodes的最近邻接点为v6
      在这里插入图片描述
    7. 此时AimedPathNodesv1, v4, v2, v5, v8, v6
      AimedPathNodes的最近邻接点为v3
      在这里插入图片描述
    8. 此时AimedPathNodesv1, v4, v2, v5, v8, v6, v3
      AimedPathNodes的最近邻接点为v7
      在这里插入图片描述
    9. 此时AimedPathNodesv1, v4, v2, v5, v8, v6, v3, v7
      AimedPathNodes的最近邻接点为v10
      在这里插入图片描述
    10. 此时AimedPathNodesv1, v4, v2, v5, v8, v6, v3, v7, v10
      AimedPathNodes的最近邻接点为v9
      在这里插入图片描述
    11. 此时AimedPathNodesv1, v4, v2, v5, v8, v6, v3, v7, v10, v9
      AimedPathNodes的最近邻接点为v11
      在这里插入图片描述
    12. 停止找最近的邻接点。实际求解最短路径时,除了上面的之外,还要再声明一个变量用于存储最短路径,并且每一步还有一个对该变量进行退栈和入栈的操作。
      在这里插入图片描述

    3. matlab实现

    dijkstra.m

    function [min,path]=dijkstra(w,start,terminal)
        n=size(w,1); label(start)=0; f(start)=start;
        for i=1:n
           if i~=start
               label(i)=inf;
        end, end
        s(1)=start; u=start;
        while length(s)<n
           for i=1:n
              ins=0;
              for j=1:length(s)
                 if i==s(j)
                    ins=1;
                 end,  
              end
              if ins==0
                 v=i;
                 if label(v)>(label(u)+w(u,v))
                    label(v)=(label(u)+w(u,v)); 
                 f(v)=u;
                 end, 
              end, 
           end   
        v1=0;
           k=inf;
           for i=1:n
                 ins=0;
                 for j=1:length(s)
                    if i==s(j)
                       ins=1;
                    end, 
                 end
                 if ins==0
                    v=i;
                    if k>label(v)
                       k=label(v);  v1=v;
                    end,  
                 end,  
           end
           s(length(s)+1)=v1;  
           u=v1;
        end
        min=label(terminal); path(1)=terminal;
        i=1; 
        while path(i)~=start
              path(i+1)=f(path(i));
              i=i+1 ;
        end
        path(i)=start;
        L=length(path);
        path=path(L:-1:1);
    

    4. 测试

    4.1. 测试一

    • 代码
      weight=[0     2     8     1   Inf   Inf   Inf   Inf   Inf   Inf   Inf;
           2     0     6   Inf     1   Inf   Inf   Inf   Inf   Inf   Inf;
           8     6     0     7     5     1     2   Inf   Inf   Inf   Inf;
           1   Inf     7     0   Inf   Inf     9   Inf   Inf   Inf   Inf;
         Inf     1     5   Inf     0     3   Inf     2     9   Inf   Inf;
         Inf   Inf     1   Inf     3     0     4   Inf     6   Inf   Inf;
         Inf   Inf     2     9   Inf     4     0   Inf     3     1   Inf;
         Inf   Inf   Inf   Inf     2   Inf   Inf     0     7   Inf     9;
         Inf   Inf   Inf   Inf     9     6     3     7     0     1     2;
         Inf   Inf   Inf   Inf   Inf   Inf     1   Inf     1     0     4;
         Inf   Inf   Inf   Inf   Inf   Inf   Inf     9     2     4     0;]
      [dis, path]=dijkstra(weight,1, 11)
      

    • 在这里插入图片描述
    • 结果
      dis = 13
      path = 1 2 5 6 3 7 10 9 11

    4.2. 测试二

    • 代码
      weight=[0     8   Inf   Inf   Inf   Inf     7     8   Inf   Inf   Inf;
         Inf     0     3   Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf;
         Inf   Inf     0     5     6   Inf     5   Inf   Inf   Inf   Inf;
         Inf   Inf   Inf     0     1   Inf   Inf   Inf   Inf   Inf    12;
         Inf   Inf     6   Inf     0     2   Inf   Inf   Inf   Inf    10;
         Inf   Inf   Inf   Inf     2     0     9   Inf     3   Inf   Inf;
         Inf   Inf   Inf   Inf   Inf     9     0   Inf   Inf   Inf   Inf;
           8   Inf   Inf   Inf   Inf   Inf   Inf     0     9   Inf   Inf;
         Inf   Inf   Inf   Inf     7   Inf   Inf     9     0     2   Inf;
         Inf   Inf   Inf   Inf   Inf   Inf   Inf   Inf     2     0     2;
         Inf   Inf   Inf   Inf    10   Inf   Inf   Inf   Inf   Inf     0;];
      [dis, path]=dijkstra(weight,1, 11)
      

    • 在这里插入图片描述
    • 结果
      dis = 21
      path = 1 8 9 10 11
    展开全文
  • 最短路径Dijkstra算法原理及Matlab实现

    万次阅读 多人点赞 2018-08-20 09:56:19
    最短路径算法主要有二 Dijkstra算法 Floyd算法 Dijkstra算法研究的是从初始点到其他每一结点的最短路径 而Floyd算法研究的是任意两结点之间的最短路径 以下图为例,首先介绍Dijstra的原理 红字为各结点的...

    图论的基础知识不再阐述。
    最短路径算法主要有二

    1. Dijkstra算法
    2. Floyd算法

    Dijkstra算法研究的是从初始点到其他每一结点的最短路径
    而Floyd算法研究的是任意两结点之间的最短路径

    以下图为例,首先介绍Dijstra的原理

    红字为各结点的编号,蓝字为各结点之间的距离

    1. 首先定义几个变量

      结点个数n;
      二维矩阵M(nxn),距离矩阵,连通的结点间即为距离,不连通的结点间为正无穷,和自己的距离为0;
      一维矩阵pb(1xn),若第i点已找到最短路径,则fp(i)=1,否则等于0,对于初始结点,fp=1;
      距离矩阵d(1xn),若第i点已找到最短路径,则的d(i)=最短距离,否则为0,初始结点d=0;
      上一结点矩阵path(1xn),若第i点找到了最短路径,则path存放这一条最短路径的前一个结点,通过对每一点的回溯,可以找到最短路径。

    2. 根据距离写出以下距离矩阵

      这里写图片描述

    3. 确定初始点为v1,则pb(1)=1;

      在图中,结点上,我们将已找到最短路径的点标为它的最短距离,(可以理解为v1点已找到最短路径,距离为0),未找到的其余点表为正无穷(即表示不连通)。
      这里写图片描述
      在与v1连通的点中,即在矩阵m的第1行,寻找最小值,最小值所在列即确定的最短路径的结点,如同v2最短,pb(2)=1,d(2)=1,对于已找到最短路径的v2上一结点为v1,path(2)=1;
      这里写图片描述
      接着,在

      • 与v1连通的,且未找到最短距离的节点的距离
      • 与v2连通的,且未找到最短距离节点的距离+v2的最短距离

      以上两种中寻找最短距离,最短为v6,pb(6)=1;d(6)=2;path(6)=1;
      这里写图片描述
      重复以上步骤,在

      • 与v1连通的,且未找到最短距离的节点的距离
      • 与v2连通的,且未找到最短距离节点的距离+v2的最短距离
      • 与v6连通的,且未找到最短距离节点的距离+v2的最短距离
        以上三种中寻找最短路径,最短为v3,pb(3)=1;d(3)=3);path(3)=6;
        这里写图片描述
        我们可以发现,所要寻找的最短路径即为
        对于已找到最短路径的点(包括初始结点),在与其连通的,未找到最短路径的结点中,将之间距离与圆圈中的距离(即上一结点已找到的最短路径)相加,求得的最小值。
        如果有多个相同的最短距离,任取其中一个。
        最终最短路径即距离如下图
        这里写图片描述

    附上代码:

    clc;clear;
    n=6;   %设置矩阵大小
    temp=1;  %设置起始点
    m=zeros(6);%定义n阶零矩阵
    m(1,2)=1;m(1,6)=2;%设置矩阵中非零非无穷的值
    m(2,1)=1;m(2,3)=4;m(2,6)=4;
    m(3,2)=4;m(3,4)=2;m(3,6)=1;
    m(4,3)=2;m(4,5)=3;m(4,6)=3;
    m(5,4)=3,m(5,6)=5;
    m(6,1)=2;m(6,2)=4;m(6,3)=1;m(6,4)=3;m(6,5)=5;
    
    for i=1:n
        for j=1:n
           if(m(i,j)==0)
               m(i,j)=inf;
           end
        end
    end
    for i=1:n
        m(i,i)=0;
    end
    pb(1:length(m))=0;pb(temp)=1;%求出最短路径的点为1,未求出的为0
    d(1:length(m))=0;%存放各点的最短距离
    path(1:length(m))=0;%存放各点最短路径的上一点标号
    while sum(pb)<n %判断每一点是否都已找到最短路径
     tb=find(pb==0);%找到还未找到最短路径的点
     fb=find(pb);%找出已找到最短路径的点
     min=inf;
     for i=1:length(fb)
         for j=1:length(tb)
             plus=d(fb(i))+m(fb(i),tb(j));  %比较已确定的点与其相邻未确定点的距离
             if((d(fb(i))+m(fb(i),tb(j)))<min)
                 min=d(fb(i))+m(fb(i),tb(j));
                 lastpoint=fb(i);
                 newpoint=tb(j);
             end
         end
     end
     d(newpoint)=min;
     pb(newpoint)=1;
     path(newpoint)=lastpoint; %最小值时的与之连接点
    end
    d
    path

    路径只需向上回溯就可得到。

    展开全文
  • 内含最短路径算法代码及实验报告。本次实验要求利用MATLAB分别实现Dijkstra算法和Floyd算法,可对输入的邻接距离矩阵计算图中任意两点间的最短距离矩阵和路由矩阵,且能查询任意两点间的最短距离和路由。
  • 本文实例讲述了Python使用Dijkstra算法实现求解图中最短路径距离问题。分享给大家供大家参考,具体如下: 这里继续前面一篇《Python基于Floyd算法求解最短路径距离问题》的内容,这里要做的是Dijkstra算法,与Floyd...
  • 最短路径 Dijkstra算法Matlab代码实现

    万次阅读 多人点赞 2020-09-11 09:29:25
    % 利用dijkstra算法计算两点间的最短路径 % A:邻接矩阵 % strat:起点编号 % dest:终点编号 % path:最短路径索引 % distence:最短路径下的距离值 function [dist,path] = dijkstra(A,start,dest) % 测试数据 A =...

     为了搞清楚最短路径的算法过程,自己编写代码实现dijkstra算法寻找路径

    % 文件名:dijkstra.m
    % 时间:2020年9月12日
    % 来源:https://blog.csdn.net/lishan132/article/details/108527271
    % 功能:利用dijkstra算法计算两点间的最短路径
    % dist:起点与终点之间的最短距离值
    % path:最短路径索引
    % Distance:最短路径下的距离值
    % A:邻接矩阵
    % strat:起点编号
    % dest:终点编号
    function [dist,path,Distance] = dijkstra(A,start,dest)
    % 测试数据 A =[0,12,inf,inf,inf,16,14;12,0,10,inf,inf,7,inf;inf,10,0,3,5,6,inf;inf,inf,3,0,4,inf,inf;inf,inf,5,4,0,2,8;16,7,6,inf,2,0,9;14,inf,inf,inf,8,9,0];
    % 测试数据 start = 1;
    % 测试数据 dest = 4;
    % 计算程序运行时间
    tic  %开始计时
    
    % 初始化操作
    p = size(A,1);        %计算顶点数目 
    S(1) = dest;          %初始化集合S,已加入到路径中的顶点编号
    U = 1:p;              %初始化集合U,未加入到路径中的顶点编号
    U(dest) = [];         %删除终点编号
    Distance = zeros(2,p);  %初始化所有顶点到终点dest的距离
    Distance(1,:) = 1:p;    %重赋值第一行为各顶点编号
    Distance(2,1:p) = A(dest,1:p);  %重赋值第二行为邻接矩阵中各顶点到终点的距离
    new_Distance = Distance;
    D = Distance;            %初始化U中所有顶点到终点dest的距离
    D(:,dest) = [];          %删除U中终点编号到终点编号的距离
    path = zeros(2,p);  %初始化路径
    path(1,:) = 1:p;    %重赋值第一行为各顶点编号
    path(2,Distance(2,:)~=inf) = dest;  %距离值不为无穷大时,将两顶点相连
    
    % 寻找最短路径
    while ~isempty(U)  %判断U中元素是否为空
        index = find(D(2,:)==min(D(2,:)),1);  %剩余顶点中距离最小值的索引
        k = D(1,index);   %发现剩余顶点中距离终点最近的顶点编号
        
        %更新顶点
        S = [S,k];     %将顶点k添加到S中
        U(U==k) = [];  %从U中删除顶点k  
        
        %计算距离
        new_Distance(2,:) = A(k,1:p)+Distance(2,k); %计算先通过结点k,再从k到达终点的所有点距离值
        D = min(Distance,new_Distance);  %与原来的距离值比较,取最小值  
       
        %更新路径
        path(2,D(2,:)~=Distance(2,:)) = k;  %出现新的最小值,更改连接关系,连接到结点k上 
        
        %更新距离
        Distance = D;  %更新距离表为所有点到终点的最小值
        D(:,S) = [];   %删除已加入到S中的顶点
    end
    dist = Distance(2,start);  %取出指定起点到终点的距离值
    toc %计时结束
    
    % 输出结果
    fprintf('找到的最短路径为:');
    while start ~= dest    %到达终点时结束
        fprintf('%d-->',start);  %打印当前点编号
        next = path(2,start);    %与当前点相连的下一顶点
        start = next;            %更新当前点
    end
    fprintf('%d\n',dest);
    fprintf('最短路径对应的距离为:%d\n',dist);
    end
    
    

    此函数共有3个输入参数,3个输出参数

    输入参数说明

    A:邻接矩阵,存储各顶点之间的距离值,是一个大小为顶点个数的方阵,对角线元素为0
    strat:起点编号
    dest:终点编号

    输出参数说明

    dist:指定起点与终点之间的最短距离值
    path:最短路径索引,一共两行,第一行的值依次为各顶点编号,第二行的值为与第一行顶点相连的顶点编号
    Distence:最短路径下的距离值,一共两行,第一行的值依次为各顶点编号,第二行的值为对应顶点到终点的最小距离值

    算法有效性的测试如下:

     根据上图,想计算A点到D点的最短路径和距离,经过理论分析,其最短路径应为A-->F-->E-->D,最短距离为16+2+4=22

    下面输入代码进行验证

    输入代码

    A =[0,12,inf,inf,inf,16,14;12,0,10,inf,inf,7,inf;inf,10,0,3,5,6,inf;inf,inf,3,0,4,inf,inf;inf,inf,5,4,0,2,8;16,7,6,inf,2,0,9;14,inf,inf,inf,8,9,0];
    start = 1;
    dest = 4;
    [dist,path,Distance] = dijkstra(A,start,dest)

    时间已过 0.005424 秒。
    找到的最短路径为:1-->6-->5-->4
    最短路径对应的距离为:22

    dist =

        22


    path =

         1     2     3     4     5     6     7
         6     3     4     4     4     5     5


    Distance =

         1     2     3     4     5     6     7
        22    13     3     0     4     6    12

     输入其他任意两个点,换一个距离矩阵,依然能正确输出最短路径和相应的距离值,算法的有效性得到验证

     输入以下代码可生成最终的最短路径图,输出结果与起点值无关,任意点到D点的最短路径均可从图中找到

    A =[0,12,inf,inf,inf,16,14;12,0,10,inf,inf,7,inf;inf,10,0,3,5,6,inf;inf,inf,3,0,4,inf,inf;inf,inf,5,4,0,2,8;16,7,6,inf,2,0,9;14,inf,inf,inf,8,9,0];
    start = 1;
    dest = 4;
    
    [~,path,Distance] = dijkstra(A,start,dest)
    
    path(:,dest) = [];
    Distance(:,dest) = [];
    s = path(1,:);
    t = path(2,:);
    weights = Distance(2,:);
    names = {'A' 'B' 'C' 'D' 'E' 'F' 'G'};
    
    g = digraph(s,t,weights,names);
    
    plot(g,'EdgeLabel',g.Edges.Weight)

     可以看到,图中所有点均向D点聚集,且显示了每一个点到D点的最短距离

    下面,使用matlab图论工具箱的函数寻找最短路径,再进行一个对比验证

    图论工具箱中求最短路径的函数有以下3个,本文使用shortestpath,matlab命令窗口中输入doc shortestpath即可查看用法

    shortestpath    两个单一节点之间的最短路径
    shortestpathtree    从节点的最短路径树
    distances    所有节点对组的最短路径距离

    % 文件名:shortpath.m
    % 时间:2020年9月12日
    % 来源:https://blog.csdn.net/lishan132/article/details/108527271
    % 功能:利用matlab自带的shortestpath函数计算两点间的最短路径
    % dist:起点与终点之间的最短距离值
    % path:最短路径
    function [dist,path] = shortpath(A,start,dest)
    %使用matlab自带的函数计算最短路径
    tic
    A(A==inf) = 0;  %将无穷大值变为0
    [t,s,weights] = find(A);  %邻接矩阵中非零值的列、行号索引,及对应值
    G = digraph(s,t,weights);  %生成一幅带权值的有向图
    [path,dist] = shortestpath(G,start,dest);  %计算最短路径
    toc
    
    %展示结果
    plot(G,'EdgeLabel',G.Edges.Weight)
    fprintf('找到的最短路径为:');
    fprintf('%d ',path);
    fprintf('\n');
    fprintf('最短路径对应的距离为:%d\n',dist);
    end
    
    

     命令窗口输入以下代码验证结果

    A =[0,12,inf,inf,inf,16,14;12,0,10,inf,inf,7,inf;inf,10,0,3,5,6,inf;inf,inf,3,0,4,inf,inf;inf,inf,5,4,0,2,8;16,7,6,inf,2,0,9;14,inf,inf,inf,8,9,0];
    start = 1;
    dest = 4;
    [dist,path] = shortpath(A,start,dest)

    时间已过 0.002112 秒。
    找到的最短路径为:1 6 5 4 
    最短路径对应的距离为:22

    dist =

        22


    path =

         1     6     5     4

    两者结果一致,再次验证算法的有效性,而且自己写的Dijkstra算法的代码还能够一次输出所有点到终点的距离及路径表

    仅一次测试以及少量的数据规模N不足以说明算法的解决效率,为了对两个算法性能进行一个比较,特地写了一个测试程序,输入的数据规模N从10到2000变化,并注释dijkstra.m、shortpath.m两个文件中的计时和输出结果部分的代码,程序如下

    % 文件名:compar1.m
    % 时间:2020年9月12日
    % 来源:https://blog.csdn.net/lishan132/article/details/108527271
    % 功能:比较自己实现的dijkstra算法与matlab图论工具箱函数的效率性能
    % 说明:请先将dijkstra.m、shortpath.m文件与本文件放在同一目录下
    clear
    close
    clc
    iter = 200;  %测试次数
    t1 = zeros(1,iter);  %算法1时间
    t2 = zeros(1,iter);  %算法2时间
    for i = 1:iter
        %% 第一步:生成测试数据,距离矩阵A,起点start,终点dest
        clearvars -except iter i t1 t2 %清空除iter,i,t1,t2外的所有变量
        N = i*10;  %输入数据规模
        ub = 15;  %输入数据距离上限
        A = unifrnd (0, ub, N, N);  %生成一个服从均匀分布的矩阵,数值范围[0,ub],矩阵大小n×n
        A = A - A';
        A(A<0) = inf;
        start = round(rand(1,1)*(N-1))+1;
        dest = round(rand(1,1)*(N-1))+1;
        while start == dest
            dest = round(rand(1,1)*(N-1))+1;
        end
        %% 第二步:计算自己编写的dk算法的运行时间
        tic  %开始计时
        dijkstra(A,start,dest);
        t1(i) = toc; %计时结束
    
        %% 第三步:计算使用matlab自带图论工具箱算法的运行时间
        tic  %开始计时
        shortpath(A,start,dest);
        t2(i) = toc;  %计时结束
    end
    
    %% 第四步:绘制算法所需时间图
    plot(1:iter,t1);
    hold on
    plot(1:iter,t2);
    legend("文中dijkstra算法","图论工具shortestpath函数")
    title("算法耗费时间比较")
    
    

    惊喜地发现,随着数据规模的增大,自己写的Dijkstra算法与图论工具函数shortestpath相比,耗时更低,而且差距越来越大。

    当然,此处还是有些不严谨,因为我在使用图论工具函数shortestpath解决问题时,前面自己还写了三条参数的处理语句,这部分语句的处理过程也是算入时间的

    结论

    本文实现了dijkstra算法的Matlab代码,并封装成一个函数,给定一个邻接矩阵,以及指定一个终点,可以直接输出任意点到终点的最短路径和相应的距离值,相对matlab自带的图论工具箱函数,其运算速度快,输出数据全,方便二次开发,提高效率。但自己写的程序中每次只寻找一个新的结点加入,有多少个结点,while中的循环体就要执行多少次,每一次循环均要更新一次所有结点到终点的距离值,当结点数据非常大时,时间复杂度为O(N^2),因此还有继续优化的空间,根据相关文献,可用堆进行优化,也可从能否一次加入多个新结点,而不是一个来考虑加快搜索速度。

    参考文章:

    [1] 数据结构--Dijkstra算法最清楚的讲解 https://blog.csdn.net/heroacool/article/details/51014824

    [2] 通俗易懂理解——dijkstra算法求最短路径 https://zhuanlan.zhihu.com/p/40338107

    [3] Dijkstra算法及其matlab实现 https://blog.csdn.net/u011317780/article/details/82429511

    [4] 李建东,盛敏编著. 通信网络基础. 北京:高等教育出版社, 2004.08.

    [5] 迪杰斯特拉 & 堆优化 https://blog.csdn.net/CSDNjiangshan/article/details/79345031

    展开全文
  • Dijkstra算法是一种最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多...
  • 蚁群算法最短路径通用Matlab程序(附图)function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q)%% --------------------------------------------------------------- % ACASP.m% 蚁群算法动态寻路算法% ...
  • MATLAB-K最短路径算法(KSP,K-shortest pathes)

    千次阅读 多人点赞 2020-10-16 17:30:12
    MATLAB-K最短路径算法(KSP,K-shortest pathes) MATLAB代码封装成函数,直接使用。 参考: k最短路径算法之Yen’s Algorithm 基于网络流量的SDN最短路径转发应用 算法背景 K 最短路径问题是最短路径问题的扩展和变形...
  • GUI图论中的最短路径算法实现-MinPathAlog.rar 这是《图论及其应用》中的“最短路径”算法GUI实现。 比较基础,共享。共同提高
  • Floyd-Warshall 算法计算给定邻接矩阵的所有对最短路径矩阵。 该算法是 O(n^3),在大多数实现中,您会看到 3 个嵌套的 for 循环。 这在 Matlab 中效率很低,所以在这个版本中,两个内部循环被向量化(因此,它运行得...
  • MATLAB实现最短路径

    千次阅读 2021-08-30 22:55:17
    Dijkstra是解决最短路径的一种算法 最短路径即从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径 二、使用步骤 1.引入库 代码如下(示例): import numpy as np import pandas as p
  • 最短路径matlab求解

    2022-02-10 19:52:07
    数学建模:最短路径求解
  • MATLAB最短路径Floyd算法

    千次阅读 热门讨论 2021-07-31 11:41:36
    直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1),D(2)…D(n)(每次加入一个点然后更新最短路径矩阵D),D(n)是图的最短距离矩阵,同时引入一个后继点矩阵path记录两点间的最短路径。...
  • 这是一道比较有意思的题目,给定一个... 最简单粗暴的方法就是把所有的路径找出来,计算每一条路径的值,然后进行比较,找出那条最短路径。但我们不需要这么做,毕竟设计一个遍历所有路径的算法还是挺复杂的。我们知...
  • 蚁群算法最短路径MATLAB代码实现,比较完整,需要的可以下载试一下
  • 这是一道比较有意思的题目,给定一个... 最简单粗暴的方法就是把所有的路径找出来,计算每一条路径的值,然后进行比较,找出那条最短路径。但我们不需要这么做,毕竟设计一个遍历所有路径的算法还是挺复杂的。我们知...
  • 最短路径-任意两点间最短距离-Floyd算法matlab实现(详细教程) 目录 简介 核心思路 优缺点分析 算法过程 简介 Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的...
  • MATLAB实现最短路径问题中的Floyd算法、代码以及说明文档。

空空如也

空空如也

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

最短路径算法matlab实现

matlab 订阅