图的单源最短路径,Floyd算法(数据结构c++)-阿里云开发者社区

开发者社区> 橘子和香蕉> 正文

图的单源最短路径,Floyd算法(数据结构c++)

简介: 这个算法结构很是简单,但是理解还是有一定的困难,一开始做的时候想不明白,跟着算法自己动手画画就知道这个算法具体是怎么回事了。 时间复杂度是O(N*3) 算法有点动态规划的意思,有两个数组,一个(dis[])是记录俩顶点之间的最短路径的长度的,一个[path]数组是记录俩结点的中间结点的。
+关注继续查看

这个算法结构很是简单,但是理解还是有一定的困难,一开始做的时候想不明白,跟着算法自己动手画画就知道这个算法具体是怎么回事了。

时间复杂度是O(N*3)

算法有点动态规划的意思,有两个数组,一个(dis[])是记录俩顶点之间的最短路径的长度的,一个[path]数组是记录俩结点的中间结点的。在初始化这个数组的默认为 顶点的下标。。 

最重要的就是下面的几步

if(dis[sta][end]>dis[sta][temp]+dis[temp][end]){

dis[sta][end] = dis[sta][temp]+dis[temp][end];

}

上面的代码就是这个算法的精华部分。

sta:开始的顶点,end:结束的顶点,temp:是sta和end上的中间结点

两者相比较,要是有更短的路径就跟新俩结点的距离。

以每一个结点为中间点,更新数组,也就是所有顶点的距离。

话不多说。上程序。。。。


img_eca6e9f181245c8a05d667b550deca3b.png



img_bcc5a1c80b5e526dee289576fd503e8a.png
img_765a3266d60b4c1e16c6d9b2c1be651f.png
img_c35d76646cc8fb575438026021ddb17b.png
img_301e90f6b96932fd58839dd2871fa4c1.png

OK

就这个多,之前的都是铺垫,注意看重点的部分,floyd算法部分

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
排序算法大数据量测试代码
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.Diagnostics; using System.IO; namespace Sort { class Program
829 0
软考之路--数据结构之线性表
        数据就是数值,也就是我们通过观察、实验或计算得出的结果。数据有很多种,最简单的就是数字。数据也可以是文字、图像、声音等。数据可以用于科学研究、设计、查证等。
913 0
《数据结构和算法分析》具有O(logN)对数特点的三个基本算法
对分查找 给定一个整数X和整数A0,A1,…,AN-1,后者已经预先排序并存在内存中,求使得Ai=X的下标i,如果X不在数据中,则返回i=-1。 int BinarySearch (const ElementType A[], ElementType x, int N)...
654 0
redis数据结构、持久化、缓存淘汰策略
redis数据结构、持久化、缓存淘汰策略Redis 单线程高性能,它所有的数据都在内存中,所有的运算都是内存级别的运算,而且单线程避免了多线程的切换性能损耗问题。redis利用epoll来实现IO多路复用,将连接信息和事件放到队列中,依次放到文件事件分派器,事件分派器将事件分发给事件处理器。
927 0
老司机的 redis 数据迁移笔记
老服务器上内存一直报警,所以要把一部分redis数据迁移到新服务器上去。 迁移的方式有两种,一种是停服务器,搬迁数据;另一种通过主从同步转移。 停服务器,搬迁数据 首先在原服务器上执行redis-cli shutdown命令,该命令会触发保证写RDB文件以及将AOF文件写入磁盘,不会丢失数
14817 0
开启数据智慧,阿里云大数据团队调研高新区
随着“云计算”、“互联网”、“物联网”的快速发展,大数据(Big Data)也吸引了越来越多的人关注,成为社会热点之一。大街小巷不论是技术人员、咨询人士以及各行各业的精英达人都在探讨着“大数据”,“大数据”显然已经成为新一代“网红”。
2011 0
+关注
橘子和香蕉
香蕉橘子
23
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载