程序员经验分享-hwhale

Dijkstra算法图解，C++实现Dijkstra算法

2023-05-16

目录

    • Dijkstra算法简介
    • 数据结构抽象
    • 初始化
    • 开始计算
      • 第一轮计算
      • 第二轮计算
      • 第三轮计算
      • 第四轮计算
      • 算法总结
    • C++实现Dijkstra算法

Dijkstra算法简介

Dijkstra算法计算是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到起点距离最近且未访问过的顶点的邻接节点，直到扩展到所有终点为止。

数据结构抽象

现在我们有一个景点地图，假设从1号顶点出发，求到其他各个顶点的最短路径。算法步骤如下：
设置地图的带权邻接矩阵为map[][]，如果从顶点 i 到顶点 j 有边，则map[i][j] == <i,j>的权值，否则map[i][j] == (无穷大)。
在这里插入图片描述

邻接矩阵为map[ ][ ]抽象为一个二维数组，表示每两个顶点之间的权值，[ i ][ j ]和[ j ][ i ]表示两个顶点之间不同方向的权值。
在这里插入图片描述

初始化

令集合S={ 1 }，S初始化只包含起点u，集合V-S = { 2，3，4，5 }，对于集合V-S中的所有顶点x，初始化最短距离数组dist[ i ] = map[ 1 ] [ i ]，dist[ u ]=0（起点到起点为0）如图3所示。如果源点1到顶点 i 有边相连，初始化前驱数组p[ i ] = 1，否则p[ i ] = -1，如图4所示。
最短距离数组dist[ i ] ，表示顶点1到其他顶点之间的最短距离，该数组经过每次计算会动态变化。
在这里插入图片描述

前驱数组p[ i ]，表示到达该顶点的前一个顶点编号，也是动态变化的。
在这里插入图片描述

开始计算

第一轮计算

1.找最小
在集合V-S = {2，3，4，5} 中，依照贪心策略来寻找 V-S集合中dist[ ]最小的顶点 T，如图3，找到最小值为2，对应的顶点 T = 2。
2. 加入S集合
将顶点T = 2加入集合S中，S={1， 2}，同时更新V-S = {3，4，5}，如图5所示。
在这里插入图片描述

3. 走捷径
刚刚找到了起点到 T = 2的最短路径，那么对集合 V-S中所有 T 的邻接点，都可以借助 T 走捷径。我们从图或邻接矩阵都可以看出，2号顶点的邻接点是3和4号顶点，如图2所示。

先看3号结点能否借助2号走捷径: dist[2] + map[2][3] = 2+2 = 4，而当前dist[3] = 5>4，因此可以走捷径即2–3，更新dist[3] = 4，记录顶点3的前驱为2，即p[3] = 2。

再看4号结点能否借助2号走捷径:如果dist[2] + map[2][4] = 2+6 = 8，而当前dist[4] = ∞ > 8.因此可以走捷径即2-4，更新dist[4] = 8，记录顶点4的前驱为2，即p[4] = 2。
更新后如图6和图7所示。

在这里插入图片描述

第二轮计算

1.找最小
在集合 V-S = {3，4，5)中，依照贪心策略来寻找dist[]中具有最小值的顶点T，找到最小值为4，对应的结点T = 3，如图6。
2. 加入S集合
将顶点T = 3加入集合S中，S={1，2，3}，同时更新V-S = {4，5}，如图8所示。
在这里插入图片描述
3. 走捷径
刚刚找到了源点到T = 3 的最短路径，那么对集合 V-S中所有T的邻接点 ，都可以借助T走捷径。我们从图或邻接矩阵可以看出，3号结点的邻接点是4和5号结点

先看4号结点能否借助3号走捷径:dist[3]+map[3][4] = 4+7 = 11，而当前dist[4] = 8 < 11，比当前路径还长，因此不更新。

再看5号结点能否借助3号走捷径:dist[3]+map3][5] = 4+1 = 5，而当前dis[5] = ∞ > 5，因此可以走捷径，即3一5，更新dist[5] = 5，记录顶点5的前驱为3，即p[5] = 3，更新后如图9和图10 所示。
在这里插入图片描述

第三轮计算

