算法-图-dijkstra 最短路径

理论知识

dijkstra三部曲

朴素版dijkstra

模拟过程 

堆优化版dijksra

经典模版例题

Dijkstra求最短路 I   

参加科学大会（第六期模拟笔试）--模版题

网络延迟

ref

理论知识

        最短路是图论中的经典问题即：给出一个有向图，一个起点，一个终点，问起点到终点的最短路径。

        dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。需要注意两点：

  • dijkstra 算法可以同时求 起点到所有节点的最短路径
  • 权值不能为负数

dijkstra三部曲

  1. 第一步，选源点到哪个节点近且该节点未被访问过;（minDist数组里的数值，结合visited数组筛选出未访问的节点）
  2. 第二步，该最近节点被标记访问过;（更新visited数组）
  3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）。minDist数组 用来记录 每一个节点距离源点的最小距离。（更新minDist数组）（初始化的时候就应该初始为最大值）

朴素版dijkstra

模拟过程 

        ①初始化：节点0 不做处理，统一从下标1 开始计算，源点（节点1） 到自己的距离为0，所以 minDist[1] = 0； 此时所有节点都没有被访问过，所以 visited数组都为0。

        ②dijkstra 三部曲 ：

         

        

      

    

 更新 minDist数组，即：源点（节点1） 到 节点6 、 节点3 和 节点4【与当前被访问节点2相连的节点】的距离。

  • 源点到节点6的最短距离为5，小于原minDist[6]的数值max，更新minDist[6] = 5
  • 源点到节点3的最短距离为3，小于原minDist[3]的数值4，更新minDist[3] = 3
  • 源点到节点4的最短距离为6，小于原minDist[4]的数值max，更新minDist[4] = 6

 

  • 源点到节点4的最短距离为5，小于原minDist[4]的数值6，更新minDist[4] = 5

 

 

...........

...........最终

        节点1）到终点（节点7）的最短距离就是 minDist[7] ，按上面举例讲解来说，minDist[7] = 12，节点1 到节点7的最短路径为 12。 

堆优化版dijksra

        1、邻接表结构存储： vector<vector<pair<int, int>>> adj(n + 1); // 邻接表直接存储边

        2、初始化最  短距离数组和优先队列，设定起点距离

        使用小顶堆（priority_queue）存储 <距离, 节点> 对，初始时将起点 (0, 1) 加入队列

                priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

        3、主循环：通过优先队列快速找到当前最短路径节点，并更新邻接节点。

                

用到的数据结构：

 vector<vector<pair<int, int>>> adj(n + 1)

adj[1] = { {2, 2}, {3, 4} }; // 从 1 出发，有 1→2 (权2)，1→3 (权4)
adj[2] = { {3, 1}, {4, 7} }; // 从 2 出发，有 2→3 (权1)，2→4 (权7)

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

动态维护当前扩展的最短路径节点

经典模版例题

Dijkstra求最短路 I  

完整代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> grid(n+1,vector<int>(n+1,INT_MAX));
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        if (z < grid[x][y]) {  // 处理重边，保留最小权重
            grid[x][y] = z;
        }
    }
    vector<int> minDist(n+1,INT_MAX);
    vector<bool> visited(n+1,false);
    int start=1;
    minDist[start]=0;
    for(int i=1;i<=n;i++)
    {
        int minval=INT_MAX;
        int cur=-1;
        for(int j=1;j<=n;j++)
        {
            if(!visited[j]&&minDist[j]<minval)
            {
                minval=minDist[j];
                cur=j;
            }
        }
        if (cur == -1) break;  // 所有剩余节点不可达
        visited[cur]=true;
        for(int j=1;j<=n;j++)
        {
            if(!visited[j]&&grid[cur][j]!=INT_MAX&&grid[cur][j]+minDist[cur]<minDist[j])
            {
                minDist[j]=minDist[cur]+grid[cur][j];
            }
        }
        
    }
    if(minDist[n]==INT_MAX) cout<<"-1";
    else cout<<minDist[n];
    return 0;
}

