算法-最短路径: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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券