1.找最小
在集合 V-S = {4，5}中，依照贪心策略来寻找V- S 集合中dist[ ] 最小的顶点T，如图9所示，找到最小值为5，对应的结点T = 5。
2. 加入S集合
将顶点T = 5加入集合S中，S = {1，2，3，5}，同时更新V-S = {4}，如图11所示。
在这里插入图片描述
3. 走捷径
刚刚找到了源点到T = 5的最短路径，那么对集合V-S中所有T = 5的邻接点，都可以借助T = 5走捷径。我们从图或邻接矩阵可以看出，5 号结点没有邻接点，因此不更新，如图9 和图10 所示。

第四轮计算

1.找最小
在集合 V-S = {4}中，依照贪心策略来寻找 dist最小的顶点，只有一个顶点，所以很容易找到，找到最小值为8，对应的结点T= 4，如图9所示。
2. 加入S集合
将顶点T=4加入集合S中，S = {1，2，3，5，4}，同时更新 V-S = { }，如图12所示。
在这里插入图片描述
3. 走捷径
V-S = { }为空，算法停止。

算法总结

map[i][j]：把图抽象为二维数组，下标代表各个顶点，值代表两个顶点ij之间的权值。
S集合：已经遍历且找到最短路径的顶点集合。
V-S集合：还未遍历的顶点集合，最短路径在寻找中。
T：当前正在遍历的顶点。
dist[ i ] ： 最短距离数组，表示当前起点到其他顶点之间的最短距离，该数组经过每次计算会动态变化。
p[ i ]：前驱数组，表示当前到达该顶点的前一个顶点编号，也是动态变化的。

算法的关键是理解走捷径：
走捷径的意思是：已找到起点到T的最短路径，起点到T的最短路径 + T到T的邻接顶点P的权值 < 当前记录起点到P的最短路径，则更新P的最短路径和前一跳。

每轮计算都是重复的操作，直到遍历了图中所有顶点，得到dist[ ]和p[ ]。
可求得从源点图中其余各个顶点的最短路径及长度，也可通过前驱数组逆向找到最短路径上经过的顶点。
例如，p[5] = 3，即5的前驱是3，p[3] = 2，即3的前驱是2，p[2] = 1，即2的前驱是1，p[1] = -1，1没有前驱，那么从起点1到5的最短路径为1-2-3-5。

C++实现Dijkstra算法

头文件

#ifndef DIJKSTRA_H
#define DIJKSTRA_H

#include <string>
#include <fstream>
#include <iostream>
#include <vector>
#define MAX_VERNUM 20//最大顶点数
#define MAX_VALUE 99999//最大权值
using namespace std;

//顶点
struct Node
{
    string path;           //路径
    string NodeName;       //节点名字
    vector<string> next_Node;//从起点开始到终点所经过的节点，不包括起点
    int value;             //路径权值
    bool visit;            //是否访问过
    Node()
    {
        visit = false;
        value = 0;
        NodeName = "";
        next_Node.clear();
        path = "";
    }
};

class Dijkstra
{
public:
    Dijkstra();
    ~Dijkstra();

    void Create_graph();                    //创建图
    void Dijkstra_cpt(string from);         //迪斯拉算法求最短路径
    void Display_table(string from);        //输出路由表

    void Modify_edge(string from, string to, int value);                        //修改边
    void Add_node(string nodename);                      //添加顶点
    void Del_node(string r1);                      //删除顶点
private:
    int vernum;                             //图的顶点个数
    int **adjmatrix;                        //邻接矩阵
    Node *node;                             //记录各个顶点最短路径的信息
};

#endif // DIJKSTRA_H

源文件

#include "Dijkstra.h"

int g_nodeNum = 5;//顶点数量
int g_edgeNum = 8;//边的数量
int g_edge[8][3] = {//边的集合
    //起点，终点，权值
    {1, 2, 2},
    {1, 3, 5},
    {2, 3, 2},
    {2, 4, 6},
    {3, 4, 7},
    {3, 5, 1},
    {4, 3, 2},
    {4, 5, 4}
};

Dijkstra::Dijkstra()
{

}

