最短路径-Floyd算法的matlab实现.md「建议收藏」

最短路径-Floyd算法的matlab实现.md「建议收藏」最短路径-Floyd算法的matlab实现​ 弗洛伊德算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或有向图或负权(但不可存在负权回路)的最短路径问题。​ 在Floyd算法中一般有两个矩阵,一个距离矩阵D,一个路由矩阵R,其中距离矩阵用于存储任意两点之间的最短距离,而路由矩阵则记录任意两点之间的最短路径信息。其思想是:如果可以从一个点进行中转,就进行比较从这个点中转和不中转的距…

大家好,又见面了,我是你们的朋友全栈君。

最短路径-Floyd算法的matlab实现

​ 弗洛伊德算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或有向图或负权(但不可存在负权回路)的最短路径问题。

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

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

从算法思想中我们可以大概推断我们要遍历n个中转点,在每个中转点进行操作的时候,需要对任意两点之间 的距离进行遍历。那么算法就应该有三重循环,第一重循环是遍历中转点,第二重和第三重循环是遍历任意两个点之间的距离。假设中转节点为K,那么节点i与j之间的最小距离怎么更新呢?
D ( i , K ) + D ( K , j ) &lt; D ( i , j ) D(i,K)+D(K,j) &lt; D(i,j) D(i,K)+D(K,j)<D(i,j)

其中D(i,K)+D(K,j)表示i到j从K中转的距离,D(i,j)表示从i到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,表示V4到V3一步就可以到达V3,如果现在可以从V2中转到达,那么R(4,3) = R(4,2) =2,表示V4->V3要先经过V2才能到达。

​ 下面我将用一个简单的例子来说明,下面是一个简单的例子:
在这里插入图片描述

这个时候我们可以写出距离矩阵D和路由矩阵R如下:


最短路径-Floyd算法的matlab实现.md「建议收藏」最短路径-Floyd算法的matlab实现.md「建议收藏」

上面是初始的距离矩阵和路由矩阵,现在我们假设:**图中的每个点之间可以经由V1中转**。这个时候我们再来判断任意两点之间的最短距离。

可以由V1中转,那么V1到到各个点的距离还是不变。V2没有到达V1的路径,所以也就不存在从V1中转的情况,所以V2到各个点的距离还是不变。

V3可以经由V1中转,那么这个时候判断一下中转前和中转后的距离大小,将最小距离留存下来如:

V3->V1 = 7 不变

V3->V2 = inf,经由V1中转之后V3->V1->V2 = 9, 于是V3到V2的最短距离变化为9,更新路由矩阵R(3,2) = R(3,1) = 1

V3->V4 = 1,经由V1中转之后V3->V1->V4 = 11, 于是V3到V4的最短距离就还是1

同理:

V4->V2 = inf, 经由V1中转之后V4->V1->V2 = 7, 于是V4到V2的最短距离变化为7,更新路由矩阵R(4,2) = R(4,1) = 1

V4->V3 = 12,经由V1中转之后V4->V1->V3 = 11, 于是V4到V2的最短距离变化为11,更新路由矩阵R(4,3) = R(4,1) = 1

那么距离矩阵和路由矩阵变化为:


最短路径-Floyd算法的matlab实现.md「建议收藏」
最短路径-Floyd算法的matlab实现.md「建议收藏」

现在假设在从V1中转的基础上,图中的每个点之间还可以经由V2中转,于是:

V1->V2 = 2

V1->V3 = 6,经由V2中转之后V1->V2->V3 = 5, 于是V1到V3的最短距离变化为5,更新路由矩阵R(1,3) = R(1,2) = 2

V1->V4 = 4

V2->V1 = inf

V2->V3 = 3

V2->V4 = inf

V3->V1 = 7

V3->V2 = 9

V3->V4 = 1

V4->V1 = 5

V4->V2 = 7

V4->V3 = 11,经由V2中转之后V4->V2->V3 = 10, 于是V4到V3的最短距离变化为10,更新路由矩阵R(4,3) = R(4,2) = 1。

