C语言最短路径和矩阵乘法.

2019PHP高薪工程师学习路线图....>>>

 #include <iostream>
#include <stdexcept>
#include <vector>
#include <algorithm>
#include <memory>
#include <map>
namespace{
 enum:int{
  MAXVALUE = 9999
 };
}
template<typename T>
class Node{
 private:
 T key_;
 
 public:
 
 template<typename Ty>
 Node(const Ty& key);
 
 template<typename Ty>
 Node(const Node<Ty>& otherNode_);
 
 template<typename Ty>
 Node(Node<Ty>&& otherNode_);
 
 Node() = default;
 
 ~Node();
 
 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_);
 
 const Node<T>& operator=(const Node<T>& otherNode_);//必须这么写 不然编译器还会合成. 
 
 template<typename Ty>
 friend std::ostream& operator<<(std::ostream& os, const Node<Ty>& node_);
 
 template<typename Ty>
 void operator=(Node<Ty>&& otherNode_);
 
};
template<typename T>
template<typename Ty>
Node<T>::Node(const Ty& key)
        :key_(key)
{
 //std::cout<<"constructor function."<<std::endl;
}
template<typename T>
template<typename Ty>
Node<T>::Node(const Node<Ty>& otherNode_)
        :key_(otherNode_.key_)
{
 std::cout<<"copy for constructor"<<std::endl;
}
template<typename T>
Node<T>::~Node()
{
 //
}
template<typename Ty>
bool operator==(const Node<Ty>& first_, const Node<Ty>& second_)
{
 return (first_.key_ == second_.key_) ? true : false;
}
template<typename T>
const Node<T>& Node<T>::operator=(const Node<T>& otherNode_) //必须这么写不然编译器自己合成. 
{
 this->key_ = otherNode_.key_;
 std::cout<<"copy function"<<std::endl;
}
template<typename Ty>
bool operator<(const Node<Ty>& first_, const Node<Ty>& second_)
{
 std::cout<<"<"<<std::endl;
 return (first_.key_ < second_.key_) ? true : false;
}
template<typename Ty>
std::ostream& operator<<(std::ostream& os, const Node<Ty>& node_)
{
 os<<node_.key_<<std::endl;
 return os;
}
template<typename T>
template<typename Ty>
void Node<T>::operator=(Node<Ty>&& otherNode_)
{
 std::cout<<"operator move"<<std::endl;
 this->key_ = otherNode_.key_;
}
template<typename T>
class Map{
 private:
  
  class Compare{
   public:
    template<typename Ty>
    bool operator()(const Node<Ty>& first_, const Node<Ty>& second_);
  };
  
  //template<typename Ty>
  //typedef Graph std::map<Node<Ty>, std::map<Node<Ty>, int>>; //不能用typedef只能用using. 
  
  class Container{
   public:
    template<typename Ty>
    bool operator()(typename Map<Ty>::cv_iter currentIter_, std::shared_ptr<Node<Ty>> currentNode_);
  }; 
  
  std::map<Node<T>, std::map<Node<T>, int>> graph_; //该边的加权值可以为负 
  std::map<Node<T>, std::vector<Node<T>>> adjList_;
  std::map<Node<T>, std::map<Node<T>, int>> temp_graph_;
  
  unsigned int nodeNumber_;
  
  template<typename Ty>
  typename Map<Ty>::Graph extend_shortest_paths(std::shared_ptr< typename Map<Ty>::Graph > g);
  
  const int& min(const int& first_, const int& second_);
  
  public:
      template<typename Ty>
      using Graph = std::map<Node<Ty>, std::map<Node<Ty>, int>>;//类型别名.
      
      template<typename Ty>
      using v_iter = typename std::vector<Node<Ty>>::const_iterator;//类型别名.
   
   template<typename Ty>
   using  cv_iter = typename std::map<Node<Ty>, std::vector<Node<Ty>>>::const_iterator;
      
      template<typename Ty>
      using cmm_iter = typename std::map<Node<Ty>, std::map<Node<Ty>, int>>::const_iterator;//类型别名. 
      