//析构函数
Dijkstra::~Dijkstra()
{
    delete[] node;                      //释放一维数组node内存
    for (int i = 0; i < MAX_VERNUM; i++)//释放二维数组adjmatrix内存
    {
        delete this->adjmatrix[i];
    }
    delete adjmatrix;
}

//创建图
void Dijkstra::Create_graph()
{
    vernum = g_nodeNum;                    //初始化顶点数和边数
    node   = new Node[MAX_VERNUM];              //保留顶点信息，其中共有MAX_VERNUM条边
    adjmatrix = new int*[MAX_VERNUM];         //数组一维长度为MAX_VERNUM
    for (int i = 0; i < MAX_VERNUM; i++)
    {
        adjmatrix[i] = new int[MAX_VERNUM];   //数组二维长度也为MAX_VERNUM
        for (int k = 0; k < MAX_VERNUM; k++)
        {
            adjmatrix[i][k] = MAX_VALUE;      //邻接矩阵初始化为无穷大
        }
    }

    for(int index=0;index<g_edgeNum;index++)
    {
        //对邻接矩阵对应上的点赋值
        adjmatrix[g_edge[index][0] - 1][g_edge[index][1] - 1] = g_edge[index][2];
    }

    for (int i = 0; i < this->vernum; i++)    //初始化node数组的编号
    {
        node[i].NodeName = "r" + to_string(i + 1);
    }
}

//算法主体
void Dijkstra::Dijkstra_cpt(string from)
{
    int f, i, j, k;
    for (f = 0; f < this->vernum; f++)
    {
        if (from.compare(node[f].NodeName) == 0)
            break;
    }
    for (i = 0; i < this->vernum; i++)//初始化node数组
    {
        node[i].path = from + "-->" + node[i].NodeName;
        node[i].next_Node.clear();
        node[i].next_Node.push_back(node[i].NodeName);
        node[i].value = adjmatrix[f][i];
        node[i].visit = false;
    }
    node[f].value = 0;                //设置起点到起点的路径为0
    node[f].visit = true;

    for (i = 1; i < this->vernum; i++)//计算剩余的顶点的最短路径
    {
        int temp = 0;                 //temp用于保存当前node数组中最小的那个下标
        int min = MAX_VALUE;          //min记录的当前的最小值
        for (j = 0; j < this->vernum; j++)
        {
            if (!node[j].visit && node[j].value < min)
            {
                min = node[j].value;
                temp = j;
            }
        }
        node[temp].visit = true;      //把temp对应的顶点加入到已经找到的最短路径的集合中
        for (k = 0; k < this->vernum; k++)
        {
            //起点到T的最短路径 + T到T的邻接顶点P的权值  < 当前记录起点到P的最短路径
            if (!node[k].visit && adjmatrix[temp][k] != MAX_VALUE && (node[temp].value + adjmatrix[temp][k]) < node[k].value)
            {
                node[k].path = node[temp].path + "-->" + node[k].NodeName;
                node[k].next_Node = node[temp].next_Node;
                node[k].next_Node.push_back(node[k].NodeName);
                node[k].value = node[temp].value + adjmatrix[temp][k];
            }
        }
    }
    Display_table(from);
}

//输出路由表
void Dijkstra::Display_table(string from)
{
    int i;
    bool flag = false;
    for (i = 0; i < this->vernum; i++)
    {
        if (from.compare(node[i].NodeName) == 0)
           flag = true;
    }
    if (flag == false)
        printf("can not found node\n");
    else
    {
        printf("start:%s\n",from.c_str());
        for (i = 0; i < this->vernum; i++)
        {
            cout << "dest:" << node[i].NodeName << "  ";
            printf("next:%s,value:%d\n",node[i].next_Node.at(0).c_str(),node[i].value);
        }
    }
    cout << endl;
}

//添加边
void Dijkstra::Modify_edge(string from,string to,int value)
{
    int f, t;
    for (f = 0; f < this->vernum; f++)    //找到起点对应的数组坐标
    {
        if (from.compare(node[f].NodeName) == 0)
            break;
    }
    for (t = 0; t < this->vernum; t++)    //找到终点对应的数组坐标
    {
        if (to.compare(node[t].NodeName) == 0)
            break;
    }
    adjmatrix[f][t] = value;              //对邻接矩阵对应上的点赋值
}

