floyd_warshall 算法.

 #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; 
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。