注意重边？？？？？！！！！  

堆优化版：

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

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> adj(n + 1); // 邻接表直接存储边

    // 读取边并构建邻接表（无需预处理二维数组）
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        adj[x].emplace_back(y, z); // 直接添加所有边
    }

    // Dijkstra算法
    vector<int> dist(n + 1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    dist[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue; // 跳过过时记录

        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    // 输出结果
    cout << (dist[n] == INT_MAX ? -1 : dist[n]);
    return 0;
}

 

参加科学大会（第六期模拟笔试）--模版题

完整代码： （我真的好爱卡哥，代码简洁又易懂！！！！！）

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    //邻接矩阵存储
    vector<vector<int>> grid(n+1,vector<int>(n+1,INT_MAX));//初始化数值为INT_MAX
    for(int i=0;i<m;i++) //输入边权
    {
        int s,e,v;
        cin>>s>>e>>v;
        grid[s][e]=v;//存储边权值
    }
    int start=1;//记录源点，从哪个点开始走
    int end=n;//记录终点
    vector<int> minDist(n+1,INT_MAX);//存储每个点至源点的最小距离
    minDist[start]=0;//源点到自身距离为0；
    vector<bool> visited(n+1,false);//记录该点是否被访问过，初始化都没有被访问过
    //依次遍历所有结点
    for(int i=1;i<=n;i++)
    {
        int minval=INT_MAX;
        int cur=start;//记录当前被访问的点中哪个点距离源点最近

        //1、选距离源点最近&&没有被访问过的点
        for(int v=1;v<=n;v++)
        {
            if(!visited[v]&&minDist[v]<minval)
            {
                minval=minDist[v];
                cur=v;//记录该最近结点的id
            }
        }
        //2、标记该最近结点beifnagw
        visited[cur]=true;
        //3、更新其他非访问节点到源点的距离（更新minDist数组）
        for(int v=1;v<=n;v++)
        {
            //没有被访问过的、与 cur相连的、更新后minDist更小的
            if(!visited[v]&&grid[cur][v]!=INT_MAX &&minDist[v]>minDist[cur]+grid[cur][v])
            minDist[v]=minDist[cur]+grid[cur][v];
        }

    }

    //不能到达终点
    if(minDist[end]==INT_MAX) cout<<-1<<endl;
    else cout<<minDist[end]<<endl; //输出到达终点的最短路径

    return 0;
    
}

堆优化版：

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

int main() {
    int n, m;
    cin >> n >> m;

    // 邻接表存储：adj[x]保存从x出发的所有边，格式为<目标节点, 边权>
    vector<vector<pair<int, int>>> adj(n + 1);

    // 处理输入并保留最小边权（处理重边）
    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
    for (int i = 0; i < m; ++i) {
        int s, e, v;
        cin >> s >> e >> v;
        if (v < grid[s][e]) grid[s][e] = v;  // 仅保留最小权重
    }

    // 将邻接矩阵转换为邻接表
    for (int x = 1; x <= n; ++x) {
        for (int y = 1; y <= n; ++y) {
            if (grid[x][y] != INT_MAX) {
                adj[x].push_back({y, grid[x][y]});
            }
        }
    }

    // Dijkstra堆优化实现
    vector<int> dist(n + 1, INT_MAX);        // 存储起点到各节点的最短距离
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 小顶堆，格式<距离, 节点>
    dist[1] = 0;                             // 起点距离初始化为0
    pq.push({0, 1});                         // 将起点加入堆

    while (!pq.empty()) {
        auto [d, u] = pq.top();              // 取出当前距离最小的节点
        pq.pop();

        if (d > dist[u]) continue;           // 跳过过时的路径记录

        for (auto [v, w] : adj[u]) {         // 遍历所有邻接节点
            if (dist[v] > dist[u] + w) {     // 发现更短路径
                dist[v] = dist[u] + w;       // 更新距离
                pq.push({dist[v], v});       // 将新距离加入堆
            }
        }
    }

    // 输出结果：终点不可达则输出-1
    cout << (dist[n] == INT_MAX ? -1 : dist[n]) << endl;
    return 0;
}

 