//添加顶点
void Dijkstra::Add_node(string nodename)
{
    node[vernum].NodeName = nodename;
    this->vernum++;
}

//删除顶点
void Dijkstra::Del_node(string r1)
{
    int r2, i, j, count = 0;
    for (r2 = 0; r2 < this->vernum; r2++)
    {
        if (r1.compare(node[r2].NodeName) == 0)
            break;
    }
    for (i = 0; i < this->vernum; i++)  //统计与删除的顶点相关的边数
    {
        if(adjmatrix[r2][i] != MAX_VALUE)
            count++;
    }

    for(i = 0;i < this->vernum; i++)    //调整邻接矩阵
    {
        for(j = 0;j < this->vernum; j++)//将邻接矩阵向内紧缩
        {
            if(i > r2 && j > r2)        //调整右下角部分
                adjmatrix[i-1][j-1] = adjmatrix[i][j];
            else if(i > r2)             //调整右上角部分
                adjmatrix[i-1][j] = adjmatrix[i][j];
            else if(j > r2)             //调整左下角部分
                adjmatrix[i][j-1] = adjmatrix[i][j];
        }
    }
    for(i = 0;i < this->vernum; i++)
    {
        adjmatrix[this->vernum][i] = MAX_VALUE;
        adjmatrix[i][this->vernum] = MAX_VALUE;
    }

    for(i = r2; i < this->vernum-1; i++)//调整顶点数组值
        node[i] = node[i+1];
    this->vernum--;
}

调用

    mDijkstra.Create_graph();
    mDijkstra.Dijkstra_cpt("r1");

打印：

start:r1
dest:r1  next:r1,value:0
dest:r2  next:r2,value:2
dest:r3  next:r2,value:4
dest:r4  next:r2,value:8
dest:r5  next:r2,value:5
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Dijkstra算法图解，C++实现Dijkstra算法 的相关文章

