# floyd_warshall 算法.

usib8630 0 2016-03-05 20:22 0

### 基本信息

× 1

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