Flody板子及其各类优化:Flody + 路径输出 ,Bellman-Ford,Bellman-Ford + 队列优化 + 前向星
程序员文章站
2022-05-12 15:02:11
...
void Flody()
{
for(int k=1; k<=n; k++)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
if(G[i][j]>G[i][k]+G[k][j])
{
G[i][j]=G[i][k]+G[k][j];
}
}
}
}
}
//Flody + 路径输出
//初始化,两点间无道路,e[i][j]初始化为正无穷
// 如果两点间有道路,记录每点的后驱 path[i][j] = j;
void flody()
{
For(k,1,N)
{
For(i,1,N)
{
For(j,1,N)
{
if(e[i][j] == e[i][k] + e[k][j])
{
if(path[i][j] > path[i][k])//找到字典序最小的路path[i][j] = path[i][k];
}
if(e[i][j] > e[i][k] + e[k][j])
{
e[i][j] = e[i][k] + e[k][j];
path[i][j] = path[i][k];
}
}
}
}
}
//Bellman-Ford
//存图
int tot;
struct Node
{
int u, v, w;
} e[4005];
void add(int u, int v, int w)
{
e[tot].u = u;
e[tot].v = v;
e[tot++].w = w;
}
int dis[1005];
int Bellman_Ford(int u, int En)
{
memset(dis,0x3f,sizeof(dis));
dis[u] = 0;
For(i,2,N)
{
int check = 1;
For(j,0,tot)//遍历所有边
{
if(dis[ e[j].v ] > dis[ e[j].u ] + e[j].w)
{
dis[ e[j].v ] = dis[ e[j].u ] + e[j].w;
check = 0;
}
}
if(check) break;
}
For(j,0,tot)//判断 有无负环
{
if(dis[ e[j].v ] > dis[ e[j].u ] + e[j].w) return -1;//存在负环
}
int main()
{
tot = 0;
while(M--) //路径数
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); //单向边
}
printf("%d\n",Bellman_Ford(1,N));
return 0;
}
//Bellman-Ford + 队列优化 + 前向星
//存图使用前向星
int dis[1005], cnt[1005];
bool book[1005];
int spfa(int u, int En)
{
memset(book,false,sizeof(book));
memset(cnt,0,sizeof(cnt));
memset(dis,0x3f,sizeof(dis));
book[u] = 1;
cnt[u] = 1;
dis[u] = 0;
queue<int> q;
q.push(u);
while(!q.empty())
{
u = q.front();
q.pop();
book[u] = 0;
for(int i = first[u]; ~i; i = e[i].next)
{
if(dis[ e[i].v ] > dis[u] + e[i].w)
{
dis[ e[i].v ] = dis[u] + e[i].w;
if(!book[ e[i].v ])
{
q.push(e[i].v);
book[e[i].v] = 1;
cnt[ e[i].v ]++;
if(cnt[ e[i].v ] > N) return -1; //存在负环
}
}
}
}
return dis[En];
}