Dijikstra算法.

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