Bellman-Ford 算法实现单源最短路径
/*从某一个点到任意一点的最短距离*/#include <iostream>#include<cstdio>#include<cstring>#define MAX 400003#define VALUE 999999using namespace std;struct edge{//定义边 int from; int to; int cost;};int v,es;int d[MAX];//某一点到任意一点的最短距离edge e[2*MAX];//建带权图void createGraph(){ int start,end,weight; scanf("%d%d",&es,&v); int i; for(i=0;i<es;i++) { //无向图，边数等于2*e scanf("%d%d%d",&start,&end,&weight); e[i].from=start; e[i].to=end; e[i].cost=weight; e[es+i].from=end; e[es+i].to=start; e[es+i].cost=weight; }}//Bellman-Ford算法只能处理正边权问题void BellmanFord(int s){int i; //初始化 for(i=1;i<=v;i++) { d[i]=VALUE;//s到各个点的最短距离为无穷大 } d[s]=0; while(true) { bool update=false; for(i=0;i<2*es;i++) { //一直更新到没有可以再更新的情况 edge ed=e[i]; //遍历每一条边，如果源点s到这条边起点是可达的，并且s到这条边的终点如果大于s到这条边起点加上这条边的权值，那么就更新最短路 if(d[ed.from]!=VALUE && d[ed.to]>d[ed.from]+ed.cost) {//如果有负边权，那么将进入死循环，距离将无限减小 d[ed.to]=d[ed.from]+ed.cost; update=true;//标记有更新过 } } //如果每一条边都访问过了并且都没有更新过，那么就跳出循环 if(update==false) break; } //输出 for(i=1;i<=v;i++) printf("%d\t",d[i]);}int main(){ createGraph(); BellmanFord(1); return 0;}