网络延迟

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

int main() {
    int n, k, m;
    cin >> n >> k >> m;
    vector<vector<int>> grid(n+1, vector<int>(n+1, INT_MAX));
    
    for(int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        grid[u][v] = w; // 存储有向边
    }
    
    vector<int> minDist(n+1, INT_MAX);
    vector<bool> visited(n+1, false);
    minDist[k] = 0; // 起点距离为0
    
    for(int i = 1; i <= n; ++i) {
        int minVal = INT_MAX;
        int cur = -1;
        // 寻找当前未访问的最小距离节点
        for(int v = 1; v <= n; ++v) {
            if (!visited[v] && minDist[v] < minVal) {
                minVal = minDist[v];
                cur = v;
            }
        }
        // 所有剩余节点不可达
        if (cur == -1) break;
        visited[cur] = true;
        // 更新相邻节点
        for(int v = 1; v <= n; ++v) {
            if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] != INT_MAX) {
                if (minDist[v] > minDist[cur] + grid[cur][v]) {
                    minDist[v] = minDist[cur] + grid[cur][v];
                }
            }
        }
    }
    
    int maxTime = 0;
    for(int i = 1; i <= n; ++i) {
        if (minDist[i] == INT_MAX) {
            cout << -1 << endl;
            return 0;
        }
        maxTime = max(maxTime, minDist[i]);
    }
    cout << maxTime << endl;
    return 0;
}

堆优化版： 

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

int main() {
    int n, k, m;
    cin >> n >> k >> m;

    vector<vector<pair<int, int>>> adj(n + 1); // 邻接表存储图

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
    }

    // Dijkstra算法
    vector<int> dist(n + 1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    dist[k] = 0;
    pq.push({0, k});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    int maxTime = *max_element(dist.begin() + 1, dist.end());
    cout << (maxTime == INT_MAX ? -1 : maxTime) << endl;

    return 0;
}

 

和模版几乎一样，只是最后判断为：所有的minDist不是INT_MAX(均可达)，输出是最大的时间（所有举例源点的最短路径中最大的那一个！！！！！！） 好开心~ 

ref

代码随想录

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/982359.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【leetcode hot 100 48】旋转图像

【leetcode hot 100 48】旋转图像

方法一&#xff1a;&#xff08;原地旋转&#xff09;对于矩阵中第 i 行的第 j 个元素&#xff0c;在旋转后&#xff0c;它出现在倒数第 i 列的第 j 个位置。matrix[row][col]在旋转后的新位置为matrix[col][n−row−1]。只要旋转四次就能回到原点。 class Solution {public vo…
阅读更多...
Vue Hooks 深度解析：从原理到实践

Vue Hooks 深度解析：从原理到实践

Vue Hooks 深度解析&#xff1a;从原理到实践 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家&#xff01;点我试试&#xff01;&#xff01; 文章目录 Vue Hooks 深度解析&#xff1a;从原理到实践一、背景…
阅读更多...
ESP32S3读取数字麦克风INMP441的音频数据

ESP32S3读取数字麦克风INMP441的音频数据

ESP32S3 与 INMP441 麦克风模块的集成通常涉及使用 I2S 接口进行数字音频数据的传输。INMP441 是一款高性能的数字麦克风&#xff0c;它通过 I2S 接口输出音频数据。在 Arduino 环境中&#xff0c;ESP32S3 的开发通常使用 ESP-IDF&#xff08;Espressif IoT Development Framew…
阅读更多...
逐行拆解 C 语言：数据类型、变量

逐行拆解 C 语言：数据类型、变量

今日&#xff0c;我们即将踏上一段充满趣味与挑战的学习之旅&#xff0c;深度钻研数据类型的多样奥秘&#xff0c;解锁变量创建的实用技巧。不仅如此&#xff0c;还会邂逅两个实用的基础库函数&#xff0c;探索它们在程序中穿针引线的奇妙作用。同时&#xff0c;几个简洁却强大…
阅读更多...
【Java数据结构】前K个高频单词

