算法板子:最短路问题——包含朴素Dijkstra算法、堆优化版的Dijkstra算法、SPFA算法、Floyd算法

目录

    • 1. 几种算法的用途
    • 2. Dijkstra算法——求源点到其他所有点的最短路径(不能处理负边权)
      • (1)朴素Dijkstra算法——适用于稠密图
      • (2)堆优化版的Dijkstra算法——适用于稀疏图
    • 4. SPFA算法——求源点到其他所有点的最短路径、判断是否存在负环(可以处理负边权)
      • (1)求有负边权的图的最短路径——求源点到其他所有点的最短路径
      • (2)判断图中是否存在负环(负环指环的权重和为负数)
    • 5. Floyd算法——求图中任意两点之间的最短路径(可以处理负边权)

1. 几种算法的用途

在这里插入图片描述

在这里插入图片描述

2. Dijkstra算法——求源点到其他所有点的最短路径(不能处理负边权)

(1)朴素Dijkstra算法——适用于稠密图

#include <iostream>
#include <cstring>
using namespace std;const int N = 500 + 10;
int n, m;// 这道题边的条数接近于顶点数量的²,边多是稠密图,用邻接矩阵g来存图; 如果一个图有n个节点,那么邻接矩阵的大小就是n*n
int g[N][N];// d[i]代表源点s到i号点的最短路径; 比如d[4]=3代表源点到点4的最短路径为3
// inf代表int值的无穷大
int d[N], inf = 0x3f3f3f3f;
// vis数组标识某个点是否出圈; vis[4]=0代表节点4没有出圈
int vis[N];// 传入源点s,计算出各个点到源点s的最短路径
int dijkstra(int s)
{// 先将源点到所有点(包括0点)的距离初始化为无穷大inffor (int i = 0; i <= n; i ++ ) d[i] = inf;// 修改源点到源点的最短路径, 为0d[s] = 0;for (int i = 1; i < n; i ++ ){int u = 0;// u保存圈内离源点最近的点for (int j = 1; j <= n; j ++ )if (!vis[j] && d[j] < d[u]) u = j;// 将找到的最近的点u出圈vis[u] = 1;// 更新源点到出圈的点u的邻接点的最短路径for (int j = 1; j <= n; j ++ ){// g[u][j]的值不等于inf代表j是u的邻接点; d[j]代表源点s到点j到的最短路径; d[u]+g[u][j]代表通过u这个点到达点j的路径长度// 对比一下点j是原先的路径更短还是通过点u到达点j是路径更短, 更新源点到点j的最短路径if (g[u][j] != inf) d[j] = min(d[j], d[u] + g[u][j]);}}// 如果源点1到点n的最短路径为无穷大, 说明不存在最短路径if (d[n] == inf) return -1;// 如果最短路径不是无穷大, 说明存在最短路径return d[n];
}int main()
{cin >> n >> m;// 将邻接矩阵每条边的权重都初始化为无穷大memset(g, 0x3f, sizeof g);// 使用邻接矩阵存储图; 若某个点到某个点有边,那么就在对应位置上存上权重,且始终存最小权重for (int i = 0; i < m; i ++ ){int a, b, w;cin >> a >> b >> w;g[a][b] = min(g[a][b], w); }// 因为这道题要算点1到点n的最短路径, 那么源点就可以设置成1, 通过dijkstra算法可以得到源点1到所有点的最短路径, 并在算法的最后返回源点1到点n的最短路径cout << dijkstra(1) << endl;return 0;
}

