来自： 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]);      }     }    }     }