随机推荐

  • 发送一个http请求以及url三部分组成和语法

    浏览器从URL中解析出服务器的主机名浏览器讲服务器的主机名转化成服务器的IP地址 xff08 DNS解析 xff09 浏览器将端口号从URL解析出来浏览器建立一条鱼web服务器的TCP连接浏览器向服务器发送一条http请求报文服务器向浏览器

  • 结构体对齐规则

    结构体 xff1a 结构体 xff08 struct xff09 是由一系列具有相同类型或不同类型的数据构成的集合 因为这一特性 xff0c 方便了开发者在使用的过程中可以将需要的不同的数据类型放在一起 xff0c 做成我们需要的数据类型

  • GPS坐标用于机器人定位的简单处理

    文章目录 前言一 GPS数据格式二 GPS坐标转换二维坐标原理三 参考代码1 转换经纬度格式2 解析通过串口获得的NMEA数据3 将经纬度转换为xy平面二维坐标 前言 最近工作上面接触使用GPS的NMEA数据为机器人提供平面坐标定位 xff

  • 学完C++基础后再学什么？

    学完 xff1f 那是什么程度 xff1f STL用得熟练吗 xff1f 算法和数据结构掌握得怎么样呢 xff1f 会写界面吗 xff1f BOOST呢 xff1f 像楼上所说的换一种语言 xff0c 简直是痴人说梦 xff0c 如果不深入

  • 视觉SLAM十四讲：回环检测-知识点+代码

    目录 基于外观的几何关系1 基础知识1 1 准确率和召回率1 2 词袋模型1 3 字典1 4 字典的数据结构1 5 相似度的计算1 6 相似度评分的处理1 7 检测回环后的验证 2 实践与代码解析2 1 创建字典2 2 相似度计算 回环检测

  • QT笔记--QT内类的层次关系，以及控件从属关系

    QT窗口界面使用的类层次如下 只包含了直接使用部分 界面上每一个创建的控件 xff0c 都是一个控件类的对象 xff0c 定义在头文件ui mainwindoow h的类UI MainWindow中 xff0c 并且其中的成员函数setup

  • C_带参数的宏定义

    C 带参数的宏定义 xff23 语言允许宏带有参数 在宏定义中的参数称为形式参数 xff0c 在宏调用中的参数称为实际参数 对带参数的宏 xff0c 在调用中 xff0c 不仅要宏展开 xff0c 而且要用实参去代换形参 带参宏定义的一般形

  • 十进制数转换成十六进制数~C语言

    include lt stdio h gt 下面将整数a转换成十六进制输出的字符串 原理 xff1a 1 xff0c 首先知道0b100000 61 0b10000 2 61 0b1000 2 61 0b100 2 61 0b10 2 利用

  • Qt实现线程安全的单例模式

    实现方式 1 实现单例 把类的构造函数 拷贝构造函数 赋值操作符定义为private的 xff1b 把获取单例的接口和唯一的实例指针定义为static的 xff0c 不需要实例化 xff0c 直接通过类名即可访问 2 支持多线程 采用双重校

  • 文本文件和二进制文件的差异和区别

    广义上的二进制文件包括文本文件 xff0c 这里讨论的是狭义上的二进制文件与文本文件的比较 xff1a 能存储的数据类型不同 文本文件只能存储char型字符变量 二进制文件可以存储char int short long float 各种变量

  • Qt实现记录日志文件log

    概述 Qt有两种实现记录日志的方式 xff0c 第一种是安装自定义的Qt消息处理程序 xff0c 自动输出程序产生的调试消息 警告 关键和致命错误消息的函数 xff1b 第二种是自定义一个类 xff0c 可以在程序指定位置打印输出指定的内容

  • Qt在linux环境下调用动态库，pro工程文件加载库和QLibrary加载库两种方式

    QT调用动态库 xff0c 在编译时和运行时的方式不同 xff0c 编译时可在pro文件加载或使用QLibrary类加载 xff1b 运行时依赖环境变量 xff0c windows下直接把动态库拷贝到可执行文件目录即可 xff0c linu

  • linux下QT发布程序双击打不开解决方法

    现象 Qt开发的程序 xff0c 使用 终端可以打开 xff0c 双击却打不开 阶段一 右键可执行程序 xff0c 选择属性 xff0c 可执行程序类型如果是 application x sharedlib xff0c 在QT的pro文件添

  • Qt发起http请求，get和post方式，并接收响应数据

    目录 Qt发起http请求get xff0c 异步接收Qt发起http请求post xff0c 异步接收Qt发起http请求get和post xff0c 收发同步http下载网络图片 Qt发起http请求get xff0c 异步接收 get

  • QT实现浏览器访问网页，使用QWebEngineView

    支持访问网页 xff0c 前进 后退 刷新 xff0c 点击超链接自动跳转 xff0c 获取网页鼠标事件 xff0c 重新编译QWebEngineView库后还可以支持播放mp4等视频 xff1b Qt在debug模式运行有时访问网页很卡

  • Qt程序打包成安装包exe

    本章介绍把Qt开发的程序打包成安装包的方法 xff0c 程序打包成install exe xff0c 可双击安装 xff0c 有默认安装路径 xff0c 也可以选择安装目录 xff0c 自动生成桌面快捷方式和开始菜单选项 xff0c 可以在

  • C/C++socket网络编程

    目录 tcp和udp通信流程图socket函数bind函数listen函数accept函数connect函数recv recvfrom read函数send write sendto sendmsg函数close shutdown函数hto

  • OSPF路由协议解释

    目录 OSPF路由协议OSPF数据包类型OSPF邻区状态OSPF的邻接关系建立过程 路由名词解释OSPF开源项目 OSPF路由协议 OSPF简介 1 xff08 Open Shortest Path First xff09 xff0c 开放

  • redis服务搭建，C++实现redis客户端，redis远程可视化工具

    目录 redis简介redis服务搭建redis常用命令C 43 43 实现redis客户端redis远程可视化工具 Another Redis DeskTop Manager redis简介 官方网址 xff1a https redis

  • Dijkstra算法图解，C++实现Dijkstra算法

    目录 Dijkstra算法简介数据结构抽象初始化开始计算第一轮计算第二轮计算第三轮计算第四轮计算算法总结 C 43 43 实现Dijkstra算法 Dijkstra算法简介 Dijkstra算法计算是从一个顶点到其余各顶点的最短路径算法 x

热门标签