于是现在的距离矩阵和路由矩阵可以变为:


最短路径-Floyd算法的matlab实现.md「建议收藏」
最短路径-Floyd算法的matlab实现.md「建议收藏」

现在假设在从V1中转的基础上,图中的每个点之间还可以经由V3中转,于是:

V1->V2 = 2

V1->V3 = 5

V1->V4 = 4

V2->V1 = inf,经由V3中转之后V2->V3->V1 = 10, 于是V2到V1的最短距离变化为10,更新路由矩阵R(2,1) = R(2,3) = 3。

V2->V3 = 3

V2->V4 = inf,经由V3中转之后V2->V3->V4 = 4, 于是V2到V5的最短距离变化为4,更新路由矩阵R(2,4) = R(2,3) = 3。

V3->V1 = 7

V3->V2 = 9

V3->V4 = 1

V4->V1 = 5

V4->V2 = 7

V4->V3 = 10

于是现在的距离矩阵和路由矩阵可以变为:


最短路径-Floyd算法的matlab实现.md「建议收藏」
最短路径-Floyd算法的matlab实现.md「建议收藏」

现在假设在从V1中转的基础上,图中的每个点之间还可以经由V4中转,于是:

V1->V2 = 2

V1->V3 = 5

V1->V4 = 4

V2->V1 = 10,经由V4中转之后V2->V4->V1 = 9, 于是V3到V1的最短距离变化为9,更新路由矩阵R(2,1) = R(2,4) = 3。

V2->V3 = 3

V2->V4 = 4

V3->V1 = 7,经由V4中转之后V3->V4->V1 = 6, 于是V3到V1的最短距离变化为6,更新路由矩阵R(3,1) = R(3,4) = 4。

V3->V2 = 9,经由V4中转之后V3->V4->V2 = 8, 于是V3到V1的最短距离变化为8,更新路由矩阵R(3,2) = R(3,4) = 4。

V3->V4 = 1

V4->V1 = 5

V4->V2 = 7

V4->V3 = 10

于是现在的距离矩阵和路由矩阵可以变为:


最短路径-Floyd算法的matlab实现.md「建议收藏」
最短路径-Floyd算法的matlab实现.md「建议收藏」

好了,到此所有点都中转过了,任意两点之间的最短距离就是最后距离矩阵中的数据,那么其路径该怎么表示呢?路径全部记录在路由矩阵中了,我们只要读取路由矩阵就可以了。

举个例子:v4->V3

从距离矩阵中可以看出V4->V3的最短距离是D(4,3) = 10;根据其路由矩阵我们可以看出:

R(4,3) = 1,表示V4->V3,先经过V1,于是再看R(1,3) = 2,表示还需要再经过V2,于是我们看R(2,3) = 3,这个时候我们发现终于到了V3,所以我们梳理一下,V4->V3的最短路径是:V4->V1->V2->V3。简言之就是固定列,根据路由矩阵在行中跳转,直到跳转到对应的点。

所以最后我们展示出代码就很容易理解了:

% floyd.m
% 采用floyd算法计算图a中每对顶点最短路
% d是矩离矩阵
% r是路由矩阵
function [d,r]=floyd(a)
n=size(a,1);
% 初始化距离矩阵
d=a;
% 初始化路由矩阵
for i=1:n
    for j=1:n
        r(i,j)=j;
    end 
end 
r;

% Floyd算法开始
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);
                r(i,j)=r(i,k);
            end 
        end 
    end
    k;
    d;
    r;
end
d
r

最后我还写了一个用于打印路径的函数:

% DisplayPath.m 打印路径函数
function DisplayPath(route, start, dest)
  % 打印出任意两点之间的最短路径 
  % route : 路由表 
  % start : 起点index
  % dest : 终点index
  
  i = 1;
  
  while 1
    if(route(start, dest) ~= dest)
      fprintf('V%s -> ', num2str(start));
      start = route(start, dest);
    else
      fprintf('V%s -> ', num2str(start));
      fprintf('V%s\n', num2str(dest));
      break;
    end
  end

