Dijikstra算法.
MilMcGrowdi
9年前
来自： http://my.oschina.net/u/2516597/blog/607688
#include <iostream> #include <priority_queue> #include <map> #include <stdexcept>
namespace{ static int MAXVALUE = 999; }template<typename T> struct Node{ T node_; int weighting_; using node_type = T; template<typename Ty> Node(const Ty& node, const int& weighting); //构造函数. template<typename Ty> Node(Node<Ty>&& otherNode); //移动构造函数. template<typename Ty> Node(const Node<Ty>& otherNode); //拷贝构造函数. template<typename Ty> friend bool operator<(const Node<Ty>& first_, const Node<Ty>& second); template<typename Ty> friend bool operator==(const Node<Ty>& first_, const Node<Ty>& second_); ~Node()=default; };template<typename T> template<typename Ty> Node<T>::Node(const Ty& node, const int& weighting) :node_(node), weighting_(weighting) { // }template<typename T> template<typename Ty> Node<T>::Node(Node<Ty>&& otherNode) :node_(otherNode.node_), weighting_(otherNode.weighting_) { // std::cout<<"move-constructor"<<std::endl; }template<typename T> template<typename Ty> Node<T>::Node(const Node<Ty>& otherNode) :node_(otherNode.onde_), weighting_(otherNode.weighting_) { // std::cout<<"copy for constructing"<<std::endl; }template<typename Ty> bool operator<(const Node<Ty>& first_, const Node<Ty>& second_) { return (first_.weighting_ < second_.weighting_) ? true : false; }template<typename Ty> bool operator==(const Node<Ty>& first_, const Node<Ty>& second_) { return (first_.node_ == second_.node_) ? true : false; }class Compare{ public: template<typename Ty> bool operator<(const Node<Ty>& first_, const Node<Ty>& second_); };template<typename Ty> bool Compare::operator<(const Node<Ty>& first_, const Node<Ty>& second_) { return first_ < second_; }template<typename T> class Graph{ //所有边的加权值必须为正. private: std::map<Node<T>, std::map<Node<T>, int> edges_; //存储无向图的各个边的加权值. std::map<Node<T>, std::vector<Node>> adjList_; //每个结点所相接的结点的邻接链表. std::priority<Node<T>, std::vector<T>, Compare> vertices_; //按照各个结点weighting_的大小来进行比较，作为除了给定源点外其他结点的集合. std::vector<Node<T>> verticeArray_; //存储从vertices_中找到最短路径的集合. template<typename Ty> void relax(const Node<Ty>& first_, const Node<Ty>& second_); //松弛操作. public: template<typename Ty, unsigned int N> Graph( const Ty (&edges)[N][3] ); //构造函数. template<typename Ty> void Dijstra(const Ty& node_data); //Dijstra算法. ~Graph(); };template<typename T> template<typename Ty, unsigned int N> Graph<T>::Graph( const Ty (&edges)[N][3] ) { if( N==0 ){ std::runtime_error("there is nothing in Graph.\n"); } for(int i=0; i<N; ++i){ Node<Ty> first_(edges[i][0], ::MAXVALUE); //这里之所以用::因为MAXVALUE位于匿名的namespace中. Node<Ty> second_(edges[i][1], ::MAXVALUE); //每个结点当前的加权值被设置为MAXVALUE. this->edges_[first_][second_] = edges[i][2]; //设置每条边相对应的加权值. this->adjList[first_].push_back(second_); //与first_相连的顶点被放在与其对应的std::vector中了. } std::cout<<"out of constructor."<<std::endl; }template<typename T> void Graph<T>::relax(const Node<Ty>& first_, const Node<Ty>& second_) { if(second_.weighting_ > first_.weighting_ + this->edges_[first_][second_]){ //second_为first_的前驱结点. second_.weighting = first_.weighting_ + this->edges_[first_][second_]; //如果前驱结点的weighting_大于当前结点(first_)的weighting_. //那么把前驱结点的weighting_设置为当前结点的weighting_和first_跟second_之间加权值的和. } }template<typename T> template<typename Ty> void Graph<T>::Dijstra(const Ty& node_data) { Node<Ty> source(node_data, 0); //设置源结点. 源结点的weighting_被设置为0. typename std::map<Node<Ty>, std::map<Node<T>, int>::const_iterator iter = this->edges_.begin(); //把所有的顶点存储到一个栈. this->verticeArray_.push_back(source); //把原点以及相距原点最短的结点都放入到verticeArray_中. for(; iter != this->edges_.end(); ++iter){ //把除了原点外的所有结点都放到vertices_中. if(source == iter->first){ continue; } this->vertices_.push(iter->first); } if( !this->vertices_.empty() ){ for(int i=0; i<this->vertices_.size(); ++i){ //逐个访问vertices_中的结点. Node<Ty> node = this->vertices_.top(); this->vertices_.pop(); this->verticeArray_.push_back(node); //把当前结点放到verticeArray_中. for(int j=0; j<this->adjList[node].size(); ++j){ //对于vertices_中各个结点相接的结点进行松弛操作. this->relax(node, adjList[node][j]); } } } }