专栏首页WebJ2EE算法-最短路径:DAG、Dijkstra、Bellman-Ford

算法-最短路径:DAG、Dijkstra、Bellman-Ford

1. 最短路径 —— DAG

1.1. 前置条件

  • 图必须是有向无环图(DAG)。

1.2. 基本原理

DAG上一定存在拓扑排序,且若在有向图 G 中从顶点 u -> v有一条路径,则在拓扑排序中顶点 u 一定在顶点 v 之前,而因为在DAG图中没有环,所以按照DAG图的拓扑排序进行序列最短路径的更新,一定能求出最短路径。

1.3. 代码示例

题目:给定几个带点权有向无环图,选一条从入度为0的起点走到出度为0的终点的路径,使得路径上的点权和最小。

分析:

  • 首先点权图转边权图;
  • 直接对每条边赋值,值为终点的点权值;
  • 没有入度的点,添加一个顶点,连接一条有向边,使之边权等于该点点权。

1.4. 特性分析

  • 时间复杂度:O(n+m);

2. 最短路径 —— Dijkstra 算法

2.1. 前置条件

  • 所有边的权重一定是非负的;
  • 图中可以包含环

2.2. 基本思路

(1) 找出“最便宜”的节点,即可在最短时间内到达的节点。

(2) 更新该节点对应的邻居节点的开销。

(3) 重复这个过程,直到对图中的每个节点都这样做了。

(4) 计算最终路径。

2.3. 程序代码

2.4. 动画展示

2.5. 特性分析

  • 时间复杂度:O(n^2);

3. 最短路径 —— Bellman-Ford 算法

3.1. 前置条件

  • 单源最短路径(从源点s到其它所有顶点v);
  • 边权可正可负
  • 图中可以包含环
  • 可以判定是否具有负权重和环;

3.2. 基本思路

  • 将除源点外的所有顶点的最短距离估计值 d[v] <-- ∞, d[s] <-- 0;
  • 反复对边集 E 中的每条边进行松弛操作,使得顶点集V中的每个顶点 v 的最短距离估计值逐步逼近其最短距离(运行|v|-1次);

3.3. 程序代码

3.4. 特性分析

  • 时间复杂度:O(nm)

本文分享自微信公众号 - WebJ2EE(WebJ2EE),作者:WEBJ2EE

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Bellman-Ford算法--解决负权边的单源最短路径算法

    在http://blog.csdn.net/hacker_zhidian/article/details/54915152这篇博客中,我们用Dijkstra算法...

    指点
  • 最短路算法实现与分析:Dijkstra算法,Floyed,Bellman-Ford, SPFA算法;

    最短路算法:最短路径算法是图论研究中,一个经典算法问题;旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。

    xuyaowen
  • 数据结构(十二):最短路径(Dijkstra算法)

    Dijkstra 算法使用贪心策略计算从起点到指定顶点的最短路径,通过不断选择距离起点最近的顶点,来逐渐扩大最短路径权值,直到覆盖图中所有顶点。

    zhipingChen
  • 单源最短路径之Bellman-Ford算法

    贝尔曼-福特算法(Bellman-Ford)是由理查德·贝尔曼(Richard Bellman) 和 莱斯特·福特 创立的,求解单源最短路径问题的一种算法。有时...

    每天学Java
  • 加权有向图----一般性单源最短路径问题(Bellman-Ford算法)

    SuperHeroes
  • 算法专题 | 10行代码实现的最短路算法——Bellman-ford与SPFA

    最短路问题也属于图论算法之一,解决的是在一张有向图当中点与点之间的最短距离问题。最短路算法有很多,比较常用的有bellman-ford、dijkstra、flo...

    TechFlow-承志
  • HAWQ + MADlib 玩转数据挖掘之(十)——图算法之单源最短路径

    一、图算法简介 1. 定义         在计算中,常将运算方程或实验结果绘制成由若干有标尺的线条所组成的图,称为“算图”。计算时根据已知条件,从有关线段上一...

    用户1148526
  • MADlib——基于SQL的数据挖掘解决方案(28)——图算法之单源最短路径

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/...

    用户1148526
  • 最短路算法目录

    风骨散人Chiam
  • 计蒜客 - 闯关游戏 | SPFA

    蒜头君在玩一个很好玩的游戏,这个游戏一共有至多 个地图,其中地图 是起点,房间 是终点。有的地图是补给站,可以加 点体力,而有的地图里存在怪物,需要消耗...

    凝神长老
  • 数据结构与算法——图最短路径

    最短路径问题一直是图论研究的热点问题。例如在实际生活中的路径规划、地图导航等领域有重要的应用。关于求解图的最短路径方法也层出不穷,本篇文章将详细讲解图的最短路...

    五分钟学算法
  • 对比 Dijkstra Bellman—Ford Spfa 最短路之间区别

    本质上Dijkstra是一种贪心,满足局部最优,每次找的是离起点最近的(保证了这个点的距离就是最短路),如果有负边权,当前找到的就不一定是最近的了。

    ACM算法日常
  • [数据结构拾遗]图的最短路径算法

    在需要使用到相应算法时,能够帮助你回忆出常用的实现方案并且知晓其优缺点和适用环境。并不涉及十分具体的实现细节描述。

    蛮三刀酱
  • [数据结构拾遗]图的最短路径算法

    在需要使用到相应算法时,能够帮助你回忆出常用的实现方案并且知晓其优缺点和适用环境。并不涉及十分具体的实现细节描述。

    Rude3Knife的公众号
  • 10 行实现最短路算法

    在上一篇文章当中我们讲解了bellman-ford算法和spfa算法,其中spfa算法是我个人比较常用的算法,比赛当中几乎没有用过其他的最短路算法。但是spfa...

    double
  • 一文搞懂戴克斯特拉算法-dijkstra

    大学学习数据结构那会,当时记得终于把 dijkstra 算法搞明白了,但是今天碰到的时候,大脑又是一片空白,于是我就又学习了下,把自己的理解写下来,希望你也可以...

    somenzz
  • 加权有向图----单点最短路径问题(Dijkstra算法)

    SuperHeroes
  • 关于SPFA Bellman-Ford Dijkstra Floyd BFS最短路的共同点与区别

    对于BFS来说,他没有松弛操作,他的理论思想是从每一点做树形便利,那么时间复杂度绝对是在大型图中难以接受的,所以BFS题目设计很精巧,数据限制,更重要的是他可以...

    风骨散人Chiam
  • 数据结构(十一):最短路径(Bellman-Ford算法)

    最短路径是指连接图中两个顶点的路径中,所有边构成的权值之和最小的路径。之前提到的广度优先遍历图结构,其实也是一种计算最短路径的方式,只不过广度遍历中,边的长度都...

    zhipingChen

扫码关注云+社区

领取腾讯云代金券