提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

数模 03图论Dijkstra and Floyd matlab 及 软件使用

MATLAB软件 and 03 Dijkstra 图论 Floyd 使用
2023-09-11 14:20:23 时间

Dijkstra算法

迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

此算法求的是两点间的最短路径，注意，得先画出带权邻接矩阵：

  [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;]


    [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;];

 

至于具体算法在数据结构课程中已经了解到了，下面直接给出matlab实操过程。

主程序

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)

在主程序中的weight即为需要自行填写的带权邻接矩阵，dijkstra(weight,1, 11)表示求的是1到11的最短路径

迪杰斯特拉算法程序

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);

然后在命令行输入主程序保存的文件名，这里我保存的是tulun1，输出：

 

 dis为最短路径长度，path表示最短路径经过的点。

 

Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

直接程序加使用方法吧，在数据结构里面学过了，算法过程不再赘述

 

matlab主程序

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)

floyd算法程序

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

举例的话用另外一个举例吧：

[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;
  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;];

输出：

其中如果要找1到11的，先找path的（1，11）显示为8，所以找（8，11）显示为9，找（9，11）为10.。。。最后得到最短路径为1，8，9，10，11。距离分别将d矩阵相应数值加起来即可。

下面利用上面的知识，迪杰斯特拉算法验证结果

结果相同。

 

图论软件操作

ps：需要软件请留言

进入软件：

随机画上几个节点：

连线结果如图：

可以填入相应的费用和容量，可以类比运筹学中的最小费用流

至于其他概念在此不做赘述，比如二部图、完全偶图、星、环、连杆、重边等概念

只填入费用就相当于带权的图，可以求最短路径以及最小生成树

可以指定起点与终点，有向与无向

如果指定容量后还可以求拓扑排序、关键排序、最大流、最大流最小费用流。

ps：有需求请留言，还可以一起交流其他问题

相关文章