国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 編程 > C > 正文

Dijkstra最短路徑算法實現代碼

2020-01-26 15:39:15
字體:
來源:轉載
供稿:網友

Dijkstra的最短路徑算法是基于前驅頂點的最短路徑計算的,整體上來講還是比較簡單的,下面是代碼:

復制代碼 代碼如下:

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

void shortestpath( const std::vector <std::vector< short> >& paths, int from, std::vector< short>& path){
    std:: vector<bool> flags(paths.size(), false);
    std:: vector<short> distance(paths.size(), 0);
    path.resize(paths.size(), 0);

    for(size_t i = 0; i != paths.size(); ++i){
        distance[i] = paths[from][i];
    }

    flags[from] = 1;

    int min, pos;
    for(size_t i = 1; i != paths.size(); ++i){
        pos = -1;
        min = std:: numeric_limits<short>::max();
        for(size_t j = 0; j != paths.size(); ++j){
            if(!flags[j] && distance[j] < min){
                min = distance[j];
                pos = j;
            }
        }

        if(pos == -1)
            break;

        flags[pos] = true;

        for(size_t j = 0; j != paths.size(); ++j){
            if(!flags[j] && paths[pos][j] != 0
                && paths[pos][j] < std::numeric_limits <int>:: max()
                && min+paths[pos][j] < distance[j]){
                distance[j] = min + paths[pos][j];
                path[j] = pos;
            }
        }
    }

    for(size_t i = 0; i != distance.size(); ++i){
        std::cout << distance[i] << " " << 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<short> path;
    shortestpath(paths, 0, path);

    std::cout << "最近路徑結果為:" << std::flush;
    for(size_t i = 0; i != path.size(); ++i){
        std::cout << path[i] << " " << std::flush;
    }
    std::cout << std:: endl;

    return 0;
}

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表

圖片精選

主站蜘蛛池模板: 延川县| 页游| 淳化县| 四川省| 新乡市| 当阳市| 忻州市| 叙永县| 杭锦后旗| 肃北| 定安县| 甘洛县| 揭西县| 岗巴县| 天津市| 迁安市| 二手房| 余姚市| 东光县| 包头市| 泽州县| 延津县| 耿马| 阜阳市| 永善县| 绥滨县| 永胜县| 图片| 平乡县| 泰来县| 灵山县| 隆子县| 巴中市| 岢岚县| 柳林县| 大名县| 安远县| 祥云县| 棋牌| 建德市| 刚察县|