数据结构--最短路径 Floyd算法

这篇具有很好参考价值的文章主要介绍了数据结构--最短路径 Floyd算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构–最短路径 Floyd算法

数据结构--最短路径 Floyd算法,408数据结构,算法,数据结构,c++,c语言,最短路,Floyd

F l o y d 算法:求出每⼀对顶点之间的最短路径 \color{red}Floyd算法:求出每⼀对顶点之间的最短路径 Floyd算法:求出每对顶点之间的最短路径
使⽤动态规划思想,将问题的求解分为多个阶段
对于n个顶点的图G,求任意⼀对顶点 V i → V j V_i \to V_j ViVj 之间的最短路径可分为如下⼏个阶段:
#初始:不允许在其他顶点中转,最短路径是?
#0:若允许在 V0 中转,最短路径是?
#1:若允许在 V0、V1 中转,最短路径是?
#2:若允许在 V0、V1、V2 中转,最短路径是?

#n-1:若允许在 V0、V1、V2 …… Vn-1 中转,最短路径是?

Floyd算法是一种用于寻找图中任意两个节点之间最短路径的算法,它的步骤如下:

  1. 创建一个二维数组dist,用于存储任意两个节点之间的最短路径长度。初始时,dist的值为图中两个节点之间的直接路径长度,如果两个节点之间没有直接路径,则设置为无穷大。
  2. 创建一个二维数组path,用于存储任意两个节点之间的最短路径的中间节点。初始时,path的值为起始节点到终点节点的直接路径上的终点节点。
  3. 使用三重循环,遍历所有节点,每次循环中选择一个节点k作为中间节点,更新dist和path数组的值。
    a. 对于每对节点i和j,如果通过节点k可以使得从节点i到节点j的路径更短,则更新dist[i][j]的值为dist[i][k] + dist[k][j],并更新path[i][j]的值为节点k。
    b. 如果dist[i][j]的值变小了,说明找到了一条更短的路径,需要更新path[i][j]的值为节点k。
  4. 重复步骤3,直到遍历完所有节点。
  5. 根据path数组,可以构建任意两个节点之间的最短路径。

以上就是Floyd算法的基本步骤。

Floyd算法的时间复杂度为 O ( n 3 ) O(n^3) O(n3),其中n为节点的个数。

若 A ( k − 1 ) [ i ] [ j ] > A ( k − 1 ) [ i ] [ k ] + A ( k − 1 ) [ k ] [ j ] 则 A ( k ) [ i ] [ j ] = A ( k − 1 ) [ i ] [ k ] + A ( k − 1 ) [ k ] [ j ] ; path ⁡ ( k ) [ i ] [ j ] = k 否则 A ( k )  和 path ( k )  保持原值 \begin{aligned} &\text{若}&& \mathrm{A}^{(k-1)}[i][j]\mathrm{>}\mathrm{A}^{(k-1)}[i][k]\mathrm{+}\mathrm{A}^{(k-1)}[k][j] \\ &\text{则}&& \mathbf{A}(k)[i][j]=\mathbf{A}^{(k-1)}[i][k]+\mathbf{A}^{(k-1)}[k][j]; \\ &&&\operatorname{path}^{(k)}[i][j]=k \\ &\text{否则}&& A^{(k)}\text{ 和 path}^{(k)}\text{ 保持原值} \end{aligned} 否则A(k1)[i][j]>A(k1)[i][k]+A(k1)[k][j]A(k)[i][j]=A(k1)[i][k]+A(k1)[k][j];path(k)[i][j]=kA(k)  path(k) 保持原值

数据结构--最短路径 Floyd算法,408数据结构,算法,数据结构,c++,c语言,最短路,Floyd
数据结构--最短路径 Floyd算法,408数据结构,算法,数据结构,c++,c语言,最短路,Floyd

V0到V4 最短路径⻓度为 A[0][4]=4
通过path矩阵递归地找到完整路径:

数据结构--最短路径 Floyd算法,408数据结构,算法,数据结构,c++,c语言,最短路,Floyd

注:
Floyd算法可以⽤于负权图
Floyd 算法不能解决带有“负权回路”的图(有负权值的边组成回路),这种图有可能没有最短路径

eg:

数据结构--最短路径 Floyd算法,408数据结构,算法,数据结构,c++,c语言,最短路,Floyd
## 代码
void floyd()
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
 {
dist[i][j] = map[i][j],
path[i][j] = 0; 
 }
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(dist[i][k] + dist[k][j] < dist[i][j])
 {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = k; //中转点
 }
 }

知识点回顾与重要考点

数据结构--最短路径 Floyd算法,408数据结构,算法,数据结构,c++,c语言,最短路,Floyd

注:也可⽤ Dijkstra 算法求所有顶点间的最短路径,重复 |V| 次即可,总的时间复杂度也是 O ( ∣ V ∣ 3 ) O(|V|^3) O(V3)文章来源地址https://www.toymoban.com/news/detail-654174.html