(2)堆优化版的Dijkstra算法——适用于稀疏图

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;const int N = 2e5 + 10;
typedef pair<int, int> PII;// 优先级队列q相当于大根堆
// 这里堆顶放的是距离源点最近的点,比如该点距离源点的距离为3,其他点距离源点的距离更大,取相反数后插入堆中,那么距离最近的就是值最大的,放在堆顶
// 堆q每个元素为一个对组,键为源点到该点的最短路径,值是点
priority_queue<PII> q;
// vis标记某点是否已出队,只有未出队的才能更新它的邻接点的最短路径; vis[2]=0代表2这个点未出队
// d[i]代表源点到点i的最短路径
int vis[N], d[N], inf = 0x3f3f3f3f;
// 这道题边比较少,是稀疏图,用邻接表存图; w数组存储权重
int h[N], e[N], ne[N], w[N], idx;int n, m;void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}int dijkstra(int s)
{// 将源点到所有点的最短路径初始化为无穷大for (int i = 0; i <= n; i ++ ) d[i] = inf;// 将源点加入堆d[s] = 0; q.push({-d[s], s});while (q.size()){// 取堆顶; 取出距离源点最近的点auto t = q.top(); q.pop();int u = t.second;// 如果已经出队过,就不能更新邻接点if (vis[u]) continue;// 如果没有出队过,标记它现在已经出队过vis[u] = 1;// 更新该点的邻接点的最短路径for (int i = h[u]; i != -1; i = ne[i]){int j = e[i], c = w[i];// 如果邻接点需要更新,则加入堆中if (d[u] + c < d[j]){d[j] = d[u] + c;q.push({-d[j], j});}}}if (d[n] == inf) return -1;return d[n];
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);for (int i = 0; i < m; i ++ ){int a, b, c;cin >> a >> b >> c;add(a, b, c);}cout << dijkstra(1) << endl;return 0;
}

4. SPFA算法——求源点到其他所有点的最短路径、判断是否存在负环(可以处理负边权)

(1)求有负边权的图的最短路径——求源点到其他所有点的最短路径

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;const int N = 1e5 + 10;int h[N], e[N], ne[N], w[N], idx;
queue<int> q;
int d[N], inf = 0x3f3f3f3f;
// vis[i]代表点i是否在队中; vis[3]=1代表点3在队中, vis[3]=0代表点3不在队中
int vis[N];int n, m;void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}void spfa(int s)
{// 将源点到全部点的最短路径全部初始化为无穷大memset(d, inf, sizeof d);d[s] = 0;// 将源点入队q.push(s); vis[s] = 1;while (q.size()){// 出队队头,标记队头不在队中int f = q.front(); q.pop(); vis[f] = 0;// 更新队头邻接点的最短路径for (int i = h[f]; i != -1; i = ne[i]){int j = e[i], c = w[i];if (d[f] + c < d[j]){d[j] = d[f] + c;// 如果点j不在队中,则加入队中if (!vis[j]) q.push(j), vis[j] = 1;}}}if (d[n] == inf) cout << "impossible" << endl;else cout << d[n] << endl;
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);for (int i = 0; i < m; i ++ ) {int a, b, c;cin >> a >> b >> c;add(a, b, c);}spfa(1);return 0;
}

(2)判断图中是否存在负环(负环指环的权重和为负数)

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;const int N = 1e5 + 10;
int n, m;int h[N], e[N], ne[N], w[N], idx;
queue<int> q;
// 在图上增加一个虚拟源点,虚拟源点到图中每个点都有条权重为0的边
// cnt数组代表虚拟源点到该点的最短路径的边数; 比如cnt[3]=3代表虚拟源点到点3的最短路径的边数为3
int d[N], vis[N], cnt[N];void add(int a, int b, int c)
{e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}bool spfa()
{// 把所有点加入队列中for (int i = 1; i <= n; i ++ ) q.push(i), vis[i] = true;while (q.size()){int f = q.front(); q.pop(); vis[f] = 0;for (int i = h[f]; i != -1; i = ne[i]){int j = e[i], c = w[i];// 更新源点到点j的最短路径if (d[f] + c < d[j]){// 更新最短路径的长度d[j] = d[f] + c;// 更新最短路径的边数cnt[j] = cnt[f] + 1;// 如果虚拟源点到点j的边数大于等于节点数,则存在负环if (cnt[j] >= n) return true;if (!vis[j]) q.push(j), vis[j] = 1;}}}// 图中不存在负环return false;
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);for (int i = 0; i < m; i ++ ) {int a, b, c;cin >> a >> b >> c;add(a, b, c);}cout << (spfa() ? "Yes" : "No") << endl;return 0;
}

5. Floyd算法——求图中任意两点之间的最短路径(可以处理负边权)

