当前位置： 首页 > news >正文

Dijkstra与Floyd求最短路算法简介

news 2025/8/16 5:26:37

文章目录

  • 前言
  • 1.Dijkstra（用于计算单源、正权边的最短路问题）
    • 大致讲解
  • 例题：
    • 1.P3371 【模板】单源最短路径（弱化版）
    • 2.P4779 【模板】单源最短路径（标准版）
    • 3.P1339 [USACO09OCT] Heat Wave G
    • 4.P2984 [USACO10FEB] Chocolate Giving S
    • 5.小美想游泳
  • 2.Floyd（Floyd-Warshall 是多源最短路径算法，支持正边权和负边权（无负权回路时））
    • 大致讲解
  • 例题
    • 1.B3647 【模板】Floyd
    • 2.[USACO07NOV] Cow Hurdles S
  • 总结

前言

求最短路问题很常见，有的是让求一个图中两个点的最短距离或者是求某一点到另外一点的最小代价，总之学会求最短路是很重要的

1.Dijkstra（用于计算单源、正权边的最短路问题）

大致讲解

Dijkstra 算法是一种用于求解带非负权值边的图中，单源最短路径的经典贪心算法。它的核心思想是：从起点出发，每次轮选择当前距离起点最近的未确定节点，以此为中间点更新其他节点的距离，直到所有节点的最短路径都被确定。

其实Dijkstra算法就是利用贪心算法来进行操作的，不断找与自己相连接的点，并遍历这些点中与自己相邻最近的点，一直遍历到最后。
过程：
1.每次从未标记的节点中选择距离出发点最近的节点，标记，收录到最优路径集合中

2.计算刚加入节点A的邻近节点B的距离（不包含标记的节点），若（节点A的距离+节点A到B的边长）<节点B的距离，就跟新节点B的距离与前面点
例子：
给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 u,v,w，表示一条 u→v 的，长度为 w 的边。

输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=2e5+5;
vector<pii>ve[N];  // 邻接表：ve[u]存储u的所有出边，每个元素是(v, w)表示u→v的边权为w
bool vis[N]; // 标记节点是否已确定最短路径
int d[N]; // 存储起点到各节点的最短距离
const int INF =1e18;
signed main()
{int n,m,s;cin>>n>>m>>s;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;ve[u].push_back({v,w});//由于是有向边，所以单向建//ve[v].push_back({u,w});如果要双向建，就加上这个}// 优先队列（小根堆）：为了快速获取距离最小的节点priority_queue<pii,vector<pii>,greater<pii>>pq;pq.push({0,s});for(int i=1;i<=n;i++){d[i]=INF;//先把距离赋值为不可达，就是非常大，为了后面比较大小}d[s]=0;//起始点到自己距离为0while(!pq.empty()){pii x=pq.top(); // 取距离最小的节点pq.pop();if(vis[x.se])//如果已经被标记过就直接跳过，说明已经遍历过这个点{continue;}vis[x.se]=1;//标记为遍历过for(auto it:ve[x.se])//遍历其子节点{if(!vis[it.fi]&&it.se+x.fi<d[it.fi])//得到最小距离{d[it.fi]=it.se+x.fi;// 更新v的最短距离pq.push({d[it.fi],it.fi});}//         下面这个看起来更直观//         int v = it.fi, w = it.se;//         if(!vis[v] && d[v] > d[u] + w)//         {//         d[v] = d[u] + w;//         pq.push({d[v], v});//         }}}for(int i=1;i<=n;i++){if(vis[i])//可达cout<<d[i]<<" ";else//不可达cout<<"2147483647"<<" ";}return 0;
}

例题：

1.P3371 【模板】单源最短路径（弱化版）

P3371 【模板】单源最短路径（弱化版）
上面的讲解代码就是这个题的AC代码

2.P4779 【模板】单源最短路径（标准版）

P4779 【模板】单源最短路径（标准版）
这题与上面题类似，代码稍微修改一下就行了，不再过多叙述

3.P1339 [USACO09OCT] Heat Wave G

P1339 [USACO09OCT] Heat Wave G
在这里插入图片描述
依旧类似于模板

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=1e4;
const int INF=0x3f3f3f3f;
int a[N];
bool vis[N];
vector<pii>ve[N];
signed main()
{IOS;int n,m,s,t;cin>>n>>m>>s>>t;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;ve[u].push_back({v,w});ve[v].push_back({u,w});}for(int i=1;i<=n;i++){a[i]=INF;}a[s]=0;priority_queue<pii,vector<pii>,greater<pii>>pq;pq.push({0,s});//入的是要求的点while(!pq.empty()){pii x=pq.top();pq.pop();if(vis[x.se]){continue;}vis[x.se]=1;for(auto it:ve[x.se]){if(!vis[it.fi]&&it.se+x.fi<a[it.fi]){a[it.fi]=it.se+x.fi;pq.push({a[it.fi],it.fi});}}}cout<<a[t];return 0;}

