floyd_warshall 算法.

usib8630的头像 usib8630 0 2016-03-05 20:22 0

 基本信息

× 1    浏览数: 26711 分享时间: 2 年 前
 #include <iostream> #include <map> #include <memory> #include <new> #include <stdexcept> namespace{  enum : int{   MAXVALUE = 9999  }; } template<typename T> class Graph{  private:   std::map<T, std::map<T, int>> graph_;   std::map<T, std::map<T, T>> path_;   std::map<T, std::map<T, int>> distance_;      unsigned int node_number_;      void floyd_warshall()noexcept;      public:    using map_type = std::map<T, std::map<T, int>>;        using map_iter = typename std::map<T, std::map<T, int>>::const_iterator;        using iter = typename std::map<T, int>::const_iterator;        template<typename Ty, unsigned int N>    Graph(const Ty (&edges)[N][3]);        ~Graph();        template<typename Ty>    void print(const Ty& start, const Ty& end); }; template<typename T> template<typename Ty, unsigned int N> Graph<T>::Graph(const Ty (&edges)[N][3])          :node_number_(N) {  if(N == 0){   throw std::runtime_error(std::string("there is nothing"));  }    /*for(int i=0; i<N; ++i){   for(int j=0; j<N; ++j){    (this->*graph_)[i][j] = (i == j) ? 0 : ::MAXVALUE; //如果该点的距离为从自身到自身那么距离为0.    }  }*/    for(int j =0; j<N; ++j){   (this->graph_)[edges[j][0]][edges[j][1]] = edges[j][2];  }    map_iter first_ = (this->graph_).cbegin();  for(; first_ != (this->graph_).cend(); ++first_){      map_iter second_ = (this->graph_).cbegin();   for(; second_ != (this->graph_).cend(); ++second_){        if(first_->first == second_->first){     (this->graph_)[first_->first][second_->first] = 0;         }else if((this->graph_)[first_->first][second_->first] > 0){     continue;         }else{     (this->graph_)[first_->first][second_->first] = ::MAXVALUE;    }   }  }    std::cout<<"successful constructor\n";    /*map_iter iter_first = this->graph_.cbegin();  for(; iter_first != this->graph_.cend(); ++iter_first){      std::cout<<iter_first->first<<":  ";   iter iter_second = this->graph_[iter_first->first].cbegin();   for(; iter_second != this->graph_[iter_first->first].cend(); ++iter_second){        std::cout<<iter_second->first<<"--"<<iter_second->second<<"  ";   }      std::cout<<std::endl;  }*/ } template<typename T> void Graph<T>::floyd_warshall()noexcept {  if(this->node_number_ == 0){   throw std::runtime_error(std::string("there nothing in graph"));  }    //注意下面的双重循环:  //first_, second_, 以first_为起点second_为终点不断的查找这两个结点间的距离.   map_iter first_ = (this->graph_).cbegin();  for(; first_ != (this->graph_).cend(); ++first_){      iter second_ = (this->graph_)[first_->first].cbegin();   for(; second_ != (this->graph_)[first_->first].cend(); ++second_){        this->distance_[first_->first][second_->first] = (this->graph_)[first_->first][second_->first];    this->path_[first_->first][second_->first] = 0;   }  }    /*map_iter x = this->distance_.cbegin();  for(; x != this->distance_.cend(); ++x){      std::cout<<x->first<<":  ";   iter y = (this->distance_)[x->first].cbegin();   for(; y != (this->distance_)[x->first].cend(); ++y){        std::cout<<y->first<<"--"<<x->first<<"  ";   }   std::cout<<std::endl;  }*/    map_iter third_ = (this->graph_).cbegin();  map_iter forth_ = (this->graph_).cbegin();  map_iter fifth_ = (this->graph_).begin();    for(; third_ != (this->graph_).cend(); ++third_){      for(; forth_ != (this->graph_).cend(); ++forth_){        for(; fifth_ != (this->graph_).cend(); ++fifth_){          if((this->distance_)[forth_->first][third_->first] != ::MAXVALUE && (this->distance_)[third_->first][fifth_->first] != ::MAXVALUE && (this->distance_)[forth_->first][third_->first]+(this->distance_)[third_->first][fifth_->first]<(this->distance_)[forth_->first][fifth_->first]){      (this->distance_)[forth_->first][fifth_->first] = this->distance_[forth_->first][third_->first] + this->distance_[fifth_->first][third_->first];      (this->path_)[forth_->first][fifth_->first] = third_->first;     }    }   }  } } template<typename T> template<typename Ty> void Graph<T>::print(const Ty& start, const Ty& end) {  this->floyd_warshall(); } template<typename T> Graph<T>::~Graph() {  if(!this->graph_.empty()){   this->graph_.clear();  }    if(!this->path_.empty()){   this->path_.clear();  }    if(!this->distance_.empty()){   this->distance_.clear();  } } int main() {  int edges[15][3]={  {1, 2, 2},  {1, 4, 20},  {2, 5, 1},  {3, 1, 3},  {4, 3, 8},  {4, 6, 6},  {4, 7, 4},  {5, 3, 4},  {5, 8, 3},  {6, 3, 1},  {7, 8, 1},  {8, 6, 2},  {8, 10, 2},  {9, 7, 2},  {10, 9, 1}  };    Graph<int> my_graph(edges);    my_graph.print(2, 4);    return 0;  }
还没有人评论,赶快来抢沙发吧!