Dijkstra最短路径算法实现代码_C 语言

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

时间: 2016-12-25

Dijkstra最短路径算法实现代码_C 语言的相关文章

c++实现MD5算法实现代码_C 语言

测试结果和百度百科测试例子一致. 实现过程中需要注意事项:最后把四个变量A B C D 链接成结果时 ,注意变量高低位的先后顺序,具体参考 LinkResult()方法. md5.h 复制代码 代码如下: #ifndef _MD5_H_#define _MD5_H_ #include <iostream>#include <string>using namespace std; class MD5{    public:        typedef unsigned char u

哈夫曼算法构造代码_C 语言

1.定义 哈夫曼编码主要用于数据压缩. 哈夫曼编码是一种可变长编码.该编码将出现频率高的字符,使用短编码:将出现频率低的字符,使用长编码. 变长编码的主要问题是,必须实现非前缀编码,即在一个字符集中,任何一个字符的编码都不是另一个字符编码的前缀.如:0.10就是非前缀编码,而0.01不是非前缀编码. 2.哈夫曼树的构造 按照字符出现的频率,总是选择当前具有较小频率的两个节点,组合为一个新的节点,循环此过程知道只剩下一个节点为止. 对于5个字符A.B.C.D.E,频率分别用1.5.7.9.6表示,

C语言对堆排序一个算法思路和实现代码_C 语言

算法思想简单描述: 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称之为堆.在这里只讨论满足前者条件的堆. 由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项.完全二叉树可以很直观地表示堆的结构.堆顶为根,其它为左子树.右子树. 初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的

C语言 奇偶排序算法详解及实例代码_C 语言

C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序.该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 使用奇偶排序法对一列随机数字进行排序的过程 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可同时与邻居进行比较.交

C语言二分查找算法及实现代码_C 语言

二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列.该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置为基准将所要査找的序列分为左右两部分.接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要査找元素可能存在的那部分序列,对其采用同样的方法进行査找,直至能够确定所要查找的元素是否存在,具体的使用方法可通过下面的代码具体了解. #include <stdio.h> binar

马尔可夫链算法(markov算法)的awk、C++、C语言实现代码_C 语言

1. 问题描述 马尔可夫链算法用于生成一段随机的英文,其思想非常简单.首先读入数据,然后将读入的数据分成前缀和后缀两部分,通过前缀来随机获取后缀,籍此产生一段可读的随机英文. 为了说明方便,假设我们有如下一段话:   复制代码 代码如下:    Show your flowcharts and conceal your tables and I will be mystified. Show your tables and your flowcharts will be obvious.   假

C语言冒泡排序算实现代码_C 语言

冒泡排序是排序算法的一种,思路清晰,代码简洁,常被用在大学生计算机课程中. "冒泡"这个名字的由来是因为越大的元素会经由交换慢慢"浮"到数列的顶端,故名. 这里以从小到大排序为例进行讲解. 基本思想及举例说明 冒泡排序的基本思想就是不断比较相邻的两个数,让较大的元素不断地往后移.经过一轮比较,就选出最大的数:经过第2轮比较,就选出次大的数,以此类推. 下面以对 3  2  4  1 进行冒泡排序说明. 第一轮 排序过程3  2  4  1    (最初) 2  3 

C 语言快速排序实例代码_C 语言

快速排序是对冒泡法排序的一种改进. 快速排序算法 的基本思想是:将所要进行排序的数分为左右两个部分,其中一部分的所有数据都比另外一 部分的数据小,然后将所分得的两部分数据进行同样的划分,重复执行以上的划分操作,直 到所有要进行排序的数据变为有序为止. 可能仅根据基本思想对快速排序的认识并不深,接下来以对n个无序数列A[0], A[1]-, A[n-1]采用快速排序方法进行升序排列为例进行讲解. (1)定义两个变量low和high,将low.high分别设置为要进行排序的序列的起始元素和最后一个元

C语言的冒泡排序和快速排序算法使用实例_C 语言

冒泡排序法 题目描述:     用一维数组存储学号和成绩,然后,按成绩排序输出. 输入:     输入第一行包括一个整数N(1<=N<=100),代表学生的个数.     接下来的N行每行包括两个整数p和q,分别代表每个学生的学号和成绩. 输出:     按照学生的成绩从小到大进行排序,并将排序后的学生信息打印出来.     如果学生的成绩相同,则按照学号的大小进行从小到大排序. 样例输入:     3     1 90     2 87     3 92 样例输出:     2 87