   template<typename Ty, unsigned int N>
   Map(const Ty (&edge)[N][3]);
   
   ~Map();
   Map()=default;
   
   void slow_all_pairs_shortest_paths();
  
};
template<typename T>
template<typename Ty, unsigned int N>
Map<T>::Map(const Ty (&edges)[N][3])
       :nodeNumber_(N)
{
 if(N == 0){
  throw std::runtime_error(std::string("there is nothing in graph"));
 }
 
 for(int i =0; i<N; ++i){ //存储无向图中的数据以及两个相连接结点之前的加权值。 
  Node<Ty> first_(edges[i][0]);
  Node<Ty> second_(edges[i][2]);
  
  this->graph_[first_][second_] = edges[i][1];
  this->temp_graph_[first_][second_] = ::MAXVALUE;
  
  this->adjList_[first_].push_back(second_); //邻接链表:跟结点A相连接的所有结点都被放在一个vector中. 
 }
}
template<typename T>
template<typename Ty>
typename Map<Ty>::Graph Map<T>::extend_shortest_paths(std::shared_ptr< typename Map<Ty>::Graph > g)
{
 
 typename Map<Ty>::Container jundge_;
 typename Map<Ty>::cv_iter first_ = this->adjList_.cbegin();
 typename Map<Ty>::v_iter second_ = this->adjList_[first_->first].cbegin();
 
 typename Map<Ty>::Graph temp_graph_;
 
 for(; first_ != this->adjList_.cend(); ++first_){
  
  for(; second_ != this->adjList_[first_->first].cend(); ++second_){
   temp_graph_[first_->first][*second_] = ::MAXVALUE;
   
   typename Map<Ty>::v_iter third_ = this->adjList_[first_->first].cbegin();
   
   for(; third_ != this->adjList_[first_->first].cend(); ++third_){
    
    bool boolean = jundge(third_, std::make_shared<Node<Ty>> (*second_));
    
    if(boolean == false){
     continue;
    }
    
    temp_graph_[first_][second_] = this->min(temp_graph_[first_][second_], (*g)[first_][third_]+this->graph_[third_][second_]);
   }
  }
 }
 
 return (*g);
}
template<typename T>
void Map<T>::slow_all_pairs_shortest_paths()
{
 Map<T>::Graph<T> L(this->graph_);
 for(int i=1; i<this->nodeNumber_; ++i){
  
  L = this->extended_shortest_paths(std::make_shared< Map<T>::Graph<T> > (this->graph_));
 }
 
}
template<typename T>
template<typename Ty>
bool Map<T>::Compare::operator()(const Node<Ty>& first_, const Node<Ty>& second_)
{
 return first_ < second_ ? true : false;
}
template<typename T>
const int& Map<T>::min(const int& first_, const int& second_)
{
 return (first_ < second_) ? first_ : second_;
}
template<typename T>
template<typename Ty>
bool Map<T>::Container::operator()(typename Map<Ty>::cv_iter currentIter_, std::shared_ptr<Node<Ty>> currentNode_)
{
 if(Map<Ty>::adjList_[*currentNode_].empty()){
  return false;
  
 }else{
  
  typename Map<Ty>::v_iter first_ = Map<Ty>::adjList_[*currentNode_].cbegin();
  typename Map<Ty>::v_iter second_ = Map<Ty>::adjList_[*currentNode_].cend();
  typename Map<Ty>::v_iter third_;
  
  third_=std::find_if(first_, second_, [currentNode_](const Node<Ty>& temp_)->bool { return (temp_ == *currentNode_) ? true : false; });
  
  if(third_ == second_){
   return false;
   
  }else{
   
   return true;
  }
 }
}
int main()
{
 Node<int> one_(20);
 Node<int> two_(30);
 
 Node<int> three_;
 
 three_ = one_;
 
 one_ = two_;
 std::cout<<one_;
 
 three_ = std::move(one_);
 std::cout<<std::boolalpha<< (one_<two_ )<<std::endl;
 
 
 return 0;
}