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


要使用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;// 入度


	public:

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

		void ResetMarkTag(bool mark = false);

		int VertexCount();

		void Dijkstra(I v);

		void Relax(DirectionEdges<I> e);

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

		void pathTo(I v) ;

		bool isContain(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>::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>::Dijkstra(I v)
	{
		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;

		// key index
		m_pq->Insert(m_distTo[v],v);

		while (!m_pq->IsEmpty()) 
		{
			I w = m_pq->PopMin();
			list<DirectionEdges<I>>::iterator it2 = m_mapList[w].begin();
			for (;it2 != m_mapList[w].end();it2++)
			{
				//relax(e);
				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;         
			// 判断w顶点是否在最短路径中
			if (m_pq->isContain(w))
			{
				// w已在最短路径中,则更新m_distTo[w]为新的值
				m_pq->ChangeValue(m_distTo[w],w);
			}
			else
			{   
				// 如果w未在最短路径中,则将distTo[w]入索引优先队列,待后面处理
				m_pq->Insert(m_distTo[w],w);
			}
		}
	}

	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 <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.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);

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

	gra.Dijkstra("龙华");

 	gra.pathTo("宝安");

 	gra.pathTo("龙岗");

	gra.pathTo("沙井");

}

 

暂无评论

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