#include <iostream>
using namespace std;const int N = 200 + 10;// d[i][j]代表点i到点j经过节点1~k的最短路径的长度; 例如d[1][3]=2代表点1到点3的最短路径长度为2
int d[N][N], INF = 0x3f3f3f3f;int n, m, k;// 更新两点之间的最短路径
void floyd()
{for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}int main()
{cin >> n >> m >> k;// 处理自环; 图中有可能存在自环,比如点1到点1存在条边,那么点1到点1的最短路径就是0for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= n; j ++ ){if (i == j) d[i][j] = 0;else d[i][j] = INF;}}// d可以先看成一个邻接矩阵,存储两点之间边的最小权重for (int i = 0; i < m; i ++ ){int a, b, w;cin >> a >> b >> w;// 图中两点之间可能有重边,保留权重最小的那条边即可d[a][b] = min(d[a][b], w);}floyd();while (k -- ){int a, b;cin >> a >> b;// 如果点a到点b的距离不是无穷大,则存在最短路径; 是无穷大,不存在最短路径; // 这里将无穷大定义为INF/2是因为,就算点a到点b不存在最短路径,但由于存在负边权,有可能使得路径从无穷大变得比无穷大小一些// 所以如果当前点a到点b的路径比无穷大的一半还大,我们就认为两点之间还是无穷大,还是没有最短路径if (d[a][b] > INF / 2) cout << "impossible" << endl;else cout << d[a][b] << endl;}return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

WordPress原创插件:disable-gutenberg禁用古腾堡编辑器和小工具

WordPress原创插件&#xff1a;disable-gutenberg禁用古腾堡编辑器和小工具 disable-gutenberg插件下载:https://download.csdn.net/download/huayula/89616495

SpringBoot快速学习

目录 SpringBoot配置文件 多环境配置 SpringBoot整合junit SpringBoot整合mybatis 1.在创建时勾选需要的模块 2.定义实体类 3.定义dao接口 4.编写数据库配置 5.使用Druid数据源 SpringBoot 是对 Spring 开发进行简化的。 那我们先来看看SpringMVC开发中的一些必须流…

翻译: 梯度下降 深度学习神经网络如何学习一

在上一节影片里我讲解了神经网络的结构 首先我们来快速回顾一下 在本节影片里&#xff0c;我们有两个目标 首介绍梯度下降的概念 它不仅是神经网络工作的基础 也是很多其他机器学习方法的基础 然后我们会研究一下这个特别的网络是如何工作的 以及这些隐藏的神经元层究竟在寻找什…

使用Openvino部署C++的Yolov5时类别信息混乱问题记录

使用Openvino部署C的Yolov5时类别信息混乱问题记录 简单记录一下。 一、问题描述 问题描述&#xff1a;在使用Yolov5的onnx格式模型进行C的Openvino进行模型部署时&#xff0c;通过读取classes.txt获得类别信息时&#xff0c;出现模型类别混乱&#xff0c;或者说根本就不给图…

如何将avi格式转换为flv格式呢?

FLV是随着FLASH MX的推出发展而来的一种视频格式&#xff0c;目前被众多新一代视频分享网站所采用&#xff0c;是目前增长较快&#xff0c;也较为广泛的视频传播格式。 FLV格式可以轻松导入FLASH播放器中&#xff0c;另外它还能起到保护版权的作用&#xff0c;非常受欢迎。那么…

在优化微信、支付宝小程序用户体验时有哪些关键指标

在优化小程序用户体验时&#xff0c;有几个关键指标需要特别关注&#xff0c;这些指标不仅能够帮助评估当前的用户体验状况&#xff0c;还能为后续的优化工作提供明确的方向。以下是一些关键指标及其解释&#xff1a; 1. 日活跃用户&#xff08;DAU&#xff09; 是指每天使用…

『 Linux 』网络基础

文章目录 协议分层OSI 七层模型TCP/IP 四层(五层)模型网络协议栈与操作系统的联系报文TCP/IP 通讯过程以太网通信的过程以太网的数据碰撞 协议分层 协议分层是计算机网络中奖网络协议进行组织和管理的方法; 通过将网络通信过程分成多个层次,每个层次负责特定的功能从而简化网络…

触屏交互设备的安全风险

现实中的绝大多数电子设备都具有交互性&#xff0c;而现在越来越多的公共场合有布置越来越多的带触屏的交互设备&#xff0c;功能有简单的&#xff0c;有复杂的&#xff0c;布置的场所和应用的场合也各有不同&#xff0c;几乎在任何一个大型公共场合都可以看到这样的设备&#…

【算法 03】雇佣问题

“雇用问题”及其算法优化 在日常生活和工作中&#xff0c;我们经常会遇到需要从多个选项中做出选择的情况&#xff0c;而“雇用问题”正是这样一个典型的例子。在这个问题中&#xff0c;我们不仅要考虑如何高效地找到最佳候选人&#xff0c;还要关注整个过程中的成本。今天&a…

提高工作效率: AWS Gen AI 在几秒钟内总结会议记录

欢迎来到雲闪世界。全面介绍如何利用 AWS Lambda、Bedrock 和 S3 创建总结会议记录的工作流程 免责声明&#xff1a;本文中使用的会议记录纯属虚构&#xff0c;仅用于作为本文说明和教育目的。它并不反映任何实际的对话、事件或个人。任何与实际人物或事件的相似之处纯属巧合。…

为什么网站要使用HTTPS访问

网站使用HTTPS访问的原因有很多&#xff0c;主要可以归纳为以下几个关键点&#xff1a; 1、数据安全性&#xff1a;HTTPS使用SSL/TLS协议对通信过程进行加密&#xff0c;确保信息在传输过程中不被窃取、篡改或冒充。对于涉及敏感信息&#xff08;如个人身份、信用卡号等&#x…

数字人解决方案——音频驱动机器人

音频集成 机器人 标志着 人工智能&#xff08;AI&#xff09;。 想象一下&#xff0c;机器人可以通过视觉和听觉导航并与周围环境互动。音频驱动的机器人使这成为可能&#xff0c;提高了它们更高效、更直观地执行任务的能力。这一发展可能会影响到各个领域&#xff0c;包括家庭…

github技巧和bug解决方法短篇收集

有一些几句话就可以说明白的观点或者解决的的问题&#xff0c;小虎单独收集到这里。 Commits没有算入每天的activity fork的仓库是不算的。 Commits made in a fork will not count toward your contributions. 参考&#xff1a; Contribution activity not shown for github…

鸿蒙HarmonyOS开发:如何使用第三方库,加速应用开发

文章目录 一、如何安装 ohpm-cli二、如何安装三方库1、在 oh-package.json5 文件中声明三方库&#xff0c;以 ohos/crypto-js 为例&#xff1a;2、安装指定名称 pacakge_name 的三方库&#xff0c;执行以下命令&#xff0c;将自动在当前目录下的 oh-package.json5 文件中自动添…

C# 中引用类型的探讨

引用类型的变量不直接包含其数据&#xff1b;它包含对其数据的引用。 如果按值传递引用类型参数&#xff0c;则可能更改属于所引 用对象的数据&#xff0c;例如类成员的值。 但是&#xff0c;不能更改引用本身的值&#xff1b;例如&#xff0c;不能使用相同引用为新对象分配内存…

QuanTide-weekly第1期

本周Po文 这周我们共发表5篇文章。《基于 XGBoost 的组合策略…》等两篇详细讲解了机器学习构建组合策略的框架和常见问题。 文章要点与结论&#xff1a; 通过两阶段式方案实现多因子、多资产的组合策略构建。第一阶段基于XGBoost构建多个多因子单标的模型&#xff0c;第二阶…

electron-updater实现electron全量更新和增量更新——渲染进程交互部分

同学们可以私信我加入学习群&#xff01; 正文开始 前言更新功能所有文章汇总一、监听页面渲染完毕1.1 myApi.handleCheckPcUpdate检查更新1.2myApi.onPcUpdateProgress接收下载信息1.3myApi.onPcDownloaded监听下载完毕事件 二、立即更新三、跳过更新四、打开更新模块总结 前言…

vtkConnectivityFilter提取连通区域中的问题

直接使用vtkConnectivityFilter提取连通区域&#xff0c;渲染上没问题&#xff0c;但是打印出polydata中的点数&#xff0c;发现跟原始数据是一致的。 for (int i 0; i < numRegions; i){vtkSmartPointer<vtkConnectivityFilter> connectivityFilter vtkSmartPointe…

Unknown input format pdf Pandoc can convert to PDF, but not from PDF.解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…

口碑好的可视耳勺:四款口碑超好产品种草分享

随着科技的进步&#xff0c;越来越多人使用可视耳勺&#xff0c;因为它能够清晰地看到耳道内的状况&#xff0c;从而实现更精准、更安全的清洁。 然而&#xff0c;如今可视耳勺市场产品参差不齐&#xff0c;产品的评价褒贬参半。有的产品声称有超高像素&#xff0c;可实际到手画…