AI 助理
备案控制台
开发者社区 人工智能 文章 正文

含有负边的图的最短路径（Bellman_ford算法）

2017-12-25 1418
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

更新所有的边，每条边更新V-1次，时间复杂度为O(V*E).

有些更新操作是重复了的，这里可以考虑检查多余的重复操作作，如果没有更新发生，则立即终止算法。

[c-sharp]  view plain copy print ?
  1. #include<iostream>      
  2. #include<malloc.h>      
  3. #include<queue>    
  4. #include <algorithm>     
  5. #include<stdlib.h>    
  6. #include<functional>  
  7. using namespace std;      
  8.    
  9. #define maxNum 100 //定义邻接举证的最大定点数    
  10. #define maxWeight 1000000 //边权最大值    
  11. //顶点信息  
  12. typedef struct  
  13. {  
  14.     int id;  
  15.     int dist;  
  16. }node;  
  17. //图的邻接矩阵表示结构      
  18. typedef struct      
  19. {      
  20.     //char v[maxNum];//图的顶点信息   
  21.     node v[maxNum];  
  22.     int e[maxNum][maxNum];//图的顶点信息      
  23.     int vNum;//顶点个数      
  24.     int eNum;//边的个数      
  25. }graph;  
  26. //函数声明    
  27. void createGraph(graph *g);//创建图g   
  28. //Bellman_ford算法  
  29. void Bellman_ford(graph *g)  
  30. {  
  31.     int k,i,j;    
  32.     //初始化dist的值  
  33.     for(i=1;i<=g->vNum;i++)    
  34.     {  
  35.         g->v[i].dist=maxWeight;  //dist为最大值  
  36.         g->v[i].id=i;  
  37.     }  
  38.     g->v[1].dist=0;//1作为源点，dist为0  
  39.     for(k=1;k<=g->vNum;k++)//V-1次循环  
  40.     {  
  41.         for(i=1;i<=g->vNum;i++)  
  42.         {  
  43.             for(j=1;j<=g->vNum;j++)  
  44.             {  
  45.                 if(g->e[i][j]!=maxWeight)  
  46.                     if(g->v[j].dist>(g->v[i].dist+g->e[i][j]))  
  47.                         g->v[j].dist=g->v[i].dist+g->e[i][j];  
  48.             }  
  49.         }  
  50.         //for(int p=1;p<=g->vNum;p++)//输出每次更新完以后的dist  
  51.         //  cout<<g->v[p].dist<<" ";  
  52.         //cout<<endl;  
  53.     }  
  54. }  
  55. void createGraph(graph *g)//创建图g      
  56. {      
  57.     cout<<"正在创建无向图..."<<endl;      
  58.     cout<<"请输入顶点个数vNum:";      
  59.     cin>>g->vNum;       
  60.     int i,j;    
  61.     //构造邻接矩阵，顶点到自身的距离是无穷大的。    
  62.     cout<<"输入邻接矩阵权值："<<endl;   
  63.     for(i=1;i<=g->vNum;i++)  
  64.         for(j=1;j<=g->vNum;j++)  
  65.         {  
  66.             cin>>g->e[i][j];  
  67.             if(g->e[i][j]==0)  
  68.                 g->e[i][j]=maxWeight;  
  69.         }  
  70. }      
  71.       
  72. int main()      
  73. {      
  74.     graph *g;      
  75.     g=(graph*)malloc(sizeof(graph));      
  76.     createGraph(g);      
  77.     Bellman_ford(g);   
  78.     cout<<"Dijkstra算法单源(源为1)最短路径为："<<endl;  
  79.     for(int k=1; k<=g->vNum; k++)  
  80.     {  
  81.         cout<<g->v[k].dist<<" ";  
  82.     }  
  83.     cout<<endl;  
  84.     system("pause");    
  85.     return 0;      
  86. }      
  87. /* 
  88. 正在创建无向图... 
  89. 请输入顶点个数vNum:8 
  90. 输入邻接矩阵权值： 
  91. 0 10 0 0 0 0 0 8 
  92. 0 0 0 0 0 2 0 0 
  93. 0 1 0 1 0 0 0 0 
  94. 0 0 0 0 3 0 0 0 
  95. 0 0 0 0 0 -1 0 0 
  96. 0 0 -2 0 0 0 0 0 
  97. 0 -4 0 0 0 -1 0 0 
  98. 0 0 0 0 0 0 1 0 
  99. Dijkstra算法单源(源为1)最短路径为： 
  100. 0 5 5 6 9 7 9 8 
  101. 请按任意键继续. . . 
  102. */  
 

 

 

ps:2011-6-15

1.修改：dist单独列出一个数组存放，不在将dist值存放在图中。

2.输出dist修改过程，发现后续的dist没有发生变化，可以通过一个检查函数来判断，如果dist前后没有发生变化则表明已经找到最短路径

