思路及证明见 算法导论 单源最短路径
图的存储使用 邻接矩阵
搜索得到最短路径树的每个节点用结构体存储 保存 父节点 和 距离父节点的距离
算法 对每个节点松弛 V-1 次之后准备使用 邻接链表存储 边的信息 这样比较快
代码还是比较简单的 应该可以看明白
#define M 100
#define INF 99999typedef struct {int d;int p;
}NODE;typedef struct {int v1,v2; // v1->v2;int edge;
};void init_vertex(NODE v[],int n){for(int i=1;i<=n;i++){v[i].p = NULL;v[i].d = INF;}v[1].d=0;
}void relax(NODE v[],int v1,int v2,int w){if(v[v2].d>v[v1].d+w){v[v2].d=v[v1].d+w;v[v2].p=v1;}
}int bellman_ford(int g[M][M],NODE v[],int n){//initializeinit_vertex(v,n);//relax every vertexfor(int i=1;i<n;i++){//serach every edgefor(int x=1;x<=n;x++){for(int y=1;y<=n;y++){//the edge is not INFif(g[x][y]!=INF){relax(v,x,y,g[x][y]);}}}}// judge the resultfor(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(v[j].d>v[i].d+g[i][j]){return 0;}}}return 1;
}int main() {//use ju zheng save graphint graph[M][M];NODE vertex[M];int n,e; // n the number of vertex m the number of edgescanf("%d %d",&n,&e);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){graph[i][j] = INF;}}int v1,v2,dis;for(int i=1;i<=e;i++){scanf("%d %d %d",&v1,&v2,&dis);graph[v1][v2] = dis;}bellman_ford(graph,vertex,n);return 0;
}
/* 5 10 1 2 6 1 3 7 2 3 8 2 4 5 4 2 -2 2 5 -4 3 5 9 3 4 -3 5 0 2 5 4 7* */