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

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