最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)

这篇具有很好参考价值的文章主要介绍了最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

简介

核心思路

优缺点分析

算法过程

         示例


简介

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

核心思路

路径矩阵

通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 [3] 

从图的带权邻接矩阵A=[a(i,j)] n×n开始,递归地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路径。

采用松弛技术(松弛操作),对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);

状态转移方程

其状态转移方程如下: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]};

map[i,j]表示i到j的最短距离,K是穷举i,j的断点,map[n,n]初值应该为0,或者按照题目意思来做。

当然,如果这条路没有通的话,还必须特殊处理,比如没有map[i,k]这条路。

优缺点分析

编辑 语音

Floyd算法适用于APSP(All Pairs Shortest Paths,多源最短路径),是一种动态规划算法,稠密图效果最佳,边权可正可负。此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra算法,也要高于执行|V|次SPFA算法。

优点:容易理解,可以算出任意两个节点之间的最短距离,代码编写简单。

缺点:时间复杂度比较高,不适合计算大量数据

算法过程

 在Floyd算中一般会用到有两个矩阵,一个距离矩阵D一个路由矩阵R,顾名思义距离矩阵D是用来储存任意两点之间的距离的,而路由矩阵则是用来记录任意两点之间的路径关系。  

Floyd算法的原理是:对于每一对顶点 i 和 j,看看是否存在一个顶点 w 使得从 i 到 w 再到 j 比已知的路径更短。如果是更新它。

把图用邻接矩阵r表示出来,如果从Vi到Vj有路可达,则D[i,j]=d(在矩阵D中为具体的数字),d表示该路的长度;否则D[i,j]=无穷大(在矩阵D中用“inf“表示)。定义一个矩阵D用来记录所插入点的信息,R[I,j]表示从Vi到Vj需要经过的点,初始化R[i,j]=j(即先默认i到j是通的)。把各个顶点插入图中,比较插点后的距离与原来的距离,假设插入的中间点为k,D[i,j] > D[i,k]+D[k,j] ),此时证明从i点经过k点再到j点比原来的要短,所以此时要更新D[i,j],则D[i,j]=D[I,k]+[k,j],同时此时R[i,j]=k。在R中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。

可能有些人对路由矩阵R不是很明白,其实路由矩阵R很好理解,我来举个例子,

比如,要寻找从V5到V1的路径。根据R,假如 R(5,1)=3则说明从V5到V1经过V3,路径为{V5,V3,V1},如果R(5,3)=3,说明V5与V3直接相连,如果R(3,1)=1,说明V3与V1直接相连。

因此,我们在定义路由矩阵R时,先要初始化矩阵(即先默认任意两点是相互相通的),即每列上的数等于该列的列序数。

例:

V1 V2 V3 V4   **** Vn
V1 1 2 3 4 **** n
V2 1 2 3 4 **** n
V3 1 2 3 4 **** n
V4 1 2 3 4 **** n
**** 1 2 3 4 **** n
Vn 1 2 3 4 **** n

示例

下面我将用一个简单的例子来说明,下面是一个简单的例子:

问题:求出任意两点间的最短距离及其路径?

最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)

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

最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程) 最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)

这样我们就定义好了距离矩阵路由矩阵,现在我们再来假设图中任意两点之间都要经V5这个点中转。算出经过中转后的两点之间的距离,然后我们再来判断任意两点之间的最短距离。
(1)先从V5开始,先让V5成为中转点。

V5由V5中转,那么V5到到各个点的距离还是不变。

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

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

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

这时两个矩阵变化为

最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程) 

(2)再让V4成为中转点。

V5  V1 都没有到达V4的路径,所以也就不存在从V5中转的情况,所以V5 V1 到各个点的距离还是不变。

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

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

V3>V5 经V4中转,原来V3->V5 = 6,经由V4中转之后V3>V4->V5 = 11, 因此V3到V5的最短距离仍为6,不更新。

这时两个矩阵变化为

最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)

 (3)同理,让所有的点都成为一次中转点

用Matlab来表示上面的过程,其代码为:

(1)先建立一个.m文件


最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)

function [d,r]=floyd(a)
n=size(a,1);%测出a矩阵的行数
d=a;% 初始化距离矩阵
for i=1:n % 初始化路由矩阵
    for j=1:n
        r(i,j)=j;%使路由矩阵r形成初始矩阵(每一列上的数为该列的列序数,例:第3列上的数全为3)(上面有提到)
    end 
end 
r;

for k=1:n % 开始Floyd算法(用if语句来比较中转前后的大小)
    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;

 (2)在命令行输入矩阵a,也就是距离矩阵

最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)

> a=[0 inf 5 inf inf;
      4 0 inf 6 inf ;
      inf inf 0 2 6;
     inf 3 inf 0 9;
     inf inf 8 inf 0];
>> [d,r]=floyd(a)

(3)得出距离矩阵D和路由矩阵R 

最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)

(4)怎么通过得出的这两个矩阵看任意一点到任意一点的最短距离及其路径。

从任意一点到任意一点从矩阵d中就很容易看出来了,比如D(2,3)=9,就表示V2到V3的最短距离是9,因此两点的距离从矩阵中很容易看出,我就不过多解释了。

现在我重点来说一下怎么看路由矩阵:

举个例子:v4->V3

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

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

再来个例子:v5->V2

从距离矩阵中可以看出V5->V2的最短距离是D(5,2) = 13;根据其路由矩阵我们可以看出:

R(5,2) = 3,表示V5->V2,先经过V3,于是再看R(3,2) = 4,表示还需要再经过V4,于是我们看R(4,2) = 2,这个时候我们发现终于到了V2,所以V5->V2的最短路径是:V4->V2->V1->V3。文章来源地址https://www.toymoban.com/news/detail-449279.html

此时我们已经拿到了我们最开始想要的结果了!!!

到了这里,关于最短路径-任意两点间最短距离-Floyd算法的matlab实现(详细教程)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 空间分析实战指南:点到多边形的最短距离

    在我们最近的项目中,出现了一个新的需求:需要验证现场拍摄的照片的经纬度与实际地块之间的最短距离,以确保业务员在地块的一公里范围内进行拍照。 实现这个功能有两种方式,一种是在前台APP中校验,一种是在后台进行校验,接下来我会分别介绍这两种方式。 在我

    2024年02月13日
    浏览(37)
  • 力扣(leetcode)第821题字符的最短距离(Python)

    题目链接:821.字符的最短距离 给你一个字符串 s 和一个字符 c ,且 c 是 s 中出现过的字符。 返回一个整数数组 answer ,其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。 两个下标 i 和 j 之间的 距离 为 abs(i - j) ,其中 abs 是绝对值函数。 示

    2024年01月19日
    浏览(36)
  • GEE机器学习——利用最短距离方法进行土地分类和精度评定

    最短距离方法(Minimum Distance)是一种常用的模式识别算法,用于计算样本之间的相似度或距离。该方法通过计算样本之间的欧氏距离或其他距离度量,来确定样本之间的相似程度或差异程度。 最短距离方法的具体步骤如下: 1. 数据准备:收集并准备用于训练的数据集,确保

    2024年01月20日
    浏览(53)
  • 2023河南萌新联赛第(二)场:河南工业大学 F - 最短距离

    时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言524288K 64bit IO Format: %lld 题目描述 给定一棵包含 n n n 个顶点的树 T T T ,以及 m m m 个查询请求。每个查询包含三个参数 : x 、 y :x、y : x 、 y 和 k k k 。其中 x x x 和 y y y 是树中的两个顶点, k k k 是一个整数。对于

    2024年02月15日
    浏览(41)
  • Floyd算法实现实际问题——18个城市间最优路线规划

    离散数学大作业   —— 利用Floyd算法计算两城市间最优路径及距离   代码在最下面 一. 提出问题 在交通网络非常发达、交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时,不仅关心节省交通费用,而且对里程和所需要的时间等问题也感兴趣。对于这样

    2024年02月10日
    浏览(34)
  • 【数理知识】求两个三维空间点的坐标矩阵之间,任意两两点之间的空间距离,matlab 实现

    假设有两个包含了三维空间点坐标的,三维向量集 A A A 和 B B B ,两集合中分别有 m m m 个和 n n n 个三维空间坐标点,可以用矩阵表示为 A = [ a 1 x a 2 x a 3 x ⋯ a m x a 1 y a 2 y a 3 y ⋯ a m y a 1 z a 2 z a 3 z ⋯ a m z ] 3 × m , B = [ b 1 x b 2 x b 3 x ⋯ b n x b 1 y b 2 y b 3 y ⋯ b n y b 1 z b 2 z b 3 z ⋯

    2024年02月11日
    浏览(47)
  • Acwing.854 Floyd求最短路 (Floyd算法)

    给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。 再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输\\\"impossible”。 数据保证图中不存在负权回路。 第一行包含三个整数n, m, k 接下来m行,每行包含三

    2024年02月13日
    浏览(35)
  • 图算法——求最短路径(Floyd算法)

    目录 一、什么是最短路径 二、弗洛伊德(Floyd)算法 三、测试程序         求图的最短路径在实际生活中有许多应用,比如说在你在一个景区的某个景点,参观完后,要怎么走最少的路程到你想参观的下个景点,这就利用到了求图最短路径的算法。求图的最短路径有很多

    2024年02月07日
    浏览(38)
  • Floyd算法求解最短路径

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

    2024年02月05日
    浏览(30)
  • 【MATLAB】最短路径Floyd算法

    1.1适用范围 ∙ bullet ∙ 求每队顶点的最短路径 ∙ bullet ∙ 有向图、无向图和混合图 1.2算法思想 直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1),D(2)…D(n)( 每次加入一个点然后更新最短路径矩阵D ),D(n)是图的最短距离矩阵,同时引入一个后继

    2024年02月16日
    浏览(31)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包