无环加权有向图最短路径(AcyclicShortPath) -- C++实现


这个算法是无环有向图的拓扑排序的简单扩展

只要将顶点的放松和拓扑排序结合起S马上就能得到一种解决无环加权有向图中的最短路径问题的算法

首先将distTs[s]初始化为0,其他distTo[]元素初始化为无穷大,然后一个一个地按照拓扑排序的顺序放松所有顶点即可

实现代码

// 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,I> m_edgeTo_TopSort;
		hash_map<I,bool> m_marked;
		hash_map<I,bool> m_OnStack;
		queue<I> m_cycle;
		bool m_isHasCycle;
		queue<I> preorder; // 所有顶点的前序排列
		deque<I> postorder; //所有顶点的后序排列


	public:

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

		int VertexCount();

		void AcyclicShortPath(I v);

		void Relax(DirectionEdges<I> e);

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

		void pathTo(I v) ;

		bool isContain(I v);

		// 拓扑排序
		void ClearQueue(queue<I>& q);
		bool hasLoop(I v);
		bool hasLoop();
		void ResetMarkTag(bool mark = false);
		void TopologicalSort();
		void DFS();
		void DeepFristSearch(I v);

		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>
	void EdgesWeightDirectionGraph<T,I>::DFS()
	{
		// 初始化相关操作
		m_edgeTo_TopSort.clear();
		ResetMarkTag();

		hash_map<I,list<DirectionEdges<I>>>::iterator it;
		for (it = m_mapList.begin();it!=m_mapList.end();it++)
		{
			if (!m_marked[it->first]) 
			{
				DeepFristSearch(it->first);
			}
		}
	}

	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::DeepFristSearch(I v)
	{
		m_marked[v] = true;
		list<DirectionEdges<I>>::iterator it;
		preorder.push(v); //前序 递归前入队列 获取顺序的时候得到的结果是 比邻接顶点顺序更前
		for (it = m_mapList[v].begin();it!=m_mapList[v].end();it++)
		{
			I tmp = it->To();
			if (!m_marked[tmp]) 
			{
				m_edgeTo_TopSort[tmp] = v;
				DeepFristSearch(tmp);
			}
		}

		postorder.push_front(v);//后序 在递归调用之后 获取顺序的时候得到的结果是比邻接顶点顺序更后
	}

	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::TopologicalSort()
	{
		DFS();
/*
		cout << "拓扑排序(逆后序)):";
		while(!postorder.empty())
		{
			I v = postorder.front();
			postorder.pop_front();
			cout << v << " ";
		}
		cout <<endl;
*/
		// 逆后序是后序的逆顺序

	}
	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::ClearQueue(queue<I>& q) 
	{
		queue<I> empty;
		swap(empty, q);
	}

	template<typename T,typename I>
	bool EdgesWeightDirectionGraph<T,I>::hasLoop()
	{
		ClearQueue(m_cycle);
		ResetMarkTag();
		m_isHasCycle = false;

		hash_map<I,list<DirectionEdges<I>>>::iterator it2;
		// 遍历所有顶点
		for (it2 = m_mapList.begin(); it2 != m_mapList.end(); it2++) 
		{

			I v = it2->first;

			if (!m_marked[v])
			{
				hasLoop(v);
				if (m_isHasCycle)
				{
					return m_isHasCycle;
				}
			}

			ResetMarkTag();
		}

		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>
	bool EdgesWeightDirectionGraph<T,I>::hasLoop(I v)
	{
		m_marked[v] = true;
		m_OnStack[v] = true; // 标记本次已遍历
		list<DirectionEdges<I>>::iterator it;
		for (it = m_mapList[v].begin();it!=m_mapList[v].end();it++)
		{
			I w = it->To();
			if (!m_OnStack[w]) 
			{
				hasLoop(w);
			}
			else // 
			{
				m_isHasCycle = true;
			}
		}

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

		return m_isHasCycle;
	}


	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>
	void EdgesWeightDirectionGraph<T,I>::AcyclicShortPath(I v)
	{
		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;

		// 
		while(!postorder.empty())
		{
			I v = postorder.front();
			postorder.pop_front();
			list<DirectionEdges<I>>::iterator it2 = m_mapList[v].begin();
			for (;it2!= m_mapList[v].end();it2++)
			{
				Relax(*it2);
			}
			
		}

	}

	template<typename T,typename I>
	void EdgesWeightDirectionGraph<T,I>::Relax(DirectionEdges<I> e)
	{
		I v = e.From();// 边e的起点(当前顶点)
		I w = e.To(); // 边e指向的顶点 (当前顶点指向的顶点)

		// 如果s到w的距离 大于 s到v的距离 + v到w距离 
		if (m_distTo[w] > m_distTo[v] + e.Weight())
		{
			// 更新distTo[w]为较小的值
			m_distTo[w] = m_distTo[v] + e.Weight(); 
			// 更新s到w最短路径的上一条边为当前的e
			m_edgeTo[w] = 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];
		// 起点m_edgeTo的边为空,对于 hash_map<I,DirectionEdges<I>> m_edgeTo; 来说,查找的时候,m_edgeTo[w]如果w不存在,将会返回一个
		// 默认构造的DirectionEdges<I>,此时 m_weight = DBL_MAX; 所以可以通过 e.Weight() != DBL_MAX; 来判断是否已到了起点
		// 或者检点一点的做法是保存起点,然后 e.From != 起点
		for (; e.Weight() != DBL_MAX; e = m_edgeTo[e.From()]) 
		 // for (; e.From() != m_s; 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 <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
#include "Component.h"
#include "EdgesWeightDirectionGraph.h"


using namespace jay;



int main(int argc, char* argv[])
{
	// 目前版本需要制定顶点的数量,有时间回头修改底层实现不需制定大小
	EdgesWeightDirectionGraph<double,string> gra(500);
	
//	gra.AddEdge("龙华","龙华",0.0); //Dijksra算法的顶点可以有自环
	gra.AddEdge("龙华","福田",0.2);
	gra.AddEdge("福田","宝安",0.3);
	gra.AddEdge("龙华","宝安",0.6);
	gra.AddEdge("福田","福永",0.1);
	gra.AddEdge("福永","龙岗",0.3);
	gra.AddEdge("宝安","罗湖",0.6);
	gra.AddEdge("罗湖","龙岗",0.3);
	gra.AddEdge("松岗","龙岗",0.3);

	gra.Show();
	if (gra.hasLoop())
	{
		cout << "图存在环,无法进行拓扑排序"<<endl;
		return 0;
	}

	gra.TopologicalSort();
	/*
	int iCount = 0;
	int p,q;
	double z;
	while(cin>>p)
	{
		cin>>q;
		cin>>z;
		gra.AddEdge(p,q,z);
	}
	*/
	

	gra.AcyclicShortPath("龙华");

 	gra.pathTo("宝安");

 	gra.pathTo("龙岗");

	gra.pathTo("沙井");

	gra.pathTo("松岗");

}

 

暂无评论

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