当前位置:  编程技术>c/c++/嵌入式

Dijkstra最短路径算法实现代码

    来源: 互联网  发布时间:2014-10-23

    本文导语:  Dijkstra的最短路径算法是基于前驱顶点的最短路径计算的,整体上来讲还是比较简单的,下面是代码: 代码如下:#include #include #include void shortestpath( const std::vector >& paths, int from, std::vector< short>& path){    std:: vector flags(paths.size...

Dijkstra的最短路径算法是基于前驱顶点的最短路径计算的,整体上来讲还是比较简单的,下面是代码:

代码如下:

#include
#include
#include

void shortestpath( const std::vector >& paths, int from, std::vector< short>& path){
    std:: vector flags(paths.size(), false);
    std:: vector 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::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 :: 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 > vj >> weight;
        paths[vi][vj] = weight;
        paths[vj][vi] = weight;
    }

    std:: vector path;
    shortestpath(paths, 0, path);

    std::cout


    
 
 

您可能感兴趣的文章:

  • 基于Java实现的Dijkstra算法示例
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3