实现Dijkstra算法最短路径问题详解

这篇文章主要介绍了实现Dijkstra算法最短路径问题详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下

实现Dijkstra算法最短路径问题详解,久久派带你了解更多相关信息。

1、最短路径问题介绍

问题解释:
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径

解决问题的算法:

  • 迪杰斯特拉算法(Dijkstra算法)
  • 弗洛伊德算法(Floyd算法)
  • SPFA算法

这篇博客,我们就对Dijkstra算法来做一个详细的介绍

2、Dijkstra算法介绍

算法特点:

  • 迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
  • 算法的思路
    Dijkstra算法采用的是一种贪心的策略,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合:T,初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s。然后,从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,OK,此时完成一个顶点,
    然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。
    然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。

3、Dijkstra算法示例演示

下面我求下图,从顶点v1到其他各个顶点的最短路径

实现Dijkstra算法最短路径问题详解

首先第一步,我们先声明一个dis数组,该数组初始化的值为:

实现Dijkstra算法最短路径问题详解

我们的顶点集T的初始化为:T={v1}

既然是求 v1顶点到其余各个顶点的最短路程,那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后,dis[2](下标从0开始)的值就已经从“估计值”变为了“确定值”,即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。
为什么呢?因为目前离 v1顶点最近的是 v3顶点,并且这个图所有的边都是正数,那么肯定不可能通过第三个顶点中转,使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

OK,既然确定了一个顶点的最短路径,下面我们就要根据这个新入的顶点V3会有出度,发现以v3 为弧尾的有: < v3,v4 >,那么我们看看路径:v1–v3–v4的长度是否比v1–v4短,其实这个已经是很明显的了,因为dis[3]代表的就是v1–v4的长度为无穷大,而v1–v3–v4的长度为:10+50=60,所以更新dis[3]的值,得到如下结果:

实现Dijkstra算法最短路径问题详解

因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3],通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想:通过“边”来松弛v1顶点到其余各个顶点的路程。

然后,我们又从除dis[2]和dis[0]外的其他值中寻找最小值,发现dis[4]的值最小,通过之前是解释的原理,可以知道v1到v5的最短距离就是dis[4]的值,然后,我们把v5加入到集合T中,然后,考虑v5的出度是否会影响我们的数组dis的值,v5有两条出度:< v5,v4>和 < v5,v6>,然后我们发现:v1–v5–v4的长度为:50,而dis[3]的值为60,所以我们要更新dis[3]的值.另外,v1-v5-v6的长度为:90,而dis[5]为100,所以我们需要更新dis[5]的值。更新后的dis数组如下图:

实现Dijkstra算法最短路径问题详解

然后,继续从dis中选择未确定的顶点的值中选择一个最小的值,发现dis[3]的值是最小的,所以把v4加入到集合T中,此时集合T={v1,v3,v5,v4},然后,考虑v4的出度是否会影响我们的数组dis的值,v4有一条出度:< v4,v6>,然后我们发现:v1–v5–v4–v6的长度为:60,而dis[5]的值为90,所以我们要更新dis[5]的值,更新后的dis数组如下图:

实现Dijkstra算法最短路径问题详解

然后,我们使用同样原理,分别确定了v6和v2的最短路径,最后dis的数组的值如下:

实现Dijkstra算法最短路径问题详解

因此,从图中,我们可以发现v1-v2的值为:∞,代表没有路径从v1到达v2。所以我们得到的最后的结果为:

起点  终点    最短路径    长度v1    v2     无          ∞          v3     {v1,v3}    10      v4     {v1,v5,v4}  50      v5     {v1,v5}    30      v6     {v1,v5,v4,v6} 60

4、Dijkstra算法的代码实现(c++)

  • Dijkstra.h文件的代码

/************************************************************//*                程序作者:Willam                          *//*                程序完成时间:2017/3/8                    *//*                有任何问题请联系:2930526477@qq.com       *//************************************************************///@尽量写出完美的程序#pragma once//#pragma once是一个比较常用的C/C++杂注,//只要在头文件的最开始加入这条杂注,//就能够保证头文件只被编译一次。#include<iostream>#include<string>using namespace std;/*本程序是使用Dijkstra算法实现求解最短路径的问题采用的邻接矩阵来存储图*///记录起点到每个顶点的最短路径的信息struct Dis {    string path;    int value;    bool visit;    Dis() {        visit = false;        value = 0;        path = \"\";    }};class Graph_DG {private:    int vexnum;   //图的顶点个数    int edge;     //图的边数    int **arc;   //邻接矩阵    Dis * dis;   //记录各个顶点最短路径的信息public:    //构造函数    Graph_DG(int vexnum, int edge);    //析构函数    ~Graph_DG();    // 判断我们每次输入的的边的信息是否合法    //顶点从1开始编号    bool check_edge_value(int start, int end, int weight);    //创建图    void createGraph();    //打印邻接矩阵    void print();    //求最短路径    void Dijkstra(int begin);    //打印最短路径    void print_path(int);};

  • Dijkstra.cpp文件的代码

