当前位置:   article > 正文

【数据结构】图——最短路径_从带权有向图(求最短路径通常是有向图)g中的某一顶点出发,找出一条通往另一顶点的

从带权有向图(求最短路径通常是有向图)g中的某一顶点出发,找出一条通往另一顶点的

最短路径问题:从在带权有向图G中的某一顶点出发,找出一条通往另一顶点的最短路径,最短也就是沿路径各边的权值总和达到最小。

最短路径分为图中单源路径和多源路径。

本文会介绍Dijkstra和Bellman-Ford解决单源路径的问题

Floyd-Warshall解决多路径的问题

单源最短路径--Dijkstra算法

单源问题,对于图中给定的结点u,求出到达各个结点v的路径代价和最小。最小路径可能是直接u->v

也可能是从u->t->v  。

Dijkstra算法就是解决所有边非负权值的最短路径。一般是从给出点u到终点v.

算法的思路

将图中的所有结点可以分为S和Q,S是已经确定最短路径的集合,Q是还没被访问的集合)(初始化时,将s放到集合中)

每一次从Q中选出一个s到Q代价最小的点u,把u从s移出放到S中,对u的相邻v 进行松弛更新。

松弛更新:判断s->u(已经确定了)  u->v的路径是否小于s->v(已经确定的)

如果是的话,就更新s->v

直到更新所有的Q结点

在我们的模拟实现中

保存一张dist[]数组,用来表示s到某点的最短路径

S[]数组用来表示已经确定最短路径的顶点、

pPath用来存储路径前一个顶点的下标

通过画图梳理这个过程

首次初始化时,dist数组s位置是0,其它为无穷,pPath数组s位置是缺省值

第二轮:寻找最短路径s-s 松弛更新出s->t s->y

第三步 选出最小v  s->y(s->s已经被标记过)

松弛更新出s-y-t s-y-x s-y-z

第三轮选边 选出s->z 对z相邻的边松弛更新

s->z->x(13)

s->z->s(14 不更新)

第四轮

选边s->t

第五轮 选出s->x 松弛更新出 x->z(不更新,已经是最短路径)

松弛更新不适合用于带负权值的路径

因为无法确定第一轮的最小值

  1. void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
  2. {
  3. size_t srci = GetVertexIndex(src);
  4. size_t n = _vertexs.size();
  5. dist.resize(n, MAX_W);
  6. pPath.resize(n, -1);
  7. //自身就是0
  8. dist[srci] = W();
  9. pPath[srci] = srci;
  10. //标记容器
  11. vector<bool> S(n, false);
  12. for (size_t j = 0; j < n; j++)
  13. {
  14. int u = 0;
  15. W min = MAX_W;
  16. for (size_t i = 0; i < n; i++)
  17. {
  18. if (S[i] == false && dist[i] < min)
  19. {
  20. u = i;
  21. min = dist[i];
  22. }
  23. }
  24. S[u] = true;
  25. //松弛更新
  26. for (size_t v = 0; v < n; v++)
  27. {
  28. if (S[v] == false && _matrix[u][v] != MAX_W &&
  29. dist[u] + _matrix[u][v] < dist[v])
  30. {
  31. dist[v] = dist[u] + _matrix[u][v];
  32. pPath[v] = u;
  33. }
  34. }
  35. }
  36. }

单源最短路径--Bellman-Ford算法
 

迪杰斯特拉算法不能解决带负权值边的最短路径,贝尔曼福特就采用暴力的方式解决了带负权值边的路径问题,还能判断出回路是否带有负权值。

贝尔曼福特算法的思路是将 srci-> j的路径问题划分为srci-> i  i->j的路径最短问题

对于从源顶点 s  到目标顶点 j 的路径来说,如果存在从源顶点 s 到顶点 i 的路径,还存在一条从顶点 i  到顶点 j  的边,并且其权值之和小于当前从源顶点 s  到目标顶点 j 的路径长度,则可以对顶点 j j 的估计值和前驱顶点进行松弛更新。

是利用已经确定的最短路径srci -i 再加上i->j的边权来更新的最短路径。

确定完所有的顶点后,都必须重新进行更新,因为每一条路径的确定,都有可能影响前一轮的路径更新。故需要遍历K次。K为N次。(因为所有的点都在变,都需要更新。)

初始化时,dist[srci]初始化为缺省值

第一次i==0时,更新出t y

第二次,i==1更新出x z 

i==2时,更新出 x s(不更新,目前是最短路径)

i==3时,更新出t->z

i==4时,用x更新出t

结束第一轮

此时还需要进行下一轮的更新

