加权有向图最短路径(BellmanFord算法) -- C++实现


该算法与Dijkstra算法的最大区别,其支持权重为负的边,只是不能存在负权环

另外本算法也是更通用的算法,因为没有指定放松边的顺序,而Dijkstra是使用了一个索引有限队列根据权值最小的边来处理

实现代码

// EdgesWeightDirectionGraph.h

#ifndef EdgesWeightDirectionGraph_H
#define EdgesWeightDirectionGraph_H

#include "Component.h"

#include "IndexPriorityQueueMin_T.h"

namespace jay{

	// T是索引优先队列的valu(这里是权重),I是索引优先队列的index(此处是顶点)
	template<typename T,typename I>
	class EdgesWeightDirectionGraph
	{
	private:

		hash_map<I,list<DirectionEdges<I>>> m_mapList; // 邻接表 存放了每个顶点的出边
		int m_V; // 顶点的数量
		int m_E; // 边的数量
		I m_s; // 当前起点

		set<I> m_ALLV;  // 图的所有顶点
		hash_map<I,T> m_distTo;          // 保存起点s到当前顶点v的最小权重(最短路径)

		hash_map<I,DirectionEdges<I>> m_edgeTo;    // 由起点s到当前顶点v的上一条边 
		IndexPriorityQueueMin_T<T,I> *m_pq; // 索引优先队列 索引是顶点 key是权重

		hash_map<I,int> m_indegree;// 入度

		hash_map<I,bool> m_onQueue;            // onQueue[v] = is v currently on the queue?
		queue<I> m_queue;          // queue of vertices to relax

		// 判断是否存在负权重环
		hash_map<I,bool> m_marked;             
		hash_map<I,bool> m_OnStack;           
		stack<DirectionEdges<I>> m_cycle;    // directed cycle (or null if no such cycle)
		bool m_isHasCycle;

	public:

		void AddEdge(I v,I w,T weight);
		void Show();

		void ResetMarkTag(bool mark = false);

		int VertexCount();

		void Dijkstra(I v);

		void Relax(I e);

		bool hasPathTo(I v) ;
		double distTo(I v);

		void pathTo(I v) ;

		bool isContain(I v);

		void BellmanFordShortestPath(I v);

		// 判断是否存在负权重环
		bool hasNegativeCycle();
		void DFS(I v);
		bool isNegative();
		stack<DirectionEdges<I>> GetCycle();
		void ClearStack(stack<DirectionEdges<I>>& q) ;
		// 

		EdgesWeightDirectionGraph(int iMaxNum);
		~EdgesWeightDirectionGraph();

	};

	template<typename T,typename I>
	EdgesWeightDirectionGraph<T,I>::EdgesWeightDirectionGraph(int iMaxNum)
	{
		m_V = 0;
		m_E = 0;
		m_pq = new IndexPriorityQueueMin_T<T,I>(iMaxNum);
	}

	template<typename T,typename I>
	EdgesWeightDirectionGraph<T,I>::~EdgesWeightDirectionGraph()
	{
		delete m_pq;
		m_pq = nullptr;
	}

	template<typename T,typename I>
	stack<DirectionEdges<I>> EdgesWeightDirectionGraph<T,I>::GetCycle()
	{
		return m_cycle;
	}

	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::BellmanFordShortestPath(I v)
	{
		// SPFA 算法
		if (hasNegativeCycle())
		{
			cout << "当前图存在负权重的环,无法使用BellmanFord求最短路径所有顶点与起点的路径,请处理负权重的环" << endl;
			return;
		}

		m_distTo.clear();
		m_edgeTo.clear();

		m_s = v;
		// 除起点外,其他顶点对应的distTo[v]设置为无限大
		set<I>::iterator it = m_ALLV.begin();
		for (; it != m_ALLV.end(); it++)
		{
			m_distTo[*it] = DBL_MAX;
		}
		m_distTo[v] = 0.0;

		m_queue.push(v);
		m_onQueue[v] = true; // 表明v在队列中
		while (!m_queue.empty()) 
		{
			I w = m_queue.front();
			m_queue.pop();
			m_onQueue[w] = false; // w已不再队列中
			Relax(w);
		}
	}

	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::Relax(I v)
	{
		list<DirectionEdges<I>>::iterator it2 = m_mapList[v].begin();
		for (;it2 != m_mapList[v].end();it2++)
		{
			I w = it2->To();
			if (m_distTo[w] > m_distTo[v] + it2->Weight()) 
			{
				m_distTo[w] = m_distTo[v] + it2->Weight();
				m_edgeTo[w] = *it2;
				if (!m_onQueue[w]) // 如果不在队列中 
				{
					m_queue.push(w);
					m_onQueue[w] = true;
				}
			}

			/*
			// java版本的代码是在这里检测负权重的环的,我在开始的时候检测
			// 这样处理效率会更高,避免扫描2次图,我暂时不做修改
			if (cost++ % G.V() == 0) {
				findNegativeCycle();
				if (hasNegativeCycle()) return;  // found a negative cycle
			}
			*/

		}
	}

	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::ClearStack(stack<DirectionEdges<I>>& q) 
	{
		stack<DirectionEdges<I>> empty;
		swap(empty, q);
	}