#include\"Dijkstra.h\"//构造函数Graph_DG::Graph_DG(int vexnum, int edge) {    //初始化顶点数和边数    this->vexnum = vexnum;    this->edge = edge;    //为邻接矩阵开辟空间和赋初值    arc = new int*[this->vexnum];    dis = new Dis[this->vexnum];    for (int i = 0; i < this->vexnum; i++) {        arc[i] = new int[this->vexnum];        for (int k = 0; k < this->vexnum; k++) {            //邻接矩阵初始化为无穷大                arc[i][k] = INT_MAX;        }    }}//析构函数Graph_DG::~Graph_DG() {    delete[] dis;    for (int i = 0; i < this->vexnum; i++) {        delete this->arc[i];    }    delete arc;}// 判断我们每次输入的的边的信息是否合法//顶点从1开始编号bool Graph_DG::check_edge_value(int start, int end, int weight) {    if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {        return false;    }    return true;}void Graph_DG::createGraph() {    cout << \"请输入每条边的起点和终点(顶点编号从1开始)以及其权重\" << endl;    int start;    int end;    int weight;    int count = 0;    while (count != this->edge) {        cin >> start >> end >> weight;        //首先判断边的信息是否合法        while (!this->check_edge_value(start, end, weight)) {            cout << \"输入的边的信息不合法,请重新输入\" << endl;            cin >> start >> end >> weight;        }        //对邻接矩阵对应上的点赋值        arc[start - 1][end - 1] = weight;        //无向图添加上这行代码        //arc[end - 1][start - 1] = weight;        ++count;    }}void Graph_DG::print() {    cout << \"图的邻接矩阵为:\" << endl;    int count_row = 0; //打印行的标签    int count_col = 0; //打印列的标签    //开始打印    while (count_row != this->vexnum) {        count_col = 0;        while (count_col != this->vexnum) {            if (arc[count_row][count_col] == INT_MAX)                cout << \"∞\" << \" \";            else            cout << arc[count_row][count_col] << \" \";            ++count_col;        }        cout << endl;        ++count_row;    }}void Graph_DG::Dijkstra(int begin){    //首先初始化我们的dis数组    int i;    for (i = 0; i < this->vexnum; i++) {        //设置当前的路径        dis[i].path = \"v\" + to_string(begin) + \"-->v\" + to_string(i + 1);        dis[i].value = arc[begin - 1][i];    }    //设置起点的到起点的路径为0    dis[begin - 1].value = 0;    dis[begin - 1].visit = true;    int count = 1;    //计算剩余的顶点的最短路径(剩余this->vexnum-1个顶点)    while (count != this->vexnum) {        //temp用于保存当前dis数组中最小的那个下标        //min记录的当前的最小值        int temp=0;        int min = INT_MAX;        for (i = 0; i < this->vexnum; i++) {            if (!dis[i].visit && dis[i].value<min) {                min = dis[i].value;                temp = i;            }        }        //cout << temp + 1 << \"  \"<<min << endl;        //把temp对应的顶点加入到已经找到的最短路径的集合中        dis[temp].visit = true;        ++count;        for (i = 0; i < this->vexnum; i++) {            //注意这里的条件arc[temp][i]!=INT_MAX必须加,不然会出现溢出,从而造成程序异常            if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {                //如果新得到的边可以影响其他为访问的顶点,那就就更新它的最短路径和长度                dis[i].value = dis[temp].value + arc[temp][i];                dis[i].path = dis[temp].path + \"-->v\" + to_string(i + 1);            }        }    }}void Graph_DG::print_path(int begin) {    string str;    str = \"v\" + to_string(begin);    cout << \"以\"<<str<<\"为起点的图的最短路径为:\" << endl;    for (int i = 0; i != this->vexnum; i++) {        if(dis[i].value!=INT_MAX)        cout << dis[i].path << \"=\" << dis[i].value << endl;        else {            cout << dis[i].path << \"是无最短路径的\" << endl;        }    }}

  • main.cpp文件的代码

