数据结构与算法 ~ 图 ~ 最短路径 ~ 贝尔曼-福特算法（图采用邻接矩阵储存）

/*graph---bellman-ford*/
#include<stdlib.h>
#include<stdio.h>
#define MAX 10
struct vexnode{
	        int visited;/*访问标志*/
              }vex[MAX];
int array[MAX][MAX];/*存放权值*/
int vexnum=-1;

/*创建图的邻接矩阵*/
void create(){
	int source,destination,weight,max;
	int i,j;
	for(i=0;i<MAX;i++)
		for(j=0;j<MAX;j++)  
			array[i][j]=999;	
	printf("\n===创建图===\n");
	printf("\n请输入弧的信息：起点  终点  权值(退出-1):");
	scanf("%d%d%d",&source,&destination,&weight);
	while (source!=-1){
		array[source][destination]=weight;
		array[destination][source]=weight;
		/*获得当前最大的结点信息*/
		max=(source>destination)?source:destination;
		if (max>vexnum)   
			vexnum=max;
		printf("\n请输入弧的信息：起点  终点  权值(退出-1):");
		scanf("%d%d%d",&source,&destination,&weight);
    }/*while*/
  printf("\n===图创建结束===\n");
}/*create*/

void Print(){
	int i,j,k;
	printf("\n===当前图 ====");
	printf ("\n   矩阵  :");
	for(i=1;i<=vexnum;i++)  
		printf("%10d",i);
	printf("\n");
	for(i=1;i<=vexnum;i++){
		printf("%10d:",i);
		for(j=1;j<=vexnum;j++){
			printf("%10d",array[i][j]);			
		}			
		printf("\n");
	}/*for*/
	printf("\n===图输出结束====");
}/*Print*/

/*计算从e到各顶点的最短路径*/
void BellmanFord(int e){
	int i,j,min,temp,k=0;
	int bellmanford[MAX];
	/*设置bellmanford数组用于存放从e到各结点的最短路径*/
	for(i=1;i<=vexnum;++i){
		if (i==e) bellmanford[i]=0;
		else  bellmanford[i]=999;		
	}/*for*/
	/*按照每个顶点开始遍历所有的结点,贝尔曼-福特算法*/
	for (i=1;i<=vexnum;i++){		
			for (j=i+1;j<=vexnum;j++){
				if  (array[i][j]!=999){
					if  (bellmanford[i]+array[i][j]<bellmanford[j]){						
						printf("\n\n%d--b[%d]+[%d][%d]=%d+%d=%d  < b[%d]=%d",++k,i,i,j,bellmanford[i],array[i][j],bellmanford[i]+array[i][j],j,bellmanford[j]);
						bellmanford[j]=bellmanford[i]+array[i][j];
						printf("\n更新b[%d]=%d",j,bellmanford[i]+array[i][j]);
					}						
					if  (bellmanford[j]+array[j][i]<bellmanford[i]){
						printf("\n%d--b[%d]+[%d][%d]=%d+%d=%d  < b[%d]=%d",++k,j,j,i,bellmanford[j],array[j][i],bellmanford[j]+array[j][i],i,bellmanford[i]);
						bellmanford[i]=bellmanford[j]+array[j][i];
						printf("\n更新[%d]=%d",i,bellmanford[j]+array[j][i]);
					}						
				}
			}/* for int j*/	
	}/* for int i*/
	/*输出bellman-ford数组*/
	for (i=1;i<=vexnum;i++){
		printf("\n[%d]=%d",i,bellmanford[i]);
	}	
}/*BellmanFord*/

int main(){
	int e;
	create();
	Print();
	while(1){
		printf("\n请输入起始点(exit for -1):");
		scanf("%d",&e);
		if (e==-1) 
			break;
		else if (e<0||e>vexnum) 
			printf("\n输入的起始点错误\n");
		else BellmanFord(e);
	}/*while*/
	system("pause");
	exit(0);
}/*main*/

 运行，输入图的信息

===创建图===

请输入弧的信息：起点  终点  权值(退出-1):1 2 9
请输入弧的信息：起点  终点  权值(退出-1):1 3 2
请输入弧的信息：起点  终点  权值(退出-1):2 3 6
请输入弧的信息：起点  终点  权值(退出-1):2 4 3
请输入弧的信息：起点  终点  权值(退出-1):2 5 1
请输入弧的信息：起点  终点  权值(退出-1):3 4 2
请输入弧的信息：起点  终点  权值(退出-1):3 6 9
请输入弧的信息：起点  终点  权值(退出-1):4 5 5
请输入弧的信息：起点  终点  权值(退出-1):4 6 6
请输入弧的信息：起点  终点  权值(退出-1):5 6 3
请输入弧的信息：起点  终点  权值(退出-1):5 7 7
请输入弧的信息：起点  终点  权值(退出-1):6 7 4
请输入弧的信息：起点  终点  权值(退出-1):-1 -1 -1

===图创建结束===

显示输入的结果：

===当前图 ====
   矩阵  :         1         2         3         4         5         6         7
         1:       999         9         2       999       999       999       999
         2:         9       999         6         3         1       999       999
         3:         2         6       999         2       999         9       999
         4:       999         3         2       999         5         6       999
         5:       999         1       999         5       999         3         7
         6:       999       999         9         6         3       999         4
         7:       999       999       999       999         7         4       999

===图输出结束====

确定开始结点，开始运行算法

请输入起始点(exit for -1):1

1--b[1]+[1][2]=0+9=9  < b[2]=999
更新b[2]=9

2--b[1]+[1][3]=0+2=2  < b[3]=999
更新b[3]=2
3--b[3]+[3][2]=2+6=8  < b[2]=9
更新[2]=8

4--b[2]+[2][4]=8+3=11  < b[4]=999
更新b[4]=11

5--b[2]+[2][5]=8+1=9  < b[5]=999
更新b[5]=9

6--b[3]+[3][4]=2+2=4  < b[4]=11
更新b[4]=4

7--b[3]+[3][6]=2+9=11  < b[6]=999
更新b[6]=11

8--b[4]+[4][6]=4+6=10  < b[6]=11
更新b[6]=10

9--b[5]+[5][7]=9+7=16  < b[7]=999
更新b[7]=16

10--b[6]+[6][7]=10+4=14  < b[7]=16
更新b[7]=14

一共进行了10次更新，下面是最终的结果

[1]=0
[2]=8
[3]=2
[4]=4
[5]=9
[6]=10
[7]=14

表示从结点1到其他结点的最短路径