最短路径问题

发表于 更新于 分类于

图论，求两点之间的最短路径

我记得一共有3种算法： Bellman-Ford algorithm、、 总结一下然后找个例题，用c++写一遍 希望这一篇不会鸽了 好像有向图和无向图有一点不一样

Bellman-Ford

最简单、时间复杂度最高，含有动态规划的思想

参考：https://www.cnblogs.com/gaochundong/p/bellman_ford_algorithm.html 9月5日之前写完bellman-ford这一部分

基础算法

步骤

  1. 创建源顶点 v 到图中所有顶点的距离的集合 distSet，为图中的所有顶点指定一个距离值，初始均为 Infinite，源顶点距离为 0；
  2. 计算最短路径，执行 V - 1 次遍历：对于图中的每条边：如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d，则更新终点 v 的距离值 d；
  3. 检测图中是否有负权边形成了环，遍历图中的所有边，计算 u 至 v 的距离，如果对于 v 存在更小的距离，则说明存在环；

伪代码

1
2
3
4
5
6
7
8
9
BELLMAN-FORD(G, w, s)
  INITIALIZE-SINGLE-SOURCE(G, s)
  for i  1 to |V[G]| - 1
       do for each edge (u, v)  E[G]
            do RELAX(u, v, w)
  for each edge (u, v)  E[G]
       do if d[v] > d[u] + w(u, v)
            then return FALSE
  return TRUE

分析

  1. 初始化一个数组dist，起点和其它点
  2. 进行边数-1次循环（为什么？包含n个点的图，最短路径最多经过n-1条边）
    1. 对图上的每条边：
      1. 边的起点u和终点v
      2. 如果dist[u]+这条边的长度小于dist[v]，那就用和更新dist[v]
      3. 否则不变
  3. 第n次更新，如果出现dist[v]大于dist[u]+边长的情况，就表示出现了负环路

复杂度分析

实现的时间复杂度为 O(V*E)，其中 V 为顶点数量，E 为边的数量。因为第 2 行的初始化占用了 Θ(V)，第 3-4 行对边进行了 V - 1 趟操作，每趟操作的运行时间为 Θ(E)。第 6-7 行的 for 循环运行时间为 O(E)。

动态规划在哪

令d(v,k)表示源点s到顶点v且最多含有k条边的最短路径，于是d(v,n−1)就是我们的目标。如果一条路径具有n nn条以上的边，则一定有环路。

对k=0

\[ d(v,0)= \left\{ \begin{array}{rcl} 0 & & {v=s}\\ \infty & & {v\not ={s}} \end{array} \right. \]

对0＜k≤n−1，有\(d(v,k)=min{d(u,k−1)+cost(u,v)∣u是v的前驱顶点}\)

c++代码

参考https://www.bilibili.com/video/BV1cj421S7Wi/?spm_id_from=333.337.search-card.all.click&vd_source=52a8e0c923505716d18229113eb20c33

例题

  1. leetcode.1514 无向，乘法