当前位置: 代码迷 >> 综合 >> 最短路 bellman模板
  详细解决方案

最短路 bellman模板

热度:22   发布时间:2024-01-14 22:28:25.0
int u[MAX,v[MAX],w[MAX];
int dist[MAX];
int n,m;
void bellman(int vs)
{int i,j,k;for(i=1;i<=n;i++)dist[i] = inf;dist[vs] = 0;for(k=1;k<=n-1;k++)//最多需要松弛n-1次{int f = 0;for(i=1;i<=m;i++){if(dist[v[i]] > dist[u[i]] + w[i]){dist[v[i]] = dist[u[i]] +w[i];f = 1;}}if(f) break;}f = 0;for(i=1;i<=m;i++) //如果还可以松弛{if(dis[v[i]] > dist[u[i]] +w[i])f = 1;}if(f) printf("-1\n"); //存在负环else printf("%d\n",dist[n]);
}