我将上面的举例的图使用floyd算法进行计算,并最后打印出任意两点之间的最短路径:

a = [0 2 6 4;
    inf 0 3 inf;
    7 inf 0 1 ;
    5 inf 12 0];
    
[d,r]=floyd(a)


disp('--------------------------')

for i = 1 : 4
  for j = 1 : 4
   DisplayPath(r, i, j);
  end
end

运行结果为:

main

d =

 0     2     5     4
 9     0     3     4
 6     8     0     1
 5     7    10     0

r =

 1     2     2     4
 3     2     3     3
 4     4     3     4
 1     1     1     4

V1 -> V1
V1 -> V2
V1 -> V2 -> V3
V1 -> V4
V2 -> V3 -> V4 -> V1
V2 -> V2
V2 -> V3
V2 -> V3 -> V4
V3 -> V4 -> V1
V3 -> V4 -> V1 -> V2
V3 -> V3
V3 -> V4
V4 -> V1
V4 -> V1 -> V2
V4 -> V1 -> V2 -> V3
V4 -> V4

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/152199.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 手机通讯录实现

    手机通讯录实现

  • bass reducer什么意思_map filter foreach区别

    bass reducer什么意思_map filter foreach区别对于一些环境变量的配置文件,如想使更改后立即生效,多用souce+file执行后即可。如/etc/profile里加了配置,source和bash的区别:sourcefilenam

  • 【JUC】——CurrentHashMap(1.7、1.8)[通俗易懂]

    【JUC】——CurrentHashMap(1.7、1.8)[通俗易懂]一.CurrentHashMap概述笔者曾在《Map——HashMap》一文中提到,HashMap是JavaCollectionFramework的重要成员,也是Map族(如下图所示)中我们最为常用的一种。不过遗憾的是,HashMap不是线程安全的。也就是说,在多线程环境下,操作HashMap会导致各种各样的线程安全问题,比如在HashMap扩容重哈希时出现的死循环问题,脏读问题…

  • 9. 数仓开发之 DWD 层

    9. 数仓开发之 DWD 层数仓开发之DWD层交易域加购事务事实表DWD层设计要点:DWD层的设计依据:维度建模理论,该层存储维度模型的事实表DWD层的数据存储格式:orc列式存储+snappy压缩DWD层表名的命名规范:dwd_数据域_表名_单分区增量****全量标识(inc/full)交易域加购事务事实表…

  • 读取金税盘数据库_一种基于金税盘控制系统登录和数据同步的方法与流程

    读取金税盘数据库_一种基于金税盘控制系统登录和数据同步的方法与流程本发明涉及税务开票领域,更具体地,涉及一种基于金税盘控制系统登录和数据同步的方法。背景技术:在以往的增值税销方开票操作中,销方用户在执行开票操作时,往往会出现当前用户信息与所使用的金税盘信息不匹配的情况,从而导致开票失败,需要调整用户数据或者更换金税盘。另外,系统中缺少对用户使用的金税盘数据的收集,无法有效的管理记录金税盘的使用情况,而且销方用户对应的库存信息和发票信息也存在数据不全的情况。技术实…

  • java的pdf转永中_永中pdf转word下载|

    java的pdf转永中_永中pdf转word下载|永中pdf转word是永中软件推出的一款网页版在线pdf转word转换器工具,这款软件之所以能在众多同类型软件中脱颖而出,是因为有这几个亮点,一个是免费且无需下载,二是不限使用次数,再就是转换后无乱码、排版整齐,有需要的朋友不要错过哦!永中pdf转word转换器介绍PDF意为”便携式文档格式”,以易于传输与储存、方便阅读、高质感等优点越来越多被使用于办公、学习和科研中,PDF文件一般需要安装阅读器…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号