Bellman-Ford算法 O(NE)
思路:枚举n-1次所有边,通过枚举所有边,将所有和已知点相连的点都设为已知,初始时起点为已知点。
for(int i=;i<=n-;i++){ //n-1是次数,枚举n-1次所有边肯定是够的
for(int j=;j<=E;j++){ //主要枚举的是边,而不是点
if(dis[u]+w[j]<dis[v){ //u,v分别是这条边连接的两个点
dis[v)=dis[u]+w[j];
pre[v]=u;
}
}
}
//思路:枚举n-1次所有边,通过枚举所有边,将所有和已知点相连的点都设为已知。