bellman-ford

旧城等待， 2022-07-11 01:56 57阅读 0赞

#include <iostream>
    #include <math.h>
    using namespace std;
    int s,edgenum,nodenum;
    const int max_edgenum=100;
    const int max_nodenum=100;
    struct Edge
    {
    	int u,v,cost;
    }edge[max_edgenum];
    int dis[max_nodenum];
    bool Bellman_ford()
    {
    	for(int i=1;i<=nodenum;i++)
    	{
    		dis[i]=(i==s?0:INF);
    	}
    	for(int i=1;i<=nodenum-1;i++)
    		for(int j=1;j<=edgenum;j++)
    		{
    			if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cost)
    				dis[edge[j].v]=dis[edge[j].u]+edge[j].cost;
    		}
    		for(int i=1;i<=edgenum;i++)
    		if(dis[edge[i].v]>dis[edge[i].u]+edge[i].cost)
    		{
    			flag=0;return false;
    		}
    		return true;
    }

#include<iostream>
    using namespace std;
    int P[100];
    int D[100];
    int W[100];
    int U[100];
    int V[100];
    int m,n;
    bool bellman_ford()
    {
    	for(int i=1;i<=n;i++)
    	{
    		D[i]=INF;
    	}
    
    	for(int i=1;i<=n-1;i++)
    	for(int j=1;j<=m;j++)
    	{
    		if(D[V[j]]>D[U[j]]+W[j])
    		{
    			D[V[j]]>D[U[j]]+W[j];
    			P[V[j]]=U[j];
    		}
    	}
    
    	for(int j=1;j<=n-1;j++)
    	{
    		if(D[V[j]]>D[U[j]]+W[j])
    			return false;
    	}
    	return true;
    }

INF这里还要学习，，，

**Ford算法解决单源最短路问题，以及双源最短路问题（因为复杂度相同）**

**从权值正负来分析，Ford算法可以解决带负权值的图的最短路问题。**

**若最短路存在，最短路径中一定不存在负环。即经过n-1条边。**

**算法思想是，进行n-1轮松弛，每轮松弛中更新所有边；n-1轮松弛后仍可更新边，说明含有负环。**

**附：百度百科上还有更简练的代码实现，每轮松弛操作后会判断是否收敛。**