代码实例：

[c-sharp]  view plain copy print ?
  1. #include<iostream>      
  2. #include<malloc.h>      
  3. #include<queue>    
  4. #include <algorithm>     
  5. #include<stdlib.h>    
  6. #include<functional>  
  7. using namespace std;      
  8.    
  9. #define maxNum 100 //定义邻接举证的最大定点数    
  10. #define maxWeight 1000000 //边权最大值    
  11. int dist[maxNum];//定义数组，默认情况下数组中的所有元素都为0  
  12. //图的邻接矩阵表示结构      
  13. typedef struct      
  14. {      
  15.     char v[maxNum];//图的顶点信息   
  16.     int e[maxNum][maxNum];//图的顶点信息      
  17.     int vNum;//顶点个数      
  18.     int eNum;//边的个数      
  19. }graph;  
  20. //函数声明    
  21. void createGraph(graph *g);//创建图g   
  22. void Bellman_ford(graph *g);  
  23. //Bellman_ford算法  
  24. void Bellman_ford(graph *g)  
  25. {  
  26.     int k,i,j,p;    
  27.     //初始化dist的值  
  28.     for(i=1;i<=g->vNum;i++)    
  29.     {  
  30.         dist[i]=maxWeight;  
  31.     }  
  32.     dist[1]=0;  
  33.     for(i=1;i<=g->vNum;i++)    
  34.     {  
  35.         cout<<dist[i]<<" ";  
  36.     }  
  37.     cout<<endl;  
  38.     cout<<"输出"<<g->vNum<<"次迭代过程中的dist值"<<endl;  
  39.     for(k=1;k<=g->vNum;k++)//V-1次循环  
  40.     {  
  41.         //更新每一条边的权值  
  42.         for(i=1;i<=g->vNum;i++)  
  43.         {  
  44.             for(j=1;j<=g->vNum;j++)  
  45.             {  
  46.                 if(g->e[i][j]!=maxWeight&&dist[i]!=maxWeight)//如果i->j之间存在路径  
  47.                 {  
  48.                     if(dist[j]>dist[i]+g->e[i][j])  
  49.                     {  
  50.                         dist[j]=dist[i]+g->e[i][j];  
  51.                           
  52.                     }  
  53.                   
  54.                 }  
  55.             }  
  56.         }  
  57.         for(i=1;i<=g->vNum;i++)  
  58.         {  
  59.             cout<<dist[i]<<" ";  
  60.         }  
  61.         cout<<endl;  
  62.     }  
  63. }  
  64. void createGraph(graph *g)//创建图g      
  65. {      
  66.     cout<<"正在创建无向图..."<<endl;      
  67.     cout<<"请输入顶点个数vNum:";      
  68.     cin>>g->vNum;       
  69.     int i,j;    
  70.     //构造邻接矩阵，顶点到自身的距离是无穷大的。    
  71.     cout<<"输入邻接矩阵权值："<<endl;   
  72.     for(i=1;i<=g->vNum;i++)  
  73.         for(j=1;j<=g->vNum;j++)  
  74.         {  
  75.             cin>>g->e[i][j];  
  76.             if(g->e[i][j]==0)  
  77.                 g->e[i][j]=maxWeight;  
  78.         }  
  79. }      
  80.       
  81. int main()      
  82. {      
  83.     graph *g;      
  84.     g=(graph*)malloc(sizeof(graph));      
  85.     createGraph(g);      
  86.     Bellman_ford(g);   
  87.     cout<<"Dijkstra算法单源(源为1)最短路径为："<<endl;  
  88.     for(int k=1; k<=g->vNum; k++)  
  89.     {  
  90.         cout<<dist[k]<<" ";  
  91.     }  
  92.     cout<<endl;  
  93.     system("pause");    
  94.     return 0;      
  95. }      
  96. /* 
  97. 正在创建无向图... 
  98. 请输入顶点个数vNum:8 
  99. 输入邻接矩阵权值： 
  100. 0 10 0 0 0 0 0 8 
  101. 0 0 0 0 0 2 0 0 
  102. 0 1 0 1 0 0 0 0 
  103. 0 0 0 0 3 0 0 0 
  104. 0 0 0 0 0 -1 0 0 
  105. 0 0 -2 0 0 0 0 0 
  106. 0 -4 0 0 0 -1 0 0 
  107. 0 0 0 0 0 0 1 0 
  108. 0 1000000 1000000 1000000 1000000 1000000 1000000 1000000 
  109. 输出8次迭代过程中的dist值 
  110. 0 10 10 1000000 1000000 12 9 8 
  111. 0 5 10 11 14 8 9 8 
  112. 0 5 5 11 14 7 9 8 
  113. 0 5 5 6 9 7 9 8 
  114. 0 5 5 6 9 7 9 8 
  115. 0 5 5 6 9 7 9 8 
  116. 0 5 5 6 9 7 9 8 
  117. 0 5 5 6 9 7 9 8 
  118. Dijkstra算法单源(源为1)最短路径为： 
  119. 0 5 5 6 9 7 9 8 
  120. 请按任意键继续. . . 
  121. */  

 




