Dijkstra实现(邻接表C++版)

这篇具有很好参考价值的文章主要介绍了Dijkstra实现(邻接表C++版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Dijkstra实现 —— 邻接表

1. 问题描述

从V0出发,到各个节点的最短距离

Dijkstra实现(邻接表C++版)

2. 解决方法(Dijkstra算法)

1. 建立Dijkstra表

Dijkstra的过程,就是维护并更新一个表来实现的。

  • 其中distance表示是从起始节点,到当前节点的距离。

  • path表示经过哪个节点达到当前节点。

  • 表初始化为:path全-1,distance全为INT_MAX。

vertices path distance
0 -1
1 -1
2 -1
3 -1
4 -1
5 -1

2. 更新

2.1. 选择0(初始化)(假定从0出发)

vertices path distance
0 0 0
1 -1
2 -1
3 -1
4 -1
5 -1

2.2 循环更新

  • 每次选择一个新的节点,加入当前的连通分量中,其中选择的规则为:选择当前dis最小的节点(假设为节点Vk)。

  • 将它加入连通分量,并使用它的相邻节点,更新distance,其中更新distance的原则是:

    • 如果经过Vk,到达节点Vm的dis (即dis[Vk] + edge{Vk, Vm}) 小于 当前的dis[vm],那么dis[vm] = dis[Vk] + edge{Vk, Vm}. (其中edge{Vk, Vm}表示Vk与Vm相连的边的长度)。

举例:从2.1表中,我们可以选择dis最小的节点,显然只有V0,将图中所有与V0相连的节点(即V1,V3,V4 节点)。

其中对于V1:dis[V0] + edge{V0, V1} = 0 + 1; 明显小于当前的dis[V1] = ∞,所以更新dist[1] = 1。V3,V4同理更新为4。

vertices path distance
0 0 0
1 0 1
2 -1
3 0 4
4 0 4
5 -1
  • 再次选择一个新的节点:当前distance中最小的点是dis[1] = 1,将V1从dis中抹除(说明已经找到了从0到它的最小距离为1),将V1的所有相连节点加入的新dis计算出来(如果小于当前dis,就更新):

    new_dis_V3 = dis[V1] + edge{V1, V3} = 1 + 2 < dis[V3] = 4,因此更新dis[V3] = 2, 并且更新path为1。

vertices path distance
0 0 0
1 0 1
2 -1
3 1 3
4 0 4
5 -1
  • 继续选择dis表中最小节点(其实这时候V0和V1这时候对应的0,1已经使用过了,将不被使用),这次选取的是V3对应的2,将V3的所有相连节点加入的新dis计算出来(如果小于当前dis,就更新):

    • new_dis_v2 = dis[V3] + edge{V3, V2} = 3 + 2 < dis[V2] = ∞,所以更新dis[2] = 5,并且将path[2]设置为3
    • new_dis_v4 = dis[V4] + edge{V3, V4} = 3 + 3 > dis[V4] = 4,所以不更新dis[4]
vertices path distance
0 0 0
1 0 1
2 3 5
3 1 3
4 0 4
5 -1
  • … 继续以上路径,可以得到最终结果

3. C++代码实现

3.0 代码设计

3.0.1 数据结构设计

图使用的是邻接表形式,即:

vector<vector<pair<int, int>>> graph; // 邻接表{from, {to, dis}} (即pair<int, int> = {to, dis})

distance 和 path都是简单的数组结构:

vector<int> path;
vector<int> dis;
3.0.1 更新操作

dis需要经常更新(每次寻找最小的节点,将它删除,并将对应的节点插入)—— 可以用小根堆来做👇

注意:邻接表{from, {to, dis}} (即pair<int, int> = {to, dis})。这里的cmp就是以pair中的第二个元素,即edg{Vk, Vm}的大小来判断在堆中的位置。

struct cmp{
    bool operator()(pair<int, int>& a, pair<int, int>& b) {
        return a.second < b.second;
    }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
3.0.2 代码的基本流程

1. 建立图 + 初始化

2. 一个循环,循环n次,更新dis和path

3. 输出结果,程序结束

3.1 代码 + 编译命令

完整的cpp代码如下👇(代码保存于Dijkstra.cpp中,编译命令为g++ Dijkstra.cpp -o dijkstra文章来源地址https://www.toymoban.com/news/detail-412112.html

// g++ Dijkstra.cpp -o dijkstra

#include <bits/stdc++.h>
using namespace std;

vector<int> path;
vector<int> dis;
vector<vector<pair<int, int>>> graph; // 邻接表{from, {to, dis}} (即pair<int, int> = {to, dis})

struct cmp{
    bool operator()(pair<int, int>& a, pair<int, int>& b) {
        return a.second < b.second;
    }
};

void print_vec(vector<int> &vec);
void print_graph();
void construct_graph(vector<vector<int>>& times, int n);
void dijkstra(int start);


int main() {
    vector<vector<int>> times = {
        {0, 1, 1},
        {0, 3, 4},
        {0, 4, 4},
        {1, 3, 2},
        {2, 5, 1},
        {3, 2, 2},
        {3, 4, 3},
        {4, 5, 3},
    };
    int n = 6;
    int start_id = 0;
    construct_graph(times, n);
    dijkstra(start_id);
    // print_vec(dis);
    exit(0);
}

void print_graph() {
    int n = graph.size();
    for (int i = 0; i < n; ++i) {
        cout << i << ": ";
        for (auto elem : graph[i]) {
            cout << "{" << elem.first << ", " << elem.second << "}, ";
        }
        cout << endl;
    }
}
void print_vec(vector<int> &vec) {
    for (auto elem : vec) {
        cout << elem << " ";
    }
    cout << endl << "---------------" <<endl;
}

// 构建图
void construct_graph(vector<vector<int>>& times, int n) {
    for (int i = 0; i < n; ++i) {
        graph.push_back(vector<pair<int, int>>());
    }
    for (auto edg : times) {
        graph[edg[0]].push_back({edg[1], edg[2]}); 
    }
}


void dijkstra(int start) {
    cout << "in dijkstra" << endl;
    // 初始化
    int n = graph.size();
    for (int i = 0; i < n; ++i) {
        path.push_back(-1);
        dis.push_back(INT_MAX);
    }
    dis[start] = 0;
    path[start] = start;

    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
    q.push({start, 0});
    while (!q.empty()) {
        // cout << "q.size() = " << q.size() <<endl;
        int cur_id = q.top().first;
        int cur_dis = q.top().second;
        q.pop();

        // 说明已经访问过了
        if (cur_dis > dis[cur_id]) {
            continue;
        }

        // 将cur_id相邻的节点装入队列
        for (pair<int, int>& neighbor : graph[cur_id]) {
            int next_id = neighbor.first;
            int next_dis = dis[cur_id] + neighbor.second;
            if (next_dis < dis[next_id]) {
                dis[next_id] = next_dis;
                q.push({next_id, next_dis});
                path[next_id] = cur_id;
            }
        }
    }

    cout << "dis = ";
    print_vec(dis);

    cout << "path = ";
    print_vec(path);
}

3.2 运行结果:

levi@LEVI1:~/code$ g++ Dijkstra.cpp -o dijkstra
levi@LEVI1:~/code$ ./dijkstra 
in dijkstra
dis = 0 1 5 3 4 6 
---------------
path = 0 0 3 1 0 2 
---------------

到了这里,关于Dijkstra实现(邻接表C++版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【图论】Dijkstra 算法求最短路 - 构建邻接矩阵(带权无向图)

    题目链接:1976. 到达目的地的方案数

    2024年03月22日
    浏览(44)
  • c语言写邻接矩阵的最短路径的Dijkstra算法(附有详细代码)

    (1) 用dis数组来存储源点1到其他顶点的初始路径,标记1号顶点, 此时dis数组中的值称为最短路径的估计值。 (2) 从dis数组中找出离源起点最近的点2号,以2号顶点为源点进行找最近的顶点。把2号顶点标记,表示已经有最小值。 以2号顶点为源点,看2号顶点有哪些出边,看能不

    2024年02月05日
    浏览(45)
  • 图论基础: 邻接矩阵与邻接表(c++实现)

    邻接矩阵(Adjacency Matrix)是表示 顶点之间相邻关系 的矩阵。 设G=(顶点,边):G=(V,E)是一个图。其中V={v1,v2,…,vn} [1] 。G的邻接矩阵是一个具有下列性质的n阶方阵: 无向图的邻接矩阵一定是成对角线对称的,是一个 对称矩阵 ,有向图 不一定 是对称的。 有向图当把它的 行

    2024年02月05日
    浏览(44)
  • C++实现图—邻接矩阵,邻接表,深度遍历,广度遍历

    目录 1.图的基本概念 2.图的存储结构 2.1邻接矩阵 2.2 邻接表 3.图的遍历 3.1广度优先遍历 3.2图的深度遍历  总结: 图是由顶点集合以及顶点之间的关系组成的一种数据结构:G = (V,E),其中顶点集合V={x|x属于某个对象集}是有穷非空集合; E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Pa

    2024年02月06日
    浏览(55)
  • C++数据结构之图的存储结构——邻接矩阵和邻接表实现无向图

    关键点: 1.构建二维数组 2.对应边的位置赋值为1 由于比较简单就直接上代码: 个人对邻接表实现无向图的理解如下,仅供参考:         由于无向图的组成是由多个顶点和多条无向边组成的,因此我们可以把它拆分成两个结构,分别是顶点和无向边,又由于我们是使用

    2024年02月05日
    浏览(55)
  • 邻接矩阵储存图实现深度优先遍历(C++)

          目录 基本要求: 图的结构体: 图的构造: 图的深度优先(DFS): 图的打印输出: 完整代码: 测试数据:  运行结果:      通过给出的图的顶点和边的信息,构建无向图的邻接矩阵存储结构。在此基础上,从A顶点开始,对无向图进行深度优先遍历,输出遍历序列

    2024年02月03日
    浏览(46)
  • 【路径规划】全局路径规划算法——Dijkstra算法(含python实现 | c++实现)

    路径规划与轨迹跟踪系列算法学习 最短路径算法-迪杰斯特拉(Dijkstra)算法 迪杰斯特拉dijkstra算法的python实现 Python实现迪杰斯特拉算法 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个节点遍历其余各节点的最短路

    2024年02月08日
    浏览(48)
  • C++算法:单源最短路径Dijkstra

    如果你有一份北京地图,想从中关村走到三元桥,那么怎样能找出实现这一目的的最短路径呢?一种可能的方法就是将这两点之间所有的路线都找出来,然后求出每条路线的距离,找出最短的路线。但是仔细想想我们就会发现这种办法几乎是不可行的,因为这样的路线太多了,

    2024年02月09日
    浏览(45)
  • (迪杰斯特拉)Dijkstra算法及其优化(C++)

    题目描述 给定一个 n n n 个点 m m m 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。 请你求出 1 1 1 号点到 n n n 号点的最短距离,如果无法从 1 1 1 号点走到 n n n 号点,则输出 − 1 −1 − 1 。 输入格式 第一行包含整数 n n n 和 m m m 。 接下来 m m m 行每行包含三

    2023年04月09日
    浏览(43)
  • 【C++数据结构 | 图速通】10分钟掌握邻接矩阵 & 邻接表 | 快速掌握图论基础 | 快速上手抽象数据类型图

    by.Qin3Yu 请注意:严格来说,图不是一种数据结构,而是一种抽象数据类型。但为了保证知识点之间的相关性,也将其列入数据结构专栏。 本文需要读者掌握顺序表和单链表的操作基础,若需学习,可参阅我的往期文章: 【C++数据结构 | 顺序表速通】使用顺序表完成简单的成

    2024年02月05日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包