Bellman-ford 代码实现 - c++编程基础

Dijkstra算法:
首先求出长度最短的一条边,再参照它求出长度次短的一条最短路径,直到从源点v0到其他各顶点的最短路径全部求出,想法不是很复杂,就是代码实现的有些奇妙啊
Bellman-ford算法
设有向网有n个顶点且不存在负权值回路(总权值为负数),则从v1到v2至多有n-1条边,以此为依据,计算出从v1 到各点的最短路径长度在某些方面与Dijkstra算法是相似的,只是比它还要更复杂

修改一次边称为一次松弛.

下面给出测试数据,第一行是顶点个数n,,然后输入每条边的数据,格式为u,v,w分别表示这条边的起点,终点和权值,顶点从0开始记起,最后一行为-1 -1 -1 ,表示数据输入的结束.

将数据保存为in.txt与源代码放在同一目录下.

/*we start 0 */
#include
  
   
#include
   
     #include
    
      using namespace std; #define INF 1000000 #define MAXN 10 int n; int edge[MAXN][MAXN]; int dist[MAXN]; int path[MAXN]; /*Bellman algorithm hell * init the function * here,the meaning of expression of dist[] and path[] * dist[] is distance ,path[2]=0 means vertex 0 to vertex 2 directed way the vertex 0 is fronter,else is -1 */ void Bellman(int v0) { int i,j,k,u;//k是表示从源点到各点的线路条数,u就是从0到那个顶点 for(i=0;i
     
      >n; // memset(edge,0,sizeof(edge)); while(1) { scanf("%d%d%d",&u,&v,&w); if(u==-1 && v==-1 && w==-1) break; edge[u][v]=w; } for(i=0;i
      
       0;j--) printf("%d-->",shortest[j]); printf("%d\n",shortest[0]); } return 0; }

测试数据:

即

运行结果如下: