C++ 图进阶系列之纵横对比 Bellman-Ford 和 Dijkstra 最短路径求解算法

#include <iostream>
#include <map>
#include <climits>
#include <vector>
#include <queue>
using namespace std;
/*
* 结（顶）点类
*/
template<typename T>
struct Vertex {
	//顶点的编号
	int vId;
	//顶点所承载的值
	T value;
	//是否被访问过:False 没有 True:有
	bool visited;
	//与此顶点相连接的其它顶点
	map< Vertex<T>*,int > connectedTo;
	//前序顶点
	Vertex<T>* preorderVertex;
	// 权重（初始为无穷大）,为了研究方便，此处权重为 int  类型
	int weight = INT_MAX;
	//无参构造函数
	Vertex() {
		this->visited=false;
		this->vId=-1;
		this->preorderVertex=NULL;
	}
	//有参构造函数
	Vertex(int  id,T value) {
		this->vId=id;
		this->value=value;
		this->visited=false;
		this->preorderVertex=NULL;
	}

/*
*添加邻接顶点
*nbrVer:相邻顶点
*weight:无向无权重图，权重默认设置为 1
*/
void addNeighbor(Vertex<T>* nbrVer,int weight=1) {
    //map 中以相邻顶点为键，边权重为值
    this->connectedTo[nbrVer]=weight;
}

/*
*判断给定的顶点是不是当前顶点的相邻顶点
*/
bool isNeighbor( Vertex<T>* nbrVer) {
    //检查
    typename::std::map< Vertex<T>,int >::iterator iter= this->connectedTo.find(nbrVer) ;
    if( iter==this->connectedTo.end() )return false;
    return true;
}

/*
*显示当前顶点以及与之相邻的其它顶点
*/
void desc() {
    cout<<"顶点编号:"<<this->vId<<";顶点值:"<<this->value<<"顶点权重："<<this->weight<<endl;
    int count= this->connectedTo.size();
    cout<<"相邻顶点："<<count;
    typename::std::map< Vertex<T>*,int >::iterator begin= this->connectedTo.begin();
    typename::std::map< Vertex<T>*,int >::iterator end= this->connectedTo.end();
    while(begin!=end) {
        //（编号，值，边权重）
        cout<<"\t("<<begin->first->vId <<","<<begin->first->value<<","<<begin->second<<")"<<"\t";
        begin++;
    }
    cout<<endl;
}           

/*
*得到和某一个相邻顶点的权重
*/
int getWeight(Vertex<T>* nbrVer) {
    return this->connectedTo[nbrVer];
}

/*
*计算顶点权重（路径长度）
*/
bool  calBfWeight(Vertex<T>* nbrVer) {
    // 顶点权重加上顶点间边的权重
    int newWeight = this->weight + this->getWeight(nbrVer);

    if (newWeight < nbrVer->weight) {
        // 计算出来权重小于顶点原来权重，则更新
        nbrVer->weight=newWeight;
        // 更新前序顶点
        nbrVer->preorderVertex = this;
        return 1;
    }
    return 0;
}

//重载 < 运算符
bool operator<(const Vertex<T> & vert) const {
    return  this->vId<vert.vId;
}
//重载 == 运算符
bool operator==(const Vertex<T> & vert) const {
    return  this->vId==vert.vId;
}

template<typename T>
class Graph {
    private:
        // 一维列表，存储所有结点
        vector< Vertex<T>* > vertList;
        // 顶点个数
        int vNums = 0;
        // 队列，用于路径搜索算法
        queue<Vertex<T>* > pathQueue;
        //保存任意顶点之间的最短路径
        vector< vector< Vertex<T>* > > allPath;
    public:
    /*
	*无参构造函数
	*/
    Graph() {}
    //其它

/*
*按值查询顶点是否存在
*/
Vertex<T>* findVert(T  vertValue) {
    for(int i=0; i<this->vNums; i++) {
        if( this->vertList[i]->value==vertValue )
            return this->vertList[i];
    }
    return NULL;
}

/*
*查询所有顶点
*/
void findVertexes() {
    for(int i=0; i<this->vNums; i++) {
        this->vertList[i]->desc();
    }
}

/*
* 添加新顶点
*/
Vertex<T>* addVertex( T  vertValue) {
    //检查顶点是否存在
    Vertex<T>* vert=this->findVert(vertValue);
    if(vert!=NULL )return vert;
    // 顶点的编号内部生成
    vert=new Vertex<T>(this->vNums, vertValue);
    // 存储顶点
    this->vertList.push_back(vert);
    // 计数
    this->vNums++;
    return vert;
}

/*
* 添加顶点与顶点之间的关系（边），
* 如果是无权重图，统一设定为 1
*/
void addEdge(T fromValue,T toValue,int weight=1) {
    // from节点
    Vertex<T>* fromVert=this->addVertex(fromValue);
    //to 结点
    Vertex<T>* toVert=this->addVertex(toValue);
    //调用顶点自身的添加相邻顶点方法。
    fromVert->addNeighbor(toVert,weight);
}

/*
*贝尔曼-福特算法
*/
void bfNearestPath(Vertex<T> *from_v) {
    Vertex<T>* tmp_v;
    from_v->weight=0;
    // 记录边更新次数
    int update_count = 0;
    // 起始点压入队列
    this->pathQueue.push(from_v);
    // 检查队列是否为空
    while(!this->pathQueue.empty()) {
        //从队列获取顶点
        tmp_v = this->pathQueue.front();
        this->pathQueue.pop();
        // 标记为已经处理
        tmp_v->visited = true;
        // 得到与其相邻顶点
        map< Vertex<T>*,int > nbr_vs = tmp_v->connectedTo;
        
        typename::std::map< Vertex<T>*,int >::iterator begin=nbr_vs.begin();
        typename::std::map< Vertex<T>*,int >::iterator end=nbr_vs.end();

        // 更新与其相邻顶点的权重
        while(begin!=end) {
            Vertex<T>* v_=begin->first;
            // 更新权重，并记录更新次数
            update_count += tmp_v->calBfWeight(v_);
            // 无向边，要双向更新
            update_count +=v_->calBfWeight(tmp_v);
            // 把相邻顶点压入队列
            if (!v_->visited) {
                this->pathQueue.push(v_);
                v_->visited=true;
            }
            begin++;
        }
    }
    // 更新完毕后，如果更新次数为 0 ，则不用再更新。
    if (update_count != 0) {
        this->bfNearestPath(from_v);
    }
}

/*
*显示任意 2 个顶点之间的最短路径
*/
void getAllPath(T  value ) {
    //起始结点
    Vertex<T>*  startv= this->findVert(value);
    for(int i=0; i<this->vNums; i++ ) {
        Vertex<T>*  t_v = this->vertList[i];
        if(t_v==startv)continue;
        vector<Vertex<T>*  > path;
        path.push_back(t_v);
        while (1) {
            // 找到前序顶点
            Vertex<T>* pv= t_v->preorderVertex;
            path.push_back(pv);
            if(pv==startv) {
                this->allPath.push_back(path);
                break;
            }
            t_v=pv;
        }
    }
}

void showAllPath( T  value ) {
    cout<<"(----------f_v~t_v 最短路径长度------------)"<<endl;
    for(int i=0; i<this->allPath.size(); i++  ) {
        //起始结点
        Vertex<T>*  startv= this->findVert(value);
        //输出起始点
        cout<<startv->value<<"("<<startv->weight<<")"<<"->";
        int weight=0;
        for(int j=this->allPath[i].size()-1; j>=0; j-- ) {
            //
            Vertex<T>* tmp=this->allPath[i][j];
            //如果是起始点
            if(tmp==startv)continue;
            //得到相邻顶点的权重
            weight+=startv->getWeight(tmp);
            startv=tmp;
            cout<<startv->value<<"("<<startv->weight<<")"<<"->";
        }
        cout<<"最短路径的值"<<weight<<endl;
    }
}

int main(int argc, char** argv) {
	// 初始化图
	Graph<char> graph;
	// 添加节点
	char verts[]= {'A', 'B', 'C', 'D', 'E', 'F'};
	for(int i=0; i<sizeof(verts); i++ ) {
		graph.addVertex(verts[i]);
	}

	// 添加顶点之间关系
	char v_to_v[9][3] = { {'A', 'B', 3},  {'A', 'C', 5} , {'B', 'C', 1 } , { 'B', 'D', 2 } , {'B', 'E', 4} , { 'C', 'E', 6}, {'D', 'E', 7},
		{'D', 'F', 8},
		{'E', 'F', 3}
	};

	for(int i=0; i<9; i++) {
		graph.addEdge( v_to_v[i][0], v_to_v[i][1], v_to_v[i][2] );
		graph.addEdge( v_to_v[i][1], v_to_v[i][0], v_to_v[i][2] );
	}
    //显示图中的所有顶点以及顶点之间的关系
	graph.findVertexes();
	return 0;
}

int main(int argc, char** argv) {
	//省略……
	//查找任一顶点到 'A' 顶点之间的最短路径长度
	Vertex<char>* fromV=   graph.findVert('A');
    //BF 算法
	graph.bfNearestPath(fromV);
	cout<<"---------BF后顶点的权重----------"<<endl;
	graph.findVertexes();
	graph.getAllPath('A');
	graph.showAllPath('A');
	return 0;
}

//省略其它……
//为优先队列提供比较函数对象
struct comp {
	bool operator() (Vertex<T>* v1, Vertex<T>* v2) {
		//由小到大排列
		return v1->weight < v2->weight;
	}
};
template<typename T>
class Graph {
	private:
    	//省略其它……
    	//优先队列容器
		priority_queue<Vertex<T>* ,vector<Vertex<T>*>,comp<T> > priorityQueue;
    	//记录 Dj 算法已经更新顶点。 DJ 算法不需要对已经过求过权重的 2 个顶点重复计算
		vector< vector< Vertex<T>* > > isUpdate;
         //省略其它

template<typename T>
class Graph {
    private:
    	//省略……
    public:
         //省略其它……
         /*
		*检查是否更新过
		*/
		bool isUpdated(Vertex<T>* v1,Vertex<T> * v2) {
			bool is=false;
			for(int i=0; i<this->isUpdate.size(); i++) {
				vector<Vertex<T>*> vec=this->isUpdate[i];
				if(v1==vec[0] && v2==vec[1] ||  v2==vec[0] && v1==vec[1] )is=true;
			}
			return is;
		}
		/*
		* Dijkstra（迪杰斯特拉）算法
		*/
		void djNearestPath(Vertex<T> * from_v) {
			// 记录边更新次数
			int update_count = 0;
			Vertex<T>* tmp_v;
			//设备起始点的权重为 0
			from_v->weight=0;
			// 起始点压入队列
			this->priorityQueue.push(from_v);
			//标记已经入队列
			from_v->visited = true;
			// 检查队列是否为空
			while ( !this->priorityQueue.empty() ) {
				// 从队列获取顶点
				tmp_v = this->priorityQueue.top();
				this->priorityQueue.pop();
				// 得到与其相邻所有顶点
				map< Vertex<T>*,int > nbr_vs = tmp_v->connectedTo;
				typename::std::map< Vertex<T>*,int >::iterator begin=nbr_vs.begin();
				typename::std::map< Vertex<T>*,int >::iterator end=nbr_vs.end();
				while(begin!=end) {
					Vertex<T>* v_=begin->first;
					// 顶点间的权重是否更新过
					if( this->isUpdated(tmp_v,v_))continue;
					// 更新权重
					tmp_v->calBfWeight(v_);
					//记录更新信息
					vector<Vertex<T>* > update= {tmp_v,v_ };
					// 把相邻顶点压入队列
					if( v_->visited==false ) {
						this->priorityQueue.push(v_);
						v_->visited=true;
					}
					begin++;
				}
			}
		}
    //省略其它……
};

int main(int argc, char** argv) {
	// 省略……
	Vertex<char>* fromV=   graph.findVert('A'); 
	cout<<"Dijkstra 算法:"<<endl; 
	graph.djNearestPath(fromV);
	cout<<"-------------------"<<endl;
	graph.findVertexes();
	graph.getAllPath('A');
	graph.showAllPath('A');
	return 0;
}