	template<typename T,typename I>
	bool EdgesWeightDirectionGraph<T,I>::hasNegativeCycle()
	{
		m_distTo.clear();
		m_edgeTo.clear();
		m_isHasCycle = false;
		ClearStack(m_cycle);
		ResetMarkTag();

		set<I>::iterator it = m_ALLV.begin();
		for (; it != m_ALLV.end(); it++)
		{
			if (!m_marked[*it])
			{
				DFS(*it);
			}

			if (m_isHasCycle)
			{
				return true;
			}
		}

		return false;
	}

	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::DFS(I v)
	{
		m_marked[v] = true;
		m_OnStack[v] = true; // 标记本次已遍历 类似AcyclicLongnestPath 有向图检测环的过程

		list<DirectionEdges<I>>::iterator it;
		for (it = m_mapList[v].begin();it!=m_mapList[v].end();it++)
		{
			I w = it->To();

			// 如果已经存在环不为空
			if (!m_cycle.empty())
			{
				return;
			}

			// 和普通有向图判断环的区别在这一段
			if (!m_marked[w]) 
			{
				m_edgeTo[w] = *it;
				DFS(w);
			}
			else if (m_OnStack[w])
			{
				// 本次遍历w顶点以被访问两次,说明存在环
				DirectionEdges<I> f = *it;
				while (f.From() != w) 
				{
					m_cycle.push(f);
					f = m_edgeTo[f.From()];
				}
				m_cycle.push(f);

				// 环的权重是否为负
				if(isNegative())
				{
					m_isHasCycle = true;
				}
			}
		}

		m_OnStack[v] = false; // 取消标记本次已遍历
	}

	template<typename T,typename I>
	bool EdgesWeightDirectionGraph<T,I>::isNegative()
	{
		// 判断是否是负环
		stack<DirectionEdges<I>> tmp = m_cycle;
		double allWeight = 0;
		while (!tmp.empty())
		{
			DirectionEdges<int> e = tmp.top();
			tmp.pop();

			I v = e.From(); 
			I w = e.To();

			allWeight += e.Weight();
		}

		if (allWeight < 0)
		{
			return true;
		}
		else
		{
			ClearStack(m_cycle);
			return false;
		}
	}

	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::ResetMarkTag(bool mark = false)
	{
		hash_map<I,bool>::iterator it;
		for (it = m_marked.begin();it!=m_marked.end();it++)
		{
			it->second = mark;
		}
	}

	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::AddEdge(I v,I w,T weight)
	{
		DirectionEdges<I> edges(v,w,weight);
		m_mapList[v].push_front(edges);

		m_ALLV.insert(v);
		m_ALLV.insert(w);
		m_indegree[w]++;
		m_E++;
	}

	template<typename T,typename I>
	bool EdgesWeightDirectionGraph<T,I>::hasPathTo(I v) 
	{
		return m_distTo[v] < DBL_MAX;
	}

	template<typename T,typename I>
	double EdgesWeightDirectionGraph<T,I>::distTo(I v) 
	{
		return m_distTo[v];
	}

	template<typename T,typename I>
	bool EdgesWeightDirectionGraph<T,I>::isContain(I v) 
	{
		return m_ALLV.find(v) != m_ALLV.end();
	}

	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::pathTo(I v) 
	{
		cout <<"---------------------" << endl;
		if (!isContain(v))
		{
			cout << "当前起点 " << v << " 未在图中" << endl;
			return ;
		}

		if (!hasPathTo(v)) 
		{
			cout << "当前起点 " << m_s << " 与顶点 "<< v <<" 不连通" << endl;
			return ;
		}

		cout << "当前起点 " << m_s << " 与顶点 "<< v <<" 最短路径为: " << endl;

		stack<DirectionEdges<I>> PathStack;
		DirectionEdges<I> e = m_edgeTo[v];

		for (; e.Weight() != DBL_MAX; e = m_edgeTo[e.From()]) 
		{
			PathStack.push(e);

		}

		while(!PathStack.empty())
		{
			DirectionEdges<I> e = PathStack.top();
			PathStack.pop();
			cout << e.From() << "->" << e.To() << "(" << e.Weight() << ")";
			cout <<endl;
		}
		cout << "总权重:" << m_distTo[v] <<endl;
	}


	template<typename T,typename I>
	int EdgesWeightDirectionGraph<T,I>::VertexCount()
	{
		return m_mapList.size();
	}

	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::Show()
	{
		hash_map<I,list<DirectionEdges<I>>>::iterator it;
		for(it = m_mapList.begin();it != m_mapList.end();it++)
		{
			I v1 = it->first;
			cout << "当前顶点 " << it->first << ": ";
			list<DirectionEdges<I>>::iterator it2;

			for (it2 = it->second.begin(); it2!=it->second.end();it2++)
			{
				cout << it2->To() << "(" << it2->Weight() << ") ";
			}

			cout << endl;
		}
	}
};

#endif

测试代码

//main.cpp

#include <time.h>
#include<windows.h>


#include "Component.h"
#include "EdgesWeightDirectionGraph.h"


using namespace jay;


int main(int argc, char* argv[])
{
	// 
	EdgesWeightDirectionGraph<double,int> gra(200);

	gra.AddEdge(5,1,0.5);
	gra.AddEdge(1,2,0.1);
	gra.AddEdge(2,3,0.2);
	gra.AddEdge(3,1,-0.2);
	gra.AddEdge(3,4,-0.3);
	gra.AddEdge(4,2,0.3);

	if (gra.hasNegativeCycle())
	{
		cout << "当前图存在负权重的环:" <<endl;
		stack<DirectionEdges<int>> tmp = gra.GetCycle();
		
		while (!tmp.empty())
		{
			DirectionEdges<int> e = tmp.top();
			tmp.pop();

			cout << e.From() << " -> " << e.To() <<endl;
		}

	}
	else
	{
		cout << "当前图不存在环"<<endl;

 		gra.BellmanFordShortestPath(5);
 
		gra.pathTo(2);
 		gra.pathTo(1);
 		gra.pathTo(4);
	}

}

 

暂无评论

注册用户登录后才能发表或者回复评论,请先登录 注册。