4.P2984 [USACO10FEB] Chocolate Giving S

P2984 [USACO10FEB] Chocolate Giving S
在这里插入图片描述
这题第一眼可能觉得就是求两段最短路径，求两次就行了，但是这样会超时，从题目中可以发现无论怎么走都要经1点，所以直接求从1到另外两点的最短距离就行了。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=2e5+6;
const int INF=0x3f3f3f3f;
int a[N];
bool vis[N];
vector<pii>ve[N];
signed main()
{IOS;int n,m,b;cin>>n>>m>>b;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;ve[u].push_back({v,w});ve[v].push_back({u,w});}memset(a,INF,sizeof(a));memset(vis,0,sizeof(vis));a[1]=0;priority_queue<pii,vector<pii>,greater<pii>>pq;pq.push({0,1});while(!pq.empty()){pii x=pq.top();pq.pop();if(vis[x.se]){continue;}vis[x.se]=1;for(auto it:ve[x.se]){if(!vis[it.fi]&&it.se+x.fi<a[it.fi]){a[it.fi]=it.se+x.fi;pq.push({a[it.fi],it.fi});}}}while(b--){int s,t;cin>>s>>t;cout<<a[s]+a[t]<<endl;//最后相加就行了}return 0;}

5.小美想游泳

小美想游泳
在这里插入图片描述
这个题实际上就是就最小瓶颈路径，即路径中边权最大值最小的路径
我们依旧可以用Dijkstra写，再定义一个数组代表从起始点到该点的路上的最大距离，在不断向最近的点延伸时，比较出最大值，遍历完后输出就行了

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int N=2e5+6;
int d[N];
bool vis[N];
vector<pii>ve[N];
const int INF=1e18;
signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=m;i++){int u,v,a;cin>>u>>v>>a;ve[u].push_back({v,a});ve[v].push_back({u,a});}int s,t;cin>>s>>t;priority_queue<pii,vector<pii>,greater<pii>>pq;for(int i=1;i<=n;i++){d[i]=INF;}pq.push({0,s});d[s]=0;while(!pq.empty()){pii x=pq.top();pq.pop();if(vis[t]){cout<<d[t];//到了就直接退出break;}if(vis[x.se]){continue;}vis[x.se]=1;for(auto it:ve[x.se]){if(!vis[it.fi]&&d[it.fi]>max(it.se,x.fi)){d[it.fi]=max(it.se,x.fi);pq.push({d[it.fi],it.fi});}	}}return 0;
}

上面都是一些相对简单的题，都可以写

2.Floyd（Floyd-Warshall 是多源最短路径算法，支持正边权和负边权（无负权回路时））

大致讲解

Floyd 算法是一种动态规划思想的全源最短路径算法，能一次性求出图中所有顶点之间的最短路径长度，支持有向图和无向图（无向图可视为双向有向图），但不允许存在负权回路（会导致路径长度无限减小）。

就是通过逐步引入中间节点，更新任意两个节点之间的最短路径。

  1. 初始状态
    我们用一个n×n的矩阵dp表示节点间的距离，其中dp[i][j]表示从节点i到节点j的初始距离：

    • 若i == j（自身到自身），距离为0；
    • 若i和j直接相连，距离为边的权重；
    • 若i和j不直接相连，距离为一个极大值（表示不可达）。

  2. 逐步引入中间节点优化路径
    算法的关键是通过三重循环，依次将每个节点k作为中间节点，尝试优化所有节点对(i, j)的路径：

    • 对于每个中间节点k，检查是否存在一条路径i → k → j，其总距离比当前已知的i → j的距离更短；
    • 如果更短，则更新dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])。

    形象地说：“如果从i到k再到j比直接从i到j更近，就走这条新路径”。

  3. 最终结果
    当所有节点都被作为中间节点尝试过之后，dp[i][j]就存储了从i到j的最短路径距离。