【Java数据结构】前K个高频单词

前K个高频单词 692. 前K个高频单词 - 力扣&#xff08;LeetCode&#xff09; 解决这个问题我们先得知道每个单词出现的次数&#xff0c;用map存储下来&#xff0c;然后将出现次数最多的通过建立小根堆解决top-K问题 &#xff0c;重点是top-K的求取。 1.建立map 首先我们可以…
阅读更多...
锂电池升压到5V并且可以锂电池充电的芯片SM5401

锂电池升压到5V并且可以锂电池充电的芯片SM5401

收拾旧物时发现一个旧台灯&#xff0c;正好又有一节锂电池&#xff0c;于是想改成&#xff1a;用锂电池给台灯供电&#xff08;台灯是5V的&#xff09;&#xff0c;并且可以通过USB给锂电池充电。 于是找到了SM5401这个芯片。 SM5401 可以把锂电池电压升压成5V输出&#xff0c…
阅读更多...
大模型工程师学习日记（十五）：Hugging Face 模型微调训练（基于 BERT 的中文评价情感分析）

大模型工程师学习日记（十五）：Hugging Face 模型微调训练（基于 BERT 的中文评价情感分析）

1. datasets 库核心方法 1.1. 列出数据集 使用 d atasets 库&#xff0c;你可以轻松列出所有 Hugging Face 平台上的数据集&#xff1a; from datasets import list_datasets# 列出所有数据集 all_datasets list_datasets()print(all_datasets)1.2. 加载数据集 你可以通过 l…
阅读更多...
高考數學。。。

高考數學。。。

2024上 具体来说&#xff0c;直线的参数方程可以写为&#xff1a; x1t y−t z1t 二、简答题(本大题共5小题&#xff0c;每小题7分&#xff0c;共35分。) 12.数学学习评价不仅要关注结果评价&#xff0c;也要关注过程评价。简要说明过程评价应关注哪几个方面。…
阅读更多...
Seurat - Guided Clustering Tutorial官方文档学习及复现

Seurat - Guided Clustering Tutorial官方文档学习及复现

由于本人没有使用过Seurat4.0&#xff0c;而是直接使用的最新版。所以本文都是基于Seurat5.2.0&#xff08;截止2025/3/6&#xff09;来进行撰写。 参考的官方教程来进行学习&#xff08;上图中的 Guided tutorial-2.700 PBMCs&#xff09;&#xff0c;肯定没有官方文档那么全面…
阅读更多...
(undone) MIT6.S081 Lec14 File systems 学习笔记

(undone) MIT6.S081 Lec14 File systems 学习笔记

url: https://mit-public-courses-cn-translatio.gitbook.io/mit6-s081/lec14-file-systems-frans Why Interesting 从一个问题开始&#xff1a;既然你每天都使用了文件系统&#xff0c;XV6的文件系统与你正在使用的文件系统有什么区别。接下来我会点名&#xff1a; 学生回答…
阅读更多...
【C++进阶学习】第一讲——继承（下）---深入挖掘继承的奥秘

【C++进阶学习】第一讲——继承（下）---深入挖掘继承的奥秘

目录 1.隐藏 1.1隐藏的概念 1.2隐藏的两种方式 2.继承与友元 3、继承与静态成员 4.单继承和多继承 4.1单继承 4.2多继承 5.菱形继承 问题1&#xff1a;冗余性 问题2&#xff1a;二义性 6.虚拟继承 7.总结 1.隐藏 1.1隐藏的概念 在 C 中&#xff0c;继承是一种机制…
阅读更多...
UI自动化：利用百度ocr识别解决图形验证码登录问题

UI自动化：利用百度ocr识别解决图形验证码登录问题

相信大家在做自动化测试过程中都遇到过图形验证码的问题&#xff0c;最近我也是遇到了&#xff0c;网上搜了很多方法&#xff0c;最简单的方法无非就是去掉图形验证码或者设置一个万能验证码&#xff0c;但是这个都需要开发来帮忙解决&#xff0c;对于我们这种自学的人来说就不…
阅读更多...
C/C++蓝桥杯算法真题打卡（Day1）

