最短パスアルゴリズム-Floyd

FloydアルゴリズムがDijkstraアルゴリズムと比較して最大の違いは、任意の点から任意の点までの最短経路を計算したことであり、アルゴリズムも理解しにくくなく、注意すべきは3層forサイクルの順序問題であり、kは最外層サイクルでなければならない.具体的なコードは以下の通りである.

#include <iostream>
#include <vector>
#include <limits>

void shortest_floyd(const std::vector <std::vector< short> >& graphic, std::vector <std::vector< short> >& paths){
    paths.clear();

    std:: vector<short> tmp;
    for(size_t i = 0; i != graphic.size(); ++ i){
        tmp.push_back( i);
    }

    for(size_t i = 0; i != graphic.size(); ++i){
        paths.push_back(tmp);
    }

    std:: vector<std::vector <short> > distance(graphic);

    std::cout << "    ：" << std::endl;
    for(size_t i = 0; i != distance.size(); ++i){
        for(size_t j = 0; j != distance[i].size(); ++j){
            std::cout << distance[i][j] << " " << std::flush;
        }
        std::cout << std:: endl;
    }


    for(size_t k = 0; k != graphic.size(); ++k){
        for(size_t i = 0; i != graphic.size(); ++i){
            for(size_t j = 0; j != graphic.size(); ++j){
                if(distance[i][k]+distance[k][j] < distance[i][j]){
                    distance[i][j] = distance[i][k]+distance[k][j];
                    paths[i][j] = paths[i][k];
                }
            }
        }
    }

    std::cout << "    ：" << std::endl;
    for(size_t i = 0; i != distance.size(); ++i){
        for(size_t j = 0; j != distance[i].size(); ++j){
            std::cout << distance[i][j] << " " << std::flush;
        }
        std::cout << std:: endl;
    }
}

int main(){
    std::cout << "      ：" << std::flush;
    int sum; std::cin >> sum;
    std:: vector<std::vector <short> > paths;
    for(int i = 0; i != sum; ++i){
        paths.push_back(std:: vector<short>(sum, std::numeric_limits< short>::max()));
        paths[i][i] = 0;
    }

    std::cout << "     ：" << std::flush;
    std::cin >> sum;

    int vi, vj, weight;
    for(int i = 0; i != sum; ++i){
        std::cin >> vi >> vj >> weight;
        paths[vi][vj] = weight;
        paths[vj][vi] = weight;
    }

    std:: vector<std::vector <short> > result;
    shortest_floyd(paths, result);

    std::cout << "      " << std::endl;
    for(size_t i = 0; i != result.size(); ++i){
        for(size_t j = 0; j != result[i].size(); ++j){
            std::cout << result[i][j] << " " << std::flush;
        }
        std::cout << std:: endl;
    }
    return 0;
}

このリンクは次のとおりです.http://blog.csdn.net/girlkoo/article/details/17525029
著者:girlkoo