例题：给出一张由 n 个点 m 条边组成的无向图。
​求出所有点对 (i,j) 之间的最短路径。

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
int dp[106][106];//表示顶点i到顶点j的最短路径长度
signed main()
{int n,m;cin>>n>>m;memset(dp,0x3f3f3f3f3f,sizeof(dp));for(int i=1;i<=n;i++){dp[i][i]=0;}for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;dp[u][v]=min(dp[u][v],w);dp[v][u]=min(dp[v][u],w);}for(int k=1;k<=n;k++)// 枚举中间顶点k{for(int i=1;i<=n;i++)//枚举起点i{for(int j=1;j<=n;j++)//枚举终点j{dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);//比较路径是否更短}}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<dp[i][j]<<" ";}cout<<endl;}return 0;
}

例题

1.B3647 【模板】Floyd

B3647 【模板】Floyd
就是一个简单的模板题

2.[USACO07NOV] Cow Hurdles S

[USACO07NOV] Cow Hurdles S
在这里插入图片描述
这题其实就类似于上面的小美想游泳，也是一个求最小瓶颈路径，即路径中边权最大值最小的路径
只不过用Dijkstra过不了，会时间超限，所以可以用Floyd

  • 状态定义：dp[i][j] 表示从节点i到节点j的最小瓶颈（即i→j所有路径中，边权最大值的最小值）。
  • 状态转移：对于中间节点k，i→j的路径可拆分为i→k→j。该拆分路径的瓶颈是 max(dp[i][k], dp[k][j])（i→k的最小瓶颈与k→j的最小瓶颈的最大值）。若此值比当前dp[i][j]更小，则更新dp[i][j]。
  • 初始状态
    • 若i == j（自身到自身）：dp[i][j] = 0（无路径，瓶颈为 0）。
    • 若i与j直接相连（边权为w）：dp[i][j] = w。
    • 若i与j不直接相连：dp[i][j] = INF（初始化为无穷大，代表不可达）
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
#define endl '\n'
const int INF = 0x3f3f3f3f3f3f3f3f;
const int N=1e3+6; // Floyd算法适合n较小的场景（n≤1e3）
int dp[N][N];
signed main()
{int n,m,q;cin>>n>>m>>q;memset(dp,INF,sizeof(dp));for(int i=1;i<=n;i++){dp[i][i]=0;}for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;dp[u][v]=min(dp[u][v],w);//初始化直接相连的节点的瓶颈// 若为无向图，需加 dp[v][u] = min(dp[v][u], w);}//Floyd核心：通过中间节点k松弛所有i→j的路径for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)// 若i→k和k→j均可达，且拆分路径的瓶颈更小，则更新{if(dp[i][k]!=INF&&dp[k][j]!=INF) dp[i][j]=min(dp[i][j],max(dp[i][k],dp[k][j]));}}}while(q--){int s,t;cin>>s>>t;if(dp[s][t]!=INF)cout<<dp[s][t]<<endl;//可达else cout<<"-1"<<endl;//不可达}return 0;
}

总结

以上仅是本人对Dijkstra与Floyd的理解，如果有错误，烦请指出

http://www.lryc.cn/news/621466.html

相关文章：

  • zabbix部署问题后常见问题
  • sqli-labs通关笔记-第50关 GET数值型order by堆叠注入(手工注入+脚本注入两种方法)
  • StringBoot-SSE和WebFlux方式消息实时推送-默认单向-可增加交互接口
  • qt项目中解决关闭弹窗后执行主界面的信号槽时闪退问题
  • c++中的Lambda表达式详解
  • ATAM：基于场景的软件架构权衡分析法
  • 使用Docker和Miniconda3搭建YOLOv13开发环境
  • 微服务架构概述
  • docker 容器管理入门教程
  • Docker network网络管理入门教程
  • JS 解构赋值语法
  • Vue浅学
  • 0814 TCP通信协议
  • 【C#补全计划】泛型约束
  • [TryHackMe](知识学习)---基于堆栈得到缓冲区溢出
  • Vue 3 + TypeScript：package.json 示例 / 详细注释说明
  • Apache 虚拟主机配置冲突导致 404 错误的排查总结
  • 通信算法之313：FPGA中实现滑动相关消耗DSP资源及7045/7035的乘法器资源
  • redis中分布式锁的应用
  • 面试题：如何用Flink实时计算QPS
  • 解锁AI潜能：五步写出让大模型神级指令
  • 宋红康 JVM 笔记 Day01｜JVM介绍
  • 嵌入式开发学习———Linux环境下网络编程学习（一）
  • 【数据分享】351个地级市农业相关数据（2013-2022）-有缺失值
  • 速通C++类型转换（代码+注释）
  • AI测试自动化：智能软件质量守护者
  • 带root权限_贝尔RG020ET-CA融合终端S905L处理器当贝纯净版刷机教程
  • ROS机器人云实践案例博客建议和范文-AI版本
  • DAY 22|算法篇——贪心四
  • linux初始化配置