算法实验四：寻找加权有向图中的一个负环

电玩女神 2022-01-28 15:37 177阅读 0赞

题目描述：

给定一个有向图，图中边的权重有正有负，设图中存在若干负环，设计算法找到一个负环。

思路描述：

**利用bellman\_ford的方法先判断有没有环，如果有环，保存这条能relax的边，然后通过他的前驱点往前遍历，并将这些边保存到一个数组里，在过程中先判断是否出现了此点，如果出现说明找到环，这个点以及后面的点都是这个环中的点，否则继续加入数组中。**

算法实现：

bool linkedDgraph1::BellmanFord(int s,int *res)//起始点，保存环中的点的数组
    {
    	int * d = new int[verticeNumber];
    	int k1 = 0,k2=0,count=1;
    	bool exist = false;
    	for (int i = 0; i < verticeNumber+1; i++)//初始化表示
    		d[i] = 1000000;
    	for (int i = 1; i < verticeNumber; i++)
    	{
    
    		for (int j = 0; j < verticeNumber; j++)
    		{
    			int u = point[j];
    			graphNode<int>* p = Adj[u].first();
    			
    			while (p != NULL)
    			{
    				int v = p->element;
    				if (d[v] > d[u] + getWeight(u, v))//relax操作
    				{
    					d[v] = d[u] + getWeight(u, v);
    					precursor[v] = u;
    				}
    				p = p->next;
    			}
    		}
    	}
    	//再扫描判断是否有负圈
    	for (int j = 0; j < verticeNumber; j++)
    	{
    		int u = point[j];
    		graphNode<int>* p = Adj[u].first();
    		while (p != NULL)
    		{
    			int v = p->element;
    			if (d[v] > d[u] + getWeight(u, v))//relax操作
    			{
    				k1 = v;
    				k2 = u;
    				exist = true; 
    				break;
    			}
    			p = p->next;
    		}
    		if (exist)
    			break;
    	}
    	vector<int> a;
    	//保证要找的点在负环上
    	/*k1 = k2;
    	k2 = precursor[k1];
    	while (precursor[k2] != k1)
    	{
    		res[count] = k2;
    		k2 = precursor[k2];
    		count++;
    	}
    	res[count++] = k1;
    	res[count] = k2;
    	res[0] = count;*/
    	a.push_back(k1);
    	a.push_back(k2);
    	while (true)//每次判断是否已经存在数组中
    	{
    		k2 = precursor[k2];
    		int index = -1;
    		for (int i = 0; i < a.size(); i++)
    			{
    				if (a[i] == k2)//判断是否找到环
    				{
    					index = i;
    				}
    			}
    		if (index != -1)//找到环
    		{
    			for (int j = index; j < a.size(); j++)
    			{
    				res[count++] = a[j];
    			}
    			break;
    		}
    		else
    			a.push_back(k2);
    	}
    	res[0] = count-1;
    	
    	return exist;
    }