C/C++蓝桥杯算法真题打卡（Day1）

一、LCR 018. 验证回文串 - 力扣&#xff08;LeetCode&#xff09; 算法代码&#xff1a; class Solution { public:bool isPalindrome(string s) {int n s.size();// 处理一下s为空字符的情况if (n 0) {return true; // 修正拼写错误}// 定义左右指针遍历字符串int left …
阅读更多...
蓝桥杯备考：动态规划路径类DP之矩阵的最小路径和

蓝桥杯备考：动态规划路径类DP之矩阵的最小路径和

如题&#xff0c;要求左上角到右下角的最短路径&#xff0c;我们还是老样子按顺序做 step1:确定状态表示 f[i][j]表示(1,1)到(i,j)的最短距离 step2 :推导状态表达方程 step3:确定填表顺序&#xff0c;应该是从上到下&#xff0c;从左到右 step4:初始化 step5 找结果&#…
阅读更多...
18类创新平台培育入库！长沙经开区2025年各类科技创新平台培育申报流程时间材料及申报条件

18类创新平台培育入库！长沙经开区2025年各类科技创新平台培育申报流程时间材料及申报条件

长沙经开区打算申报企业研发中心、技术创新中心、工程技术研究中心、新型研发机构、重点实验室、概念验证中心和中试平台、工程研究中心、企业技术中心、制造业创新中心、工业设计中心等创新平台的可先备案培育入库&#xff0c;2025年各类平台的认定将从培育库中优先推荐&#…
阅读更多...
CyberDefenders----WebStrike Lab

CyberDefenders----WebStrike Lab

WebStrike Lab 实验室链接 简介： 公司网络服务器上发现了一个可疑文件，在内联网中发出警报。开发团队标记了异常，怀疑存在潜在的恶意活动。为了解决这个问题，网络团队捕获了关键网络流量并准备了一个 PCAP 文件以供审查。您的任务是分析提供的 PCAP 文件以发现文件的出现…
阅读更多...
【python】gunicorn配置

【python】gunicorn配置

起因&#xff1a;因为cpu利用率低导致我去缩容&#xff0c;虽然缩容之后cpu利用率上升维持在60%左右&#xff0c;但是程序响应耗时增加了。 解释&#xff1a;因为cpu干这件活本身不累&#xff0c;但在干这件活的时候不能去干其他事情&#xff0c;导致并发的请求不能及时响应&am…
阅读更多...
SSE vs WebSocket：AI 驱动的实时通信抉择

SSE vs WebSocket：AI 驱动的实时通信抉择

引言 近年来，基于 Transformer 的大模型推动了 AI 产业的飞速发展，同时带来了新的技术挑战： 流式传输 vs 批量返回：大模型生成的长文本若需一次性返回，会显著影响用户体验，实时推送成为必需。语音交互需求：语音助手要求毫秒级响应，而非等待用户完整输入后再返回结果。…
阅读更多...
基于海思soc的智能产品开发（芯片sdk和linux开发关系）

基于海思soc的智能产品开发（芯片sdk和linux开发关系）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 随着国产化芯片的推进&#xff0c;在soc领域&#xff0c;越来越多的项目使用国产soc芯片。这些soc芯片&#xff0c;通常来说运行的os不是linux&…
阅读更多...
各种DCC软件使用Datasmith导入UE教程

各种DCC软件使用Datasmith导入UE教程

3Dmax: 先安装插件 https://www.unrealengine.com/zh-CN/datasmith/plugins 左上角导出即可 虚幻中勾选3个插件,重启引擎 左上角选择文件导入即可 Blender导入Datasmith进UE 需要两个插件, 文章最下方链接进去下载安装即可 一样的,直接导出,然后UE导入即可 C4D 直接保存成…
阅读更多...
最新文章

Copyright @ 2022~2023