本文转自xwdreamer博客园博客，原文链接：http://www.cnblogs.com/xwdreamer/archive/2011/06/14/2297002.html，如需转载请自行联系原作者


文章标签：
算法
关键词：
算法最短路径
最短路径算法
算法图
算法bellman_ford
嗯哼9925
目录
相关文章
java冯坚持
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法，这两种算法分别用于解决单源和多源最短路径问题，并且提供了Java语言的实现代码。
java冯坚持
79 3
数据结构与算法细节篇之最短路径问题：Dijkstra和Floyd算法详细描述，java语言实现。
东方睿赢
|
6月前
|
存储 算法 Java
Java中，树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中，树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点，而BFS利用队列按层次访问。以下是简化的代码片段：[Java代码略]
东方睿赢
48 4
VipSoft
|
4月前
|
自然语言处理 算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
VipSoft
59 0
HanLP — HMM隐马尔可夫模型 - 路径规划算法 - 求解最短路径 - 维特比(Viterbi)算法
亚丁号
|
5月前
|
算法 Java
Java语言实现最短路径算法（Shortest Path）
Java语言实现最短路径算法（Shortest Path）
亚丁号
62 3
VipSoft
|
4月前
|
算法 定位技术
路径规划算法 - 求解最短路径 - A*（A-Star)算法
路径规划算法 - 求解最短路径 - A*（A-Star)算法
VipSoft
94 0
VipSoft
|
4月前
|
算法
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
路径规划算法 - 求解最短路径 - Dijkstra(迪杰斯特拉)算法
VipSoft
72 0
众所周知
|
5月前
|
存储 算法 Python
“解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系，通过节点和边连接。常见的表示方法是邻接矩阵（适合稠密图）和邻接表（适合稀疏图）。图遍历包括DFS（深度优先搜索）和BFS（广度优先搜索）：DFS深入探索分支，BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
众所周知
45 1
AIGC小王子
|
5月前
|
数据采集 存储 算法
「AIGC算法」图搜索算法详解
本文探讨了图搜索算法，包括遍历和最短路径搜索。DFS和BFS是遍历算法，前者使用栈深入搜索，后者用队列逐层遍历。Dijkstra、Bellman-Ford、A*、Floyd-Warshall和Johnson算法则解决最短路径问题。文中还给出了DFS的Python实现示例。这些算法在路径规划、网络分析等领域有重要应用。
AIGC小王子
94 0
weixin_836869520
|
6月前
|
算法 Java
Java数据结构与算法：最短路径算法
Java数据结构与算法：最短路径算法
weixin_836869520
70 0
weixin_836869520
|
6月前
|
算法 Java 定位技术
Java数据结构与算法：贪心算法之最短路径
Java数据结构与算法：贪心算法之最短路径
weixin_836869520
42 0

热门文章

最新文章

  • 1
    【编程练习】收集的一些c++代码片，算法排序，读文件，写日志，快速求积分等等
  • 2
    字符串相似度算法 递归与动态规划求解分析
  • 3
    【TDOA定位】基于chan和talor算法实现TDOA定位含性能对比matlab代码
  • 4
    【算法】算法之美—Fire Net
  • 5
    深入理解MySQL中的Join算法
  • 6
    openssl中算法的组织方式
  • 7
    【算法研究】Bresenham画线算法
  • 8
    算法导论第十四章 数据结构的扩张
  • 9
    JVM内存模型及垃圾回收算法
  • 10
    【字符串处理算法】删除特定的字符的算法设计及C代码实现
  • 1
    带你读《阿里云产品六月刊》——十四、【CVPR2024】阿里云人工智能平台PAI图像编辑算法论文入选CVPR2024
    154
  • 2
    基于粒子群优化的图像融合算法matlab仿真
    60
  • 3
    基于鲸鱼优化的DSN弱栅栏覆盖算法matlab仿真
    59
  • 4
    算法金 | 秒懂 AI - 深度学习五大模型：RNN、CNN、Transformer、BERT、GPT 简介
    160
  • 5
    实战算法的基础入门（3）
    62
  • 6
    实战算法的基础入门（2）
    56
  • 7
    实战算法的基础入门（1）
    82
  • 8
    分库分表主键生成 - 自增主键 雪花类算法 分段
    76
  • 9
    基于改进K-means的网络数据聚类算法matlab仿真
    79
  • 10
    瓴羊Quick Service智能客服算法通过国家网信办深度合成服务算法备案
    98

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    无影云桌面