#include\"Dijkstra.h\"//检验输入边数和顶点数的值是否有效,可以自己推算为啥://顶点数和边数的关系是:((Vexnum*(Vexnum - 1)) / 2) < edgebool check(int Vexnum, int edge) {    if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)        return false;    return true;}int main() {    int vexnum; int edge;    cout << \"输入图的顶点个数和边的条数:\" << endl;    cin >> vexnum >> edge;    while (!check(vexnum, edge)) {        cout << \"输入的数值不合法,请重新输入\" << endl;        cin >> vexnum >> edge;    }    Graph_DG graph(vexnum, edge);    graph.createGraph();    graph.print();    graph.Dijkstra(1);    graph.print_path(1);    system(\"pause\");    return 0;}

输入:

6 8

1 3 10

1 5 30

1 6 100

2 3 5

3 4 50

4 6 10

5 6 60

5 4 20

输出: 

实现Dijkstra算法最短路径问题详解

从输出可以看出,程序的结果和我们之前手动计算的结果是一样的。

到此这篇关于实现Dijkstra算法最短路径问题详解的文章就介绍到这了,更多相关C++实现Dijkstra算法内容请搜索趣讯吧以前的文章或继续浏览下面的相关文章希望大家以后多多支持趣讯吧!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,请发送邮件至 55@qq.com 举报,一经查实,本站将立刻删除。转转请注明出处:https://www.szhjjp.com/n/11867.html

(0)
nan
上一篇 2021-08-11
下一篇 2021-08-11

相关推荐

  • 银行一年利息怎么算(银行一年利息多少)

    建设银行,是我国传统的“四大国有行”之一,拥有着众多的营业网点,业务范围也非常的广泛。在众多的业务当中,当属定期存款类业务为最常见的业务。相信很多投资者,尤其是一些中老年投资者,都喜欢将自己的积蓄存在建设银行的定期存款中,既安全又稳定。那么,在建设银…

    2022-01-15
    0
  • 新手怎样申请淘宝店铺呢?

    新手怎样申请淘宝店铺呢?,爱惜日带你了解相关信息。其实很简单,一张身份证,3步就可以完成打开淘宝网,找到我的淘宝,上方的导航上选择免费开店!然后选择个人开店。新手建议先开个人店,因为操作简,容易上手!!按上面的提示进行就行,上面都写的很清楚!最后要实名认证。注意开店认证和支付宝实名认证必须是同一个人!认证需要准备身份证正反面,还有本人手拿身份证正反面的照片!当然人

    2021-09-04
    0
  • excel中取前几位数字的函数(利用函数提取数字)

    一个EXCEL,如果我们要截取一个表格内容的前面几位。我们需要用到的一个函数就是MID。MID函数用于从指定位置开始,提取我们指定的字符数。例如,从第1个字符开始,提取4个字符,公式表示为MID(参数1,1,4),参数1表示要提取字符串的单元格,参数

    2021-10-07
    0
  • 安利沐浴露价格表(安利雅蜜系列产品)

    一到夏天,对于爱洗澡的小仙女们来说,选择一款舒心又香气的沐浴露真的很重要!它不仅能赶走你一天疲惫的工作情绪,还能把汗渍和油腻通通洗掉,让你的身体留有余香。今天小编就来给大家安利几款香香的沐浴露,需要的

    2021-12-17 用户投稿
    0
  • 从这4部分研究事半功倍(济宁网站运营策略)

    网站运营分为四个部分:内容运营、用户运营、活动运营和新媒体运营。1内容运营网站建设,网站内容作为一个主要的发挥,我们把它放在第一位。首先,网站运营最基本的事情就是不断更新网站,以避免网站动态过少和搜索引擎排名下降的现象。因此,网站内容的

    2021-12-16
    0
  • 微信20w限额满了怎么办(微信转账限额怎么解除)

    21世纪的今天,许多互联网技术促使传统行业的改变及适应,如央视电台建立抖音官方帐户,银行也于电子支付发展之际作出相应措施。微信作为目前最受欢迎的社交app及电子支付途径,受央行的监管要求,个人用户的微信每年转账额度不能超过20万元,然而许多商家收入于

    2021-09-24 用户投稿
    0

发表回复

登录后才能评论