下一轮再i==3时,更新出t->z=-4

  1. bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
  2. {
  3. size_t n = _vertexs.size();
  4. size_t srci = GetVertexIndex(src);
  5. dist.resize(n, MAX_W);
  6. pPath.resize(n, -1);
  7. dist[srci] = W();
  8. //最多更新k轮
  9. for (size_t k = 0; k < n; k++)
  10. {
  11. bool updata = false;
  12. cout << "更新第:" << k << "轮" << endl;
  13. //srci->i+i->j
  14. for (size_t i = 0; i < n; i++)
  15. {
  16. for (size_t j = 0; j < n; j++)
  17. {
  18. if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
  19. {
  20. updata = true;
  21. cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
  22. dist[j] = dist[i] + _matrix[i][j];
  23. pPath[j] = i;
  24. }
  25. }
  26. }
  27. if (!updata)
  28. break;
  29. }
  30. //如果还能更新,就是带负路径
  31. for (size_t i = 0; i < n; i++)
  32. {
  33. for (size_t j = 0; j < n; j++)
  34. {
  35. if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j])
  36. {
  37. return false;
  38. }
  39. }
  40. }
  41. return true;
  42. }

利用程序编写过程和我们的画图一致

贝尔曼福特算法是暴力求解,有相当高的时间复杂度O(N^3),但是能够解决负权值问题。


多源最短路径--Floyd-Warshall算法

Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。

弗洛伊德算法考虑的是中间最短路径的中间结点,设k是p的一个中间节点,那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1,p2。p1是从i到k且中间节点属于{1,2,…,k-1}取得的一条最短路径。p2是从k到j且中间节点属于{1,2,…,k-1}取得的一条最短路径。

Floyd-Warshall算法是一种动态规划算法,其运行时间为o(n^3)与最短路径路径上通常的假设一样,假设权重可以为负,但不能有权重为负的环路

如果存在从顶点 i  到顶点 k  的路径,还存在从顶点 k  到顶点 j  的路径,并且这两条路径的权值之和小于当前从顶点 i 到顶点 j 的路径长度,则可以对顶点 j  的估计值和前驱顶点进行松弛更新。

算法原理:

费洛伊徳算法就是将最短路径分成dist[i][k]+ dist[k][j]与dist[k][j]的问题

算法需要一个二维的vvdist记录最短路径,vvpPath标记父路径

将直接相连的视作最短路径 

进行k次更新(K为n,i和j都在变换)

动态规划更新vvdist

注意vvpPath[i][j]的前一个不再是i而应该是递归的vvpPath[k][j],可能变化一次,也可能变化好多次

  1. void FloydWarshall(vector<vector<W>>& vvDist, vector<vector<int>>& vvpPath)
  2. {
  3. size_t n = _vertexs.size();
  4. vvDist.resize(n, vector<W>(n, MAX_W));
  5. vvpPath.resize(n, vector<int>(n, -1));
  6. //更新权值和父路径
  7. for (size_t i = 0; i < n; i++)
  8. {
  9. for (size_t j = 0; j < n; j++)
  10. {
  11. if (_matrix[i][j] != MAX_W)
  12. {
  13. vvDist[i][j] = _matrix[i][j];
  14. vvpPath[i][j] = i;
  15. }
  16. if (i == j)
  17. {
  18. vvDist[i][j] = W();
  19. }
  20. }
  21. }
  22. //O(N^3)
  23. //最多更新k次
  24. for (size_t k = 0; k < n; k++)
  25. {
  26. for (size_t i = 0; i < n; i++)
  27. {
  28. for (size_t j = 0; j < n; j++)
  29. {
  30. //存在 i->k k->j 且<dist[i][j]
  31. if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W
  32. && vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
  33. {
  34. vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
  35. vvpPath[i][j] = vvpPath[k][j];
  36. }
  37. }
  38. }
  39. // 打印权值和路径矩阵观察数据
  40. for (size_t i = 0; i < n; ++i)
  41. {
  42. for (size_t j = 0; j < n; ++j)
  43. {
  44. if (vvDist[i][j] == MAX_W)
  45. {
  46. //cout << "*" << " ";
  47. printf("%3c", '*');
  48. }
  49. else
  50. {
  51. //cout << vvDist[i][j] << " ";
  52. printf("%3d", vvDist[i][j]);
  53. }
  54. }
  55. cout << endl;
  56. }
  57. cout << endl;
  58. for (size_t i = 0; i < n; ++i)
  59. {
  60. for (size_t j = 0; j < n; ++j)
  61. {
  62. //cout << vvParentPath[i][j] << " ";
  63. printf("%3d", vvpPath[i][j]);
  64. }
  65. cout << endl;
  66. }
  67. cout << "=================================" << endl;
  68. }
  69. }

最短路径的总结

迪杰斯特拉算法是基于贪心算法设计,解决非负数权值的路径问题。将顶点分为S和Q,每次都从Q中选出最小的权值u放到s中,然后将u的相邻边进行松弛调整。

贝尔曼福特算法是暴力求解,能求解出带负权值的路径,能判断负权环路。是一个时间复杂度为o(N^3)的算法。要进行K次松弛调整。每一次都是通过dist[i]+_matrix[i][j]更新权值

费洛伊徳算法是动态规划的思想,将路径分为i->k k->j的思想。同样要进行K轮次的更新。复杂度为0(N^3)。能够求解任意俩顶点的最短路径。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/神奇cpp/article/detail/842811
推荐阅读
相关标签
  

闽ICP备14008679号