7.6 最短路径

01

前言

1、假若要在计算机上建立一个交通资讯系统则可以采用图的结构来表示实际的交通网络。

2、考虑到交通图的有向行(如航运,逆水和顺水时的船速就不一样)带权有向图中,称路径上的第一个顶点为源点,最后一个顶点为终点。

02

最短路径

1、求最短路径的一个办法是,每次以一个顶点为源点,重复执行迪杰斯特拉算法n次。这样,便可求得每一对顶点之间的最短路径。总的执行时间为O(n的3次方)。

2、弗洛依德算法:通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 从图的带权邻接矩阵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^

如果您觉得本篇文章对您有作用,请转发给更多的人,点一下好看就是对小编的最大支持!

本文分享自微信公众号 - C语言入门到精通(gh_780327809188),作者:闫小林

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 5.3 矩阵的压缩存储

    1、矩阵是很多科学与工程计算问题中研究的数学对象,如何存储矩阵的元,从而使矩阵的各种算法能有效地进行。

    闫小林
  • 编程小白 | 每日一练(157)

    这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

    闫小林
  • C语言 | 每日基础(25)

    读者:用预定义宏 #define Nullptr(type) (type *)0 帮助创建正确类型 的空指针。

    闫小林
  • 【每日一题】1445: [蓝桥杯][历届试题]最大子阵

    节日快乐,筒子们! 不过小编还是给大家准备了每日一题! 2333 题目描述 给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。 其...

    编程范 源代码公司
  • 5.3 矩阵的压缩存储

    1、矩阵是很多科学与工程计算问题中研究的数学对象,如何存储矩阵的元,从而使矩阵的各种算法能有效地进行。

    闫小林
  • 矩阵的基本知识构造重复矩阵的方法——repmat(xxx,xxx,xxx)构造器的构造方法单位数组的构造方法指定公差的等差数列指定项数的等差数列指定项数的lg等差数列sub2ind()从矩阵索引==》

    要开始学Matlab了,不然就完不成任务了 java中有一句话叫作:万物皆对象 在matlab我想到一句话:万物皆矩阵 矩阵就是Java中的数组 ...

    用户1174983
  • C++蛇形矩阵算法

    它由1开始的自然数依次排列成的一个矩阵上三角形、环形或对角线等的走法,输入文件由一行或多行构成,每行由一个正整数N组成(N不大于100)。在程序设计时需要运用到...

    老九学堂-小师弟
  • 13.高斯消去法(2)——三角矩阵

      对于矩阵有一类特殊的矩阵,叫做三角矩阵。 ?   这种矩阵如果还是按照定义一个二维数组来对数值进行存储的话,无疑将消耗掉不必要的空间,所以我们采用压缩存储的...

    用户1148394
  • matlab矩阵及其运算(六)

    上一期中二狗给大家介绍了广义逆矩阵,并且给出了广义逆矩阵的四种类型,本期二狗带大家对三种常见的广义逆矩阵的求解方法和性质进行讲解。

    艾木樨
  • 编程小白 | 每日一练(157)

    这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

    闫小林

扫码关注云+社区

领取腾讯云代金券