Bellman-Ford算法
2010年7月21日 04:12
#include<iostream> using namespace std; const int V=101; const int E=101; #define typec int // type of cost const typec inf=0x3f3f3f3f; // max of cost int n, m, pre[V], edge[E][3]; typec dist[V]; int relax (int u, int v, typec c) { if (dist[v] > dist[u] + c) { dist[v] = dist[u] + c; pre[v] = u; return 1; } return 0; } int bellman (int src) { int i, j; for (i=0; i<n; ++i) { dist[i] = inf; pre[i] = -1; } dist[src] = 0; bool flag; for (i=1; i<n; ++i) { flag = false; for (j=0; j<m; ++j) { if( 1 == relax(edge[j][0], edge[j][1], edge[j][2]) ) flag = true; } if( !flag ) break; } for (j=0; j<m; ++j) { if (1 == relax(edge[j][0], edge[j][1], edge[j][2])) return 0 } return 1; } int main() { int i; int src; cin>>n>>m; for(i=0; i<m; ++i) { cin>>edge[i][0]>>edge[i][1]>>edge[i][2]; } cin>>src; cout<<bellman(src)<<"\n"; for(i=0; i<n; i++) { cout<<dist[i]<<' '; } cout<<'\n'; return 0; }
模版的使用,Bellman-Ford算法,复杂度O(VE),可解决负权边,判别负权回路。
额外采用Yen氏改进,但不降低渐进复杂度。还可采用队列优化成SPFA(Shortest Path Faster Algorithm)。