Dijkstra算法和Floyd算法详解(MATLAB代码)

这篇具有很好参考价值的文章主要介绍了Dijkstra算法和Floyd算法详解(MATLAB代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、Dijkstra算法

1.算法简介

Dijkstra算法是由E.W.Dijkstra1959年提出,又叫迪杰斯特拉算法,它应用了贪心算法模式,是目前公认的最好的求解最短路径的方法。算法解决的是有向图中单个源点到其他顶点的最短路径问题,其主要特点是每次迭代时选择的下一个顶点是标记点之外距离源点最近的顶点。

2.算法原理

该算法在计算的时候将所有的点分为两个集合。集合U中存放已找到最短路径的顶点,集合V中存放当前还未找到的最短路径的顶点。

Dijkstra算法的功能是,给定一个起点,计算其到其他所有点的最短路径,也就是1 TO N的问题。

在集合T中找到起点V0能够达到的,且距离最短的点,将其加入到U中,之后根据新加入的点,重新计算一次V0T中剩余点的当前最短距离

3.示例讲解

求A点到H点的距离

八个点的位置关系图如下所示:

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

A点到各个点之间的距离如图所示(只算与A点直接相连的距离,A点需要跨过一个点才能到达的点,距离为inf)

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

 每次选择距离A最短的一个点,然后用这个点的距离更新其他相邻点到A的距离,如果比当前的点小,则更新节点的值。查看所有点,D距离家最近,则用D更新与它相邻的点

C: MIN(10, 3 + 5)  = 8    G: MIN(3 + 12, INF) = 15

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

  剔除掉D这个点,然后从所有点中找距离家最小值的点,发现B最小,更新B相连的点 C, E

C: MIN(8, 4+3)  = 7          E: MIN(4+8, INF) = 12

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

剔除掉B这个点,继续找最小值的点 C,更新C相连的点 E,F

E: MIN(12, 10)  = 10       F: MIN(7 + 12, INF) = 19

 dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

 篇幅有限,后面的步骤以此类推,这里直接给出最终结果

A-H的距离为14        路径:A-B-C-E-F-H

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

 4.流程图

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

5.MATLAB代码

把以下两个文件放一个文件夹里,且运行tulun1.m文件

创建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)

 创建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

6.实现结果

各点之间的位置关系图如下:

A

B

C

D

E

F

G

H

A

0

4

10

3

inf

inf

inf

inf

B

4

0

3

inf

8

inf

inf

inf

C

10

3

0

5

3

12

inf

inf

D

3

inf

5

0

inf

inf

12

inf

E

inf

8

3

inf

0

3

inf

5

F

inf

inf

12

inf

3

0

inf

1

G

inf

inf

inf

12

inf

inf

0

2

H

inf

inf

inf

inf

5

1

2

0

方便大家复制

[0 4 10 3 inf inf inf inf;
4 0 3 inf 8 inf inf inf;
10 3 0 5 3 12 inf inf;
3 inf 5 0 inf inf 12 inf;
inf 8 3 inf 0 3 inf 5;
inf inf 12 inf 3 0 inf 1;
inf inf inf 12 inf inf 0 2;
inf inf inf inf 5 1 2 0]

输入位置关系图、起点和终点,得到结果。

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

二、Floyd算法

1.算法简介

Floyd算法又称为插点法相对于Dijkstra算法来说,可以解决多源最短路径问题(即可以从任意一个点到任意一个点),可应用于地图导航走最短路径、为各城市修建最短路径的通信网(节省成本)等问题。

该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

 2.示例讲解

A 为最短路径长度,Path 为最短路径

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

 A点为中转点

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

 B点为中转点

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

C点为中转点

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlabD点为中转点

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab 以下是各个点之间的最短路径和最短路径长度

最短路径长

最短路径

a->b

2

a->b

a->c

5

a->b->c

a->d

4

a->d

b->a

9

b->c->d->a

b->c

3

b->c

b->d

4

b->c->d

最短路径长

最短路径

c->a

6

c->d->a

c->b

8

c->a->d->b

c->d

1

c->d

d->a

5

d->a

d->b

7

d->a->b

d->c

10

d->a->b->c

 3.流程图

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

 4.MATLAB代码

把以下两个文件放一个文件夹里,且运行tulun1.m文件

 创建tulun1.m文件

a = input('please enter the value of a:');
start = input('please enter the start:');
terminal = input('please enter the terminal:');
          [D, path,min1,path1]= tulun2(a,start, terminal)

创建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;

5.实现结果

各个点之间的位置关系图如下:

A

B

C

D

A

0

2

6

4

B

inf

0

3

inf

C

7

inf

0

1

D

5

inf

12

0

方便大家复制

[0 2 6 4;
inf 0 3 inf;
7 inf 0 1;
5 inf 12 0]

输入位置关系图、起点和终点

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

得到结果

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

 D=各个路径之间的最短距离

path=各个路径

minl=从2到4的最短距离

pathl=从2到4的路径

关于D和path的路径怎么看,我在举个例子

假如从3(C)到2(B),看结果可知最短距离是8

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

 看结果可知最短路径是3-4-1-2

解释:3(B)->2(B)可以看到是4,

           所以去找4(D)->2(B)可以看到是1

           所以去找1(A)->2  (B) 可以看到2

          因为我们要到达的终点就是2,所以最短路径为3-4-1-2

dijkstra算法matlab代码,学习笔记,算法,贪心算法,matlab

参考博客

算法之迪杰斯特拉(dijkstra)非常详细介绍_PRML_MAN的博客-CSDN博客_迪杰斯特拉

 MATLAB 图论 Dijkstra算法以及Floyd算法_学习笔记本的博客-CSDN博客

Floyd (弗洛伊德)算法简述_慕羽★的博客-CSDN博客_弗洛伊德算法文章来源地址https://www.toymoban.com/news/detail-601567.html

到了这里,关于Dijkstra算法和Floyd算法详解(MATLAB代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包