到了这里,关于数据结构--最短路径 Floyd算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】图—弗洛伊德(Floyd)算法

    上文介绍了迪杰斯特拉(Dijkstra)算法,计算网图的某个源点到其余各个顶点的最短路径问题(边权值为非负值),本文介绍另一个求最短路径的算法——弗洛伊德算法,它是计算所有顶点到所有顶点的最短路径,其时间复杂度为 O ( n 3 ) O(n^3) O ( n 3 ) ,其算法相比Dijkstra算法更加

    2024年02月12日
    浏览(51)
  • 大话数据结构-迪杰斯特拉算法(Dijkstra)和弗洛伊德算法(Floyd)

      最短路径,对于图来说,是两顶点之间经过的边数最少的路径;对于网来说,是指两顶点之间经过的边上权值之和最小的路径。路径上第一个顶点为源点,最后一个顶点是终点。   以如下无向图为例:   我们来计算下标为0的顶点,到其他顶点的最短路径,首先定义

    2024年02月06日
    浏览(39)
  • 【数据结构入门精讲 | 第九篇】考研408排序算法专项练习(一)

    前面几篇文章介绍的是排序算法,现在让我们开始排序算法的专项练习。 1.希尔排序是稳定的算法。(错) 解析:稳定性是指如果两个元素在排序前后的相对顺序保持不变,那么这个排序算法就是稳定的。对于具有相同的元素,排序后它们的相对位置应该保持不变。

    2024年02月03日
    浏览(46)
  • 数据结构--最短路径 Dijkstra算法

    计算  b e g i n  点到各个点的最短路 color{red}计算 begin 点到各个点的最短路 计算   b e g in   点到各个点的最短路 如果是无向图,可以先把无向图转化成有向图 我们需要2个数组 final[] (标记各顶点是否已找到最短路径)与 dis[] (最短路径⻓度)数组 Dijkstra算法是一种用于

    2024年02月12日
    浏览(35)
  • 【数据结构】图解:迪杰斯特拉算法(Dijkstra)最短路径

    目录 一、方法描述 二、例题一  ​编辑 三、例题二  有图如上,用迪杰斯特拉算法求顶点A到其余各顶点的最短路径,请问1.第一步求出的最短路径是A到C的最短路径2.第二步求出的是顶点A到顶点B/F的最短路径3.顶点A到D的最短路径长度是__25___ (填数字)4.顶点A到顶点F的最短路

    2024年02月12日
    浏览(35)
  • 【数据结构】最小生成树(Prim算法,普里姆算法,普利姆)、最短路径(Dijkstra算法,迪杰斯特拉算法,单源最短路径)

    问题解答 (1)最小生成树(Minimal Spanning Tree)的定义 生成树的代价 :设 G ( V , E ) G(V,E) G ( V , E ) 是一个无向连通网图,生成树上 各边的权值之和 称为 生成树的代价 。 最小生成树 :在图 G G G 所有生成树中, 代价最小的生成树 为 最小生成树 。 (2)最小生成树(MST)的性

    2024年02月11日
    浏览(38)
  • 数据结构 -最短路径dijkstra(迪杰斯特拉)算法讲解及代码实现

            迪杰斯特拉算法是一种广义的贪心算法,求出局部最优解,再去求全局最优解 举例图:(起始点为1) 辅助数组: s:记录了目标顶点到其他顶点的最短路径是否求得(求得为1,否则为0) p:目标顶点到其他顶点的最短路径的前驱节点 (如,求得1-7-5的最短路径,那

    2024年02月11日
    浏览(34)
  • 数据结构实验任务六 :基于 Dijsktra 算法的最短路径求解

    本次代码为实验六:基于 Dijsktra 算法的最短路径求解实现。本实验的重点在于对于Dijsktra算法的理解。有关Dijsktra的资料可以参考有关博文: 图论:Dijkstra算法——最详细的分析,图文并茂,一次看懂!-CSDN博客 以下附上实现代码: 以上代码仅供参考,欢迎交流。

    2024年02月04日
    浏览(45)
  • 数据结构与算法 —— 最短路径Dijkstra算法(迪杰斯特拉)详细图解以及python实现

    目录 前言 1. 介绍 2. 加权图 2.1 概念 3. 最短路径 -- Dijkstra 算法 3.1 历史 3.2 Dijkstra 算法的基本思路 3.3 Dijkstra 算法图解 4.  python中dijkstra算法的实现 5. 总结  前两章我们讲到了关于图的基本知识,和广度/深度优先搜索。 本章,我们将介绍 加权图 和 最短路径 的相关知识。 最

    2024年02月12日
    浏览(51)
  • 数据结构(12)Dijkstra算法JAVA版:图的最短路径问题

    目录 12.1.概述 12.1.1.无权图的最短路径  12.1.2.带权图的最短路径 1.单源最短路径 2.多源最短路径 12.2.代码实现 无权图的最短路径,即最少步数,使用BFS+贪心算法来求解最短路径,比较好实现,此处不做展开讨论。 有权图的最短路径,不考虑权重为负数的情况,因为权重为负

    2024年02月06日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包