图论:最短路(dijkstra算法、bellman算法、spfa算法、floyd算法)详细版

终于是学完了,这个最短路我学了好几天,当然也学了别的算法啦,也是非常的累啊。

话不多说下面看看最短路问题吧。

最短路问题是有向图,要求的是图中一个点到起点的距离,其中我们要输入点和点之间的距离,来求最短路。

下面分为几类题目:

单源汇最短路-->一个起点

1.边权为正数(dijkstra)

dijkstra算法的原理其实是拿第一个点与相连接的点进行距离上的比较,让距离最近的点作为下一个比较的第一个点,由于是边权为正数,所以不用去考虑负数和负环路。但是为啥我要分为两种类型,不是因为优化就是比朴素好,因为他们的存储数据不同,要存储的方式也是不同的,所以方法也是不同的。

方法:

dis[1]=0,dis[i]=0x3f正无穷
for(int i=1~n) 当前已经确定最短距离的点(当然用邻接表存储的for(int i=h[st];i!=-1;i=ne[i]))
t<-不在s中的距离最近的点
s<-t
用t更新其他点的距离

(1)朴素 O(n^2) n点数m边数-->边数较多-->稠密图-->邻接矩阵


看题:

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 −1。

数据范围

1≤n≤500,
1≤m≤10^5,
图中涉及边长均不超过10000。

看这个

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

代码实现:

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m;
int g[N][N];
int dis[N];
bool st[N];
int Dijkstra(){
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++)//j-x当前的点
            if(!st[j]&&(t==-1||dis[t]>dis[j]))
               t=j;
            // if(t==n)break;
            st[t]=true;
        for(int j=1;j<=n;j++)
            dis[j]=min(dis[j],dis[t]+g[t][j]);
    }
    if(dis[n]==0x3f3f3f3f)return -1;
    return dis[n];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c);
    } 
    cout<<Dijkstra()<<endl;
}
(2)堆优化版 O(mlogn)-->边少-->稀疏图-->邻接表

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 −1。

数据范围

1≤n,m≤1.5×10^5,
图中涉及边长均不小于 0,且不超过 10000。
数据保证:如果最短路存在,则最短路的长度不超过 10^9。

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

代码实现(因为是队列嘛,咱们也可以使用模拟队列):

#include<bits/stdc++.h>
#include<cstring>//memset函数的头文件
#include<iostream>
#include<algorithm>
#include<queue>
#define xx first 
#define yy second
using namespace std;
const int N = 150010;
typedef pair<int, int>PII;//前者是距离 堆中按照前者距离排序 后者是点序号
priority_queue<PII, vector<PII>, greater<PII>>heap;//小根堆
int h[N], w[N], e[N], ne[N], idx;//稀疏图用邻接表储存 w[N]存权重
int dist[N];//起点点到终点的(当前)最短距离
bool vis[N];//标记起点到某个点的最短距离是否确定
int st,ed;//起点到终点
int n, m;
//数组模拟邻接表的插入函数
void add(int a, int b, int c){//存在一条从点a到点b的有向边 距离为c
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int Dijkstra(int st, int ed){
    //初始设定起点点到其他所有点距离为正无穷
    memset(dist, 0x3f, sizeof dist);
    //起点到起点距离为0 加入堆
    dist[st] = 0;
    //第一参数是距离
    //第二参数是终点编号
    heap.push({ 0,st });
    while (heap.size()){
        auto t = heap.top();
        heap.pop();//取出后一定要弹出
        int ver = t.yy, distance = t.xx;//ver取得该点的下标
        if (vis[ver])continue;//已经确定了就跳过
        //要做就先确定下来
        //出队时确定加入S集合
        vis[ver] = true;
        //把确定下来的那个点能拓展到的新点 加入堆
        for (int i = h[ver];~i;i = ne[i]){
            int j = e[i];
            if (dist[j] > distance + w[i]){
                dist[j] = distance + w[i];
                heap.push({ dist[j],j });
            }
        }
    }
    if (dist[ed] == 0x3f3f3f3f)return -1;//不连通
    return dist[ed];
}
int main(){
    memset(h, -1, sizeof h);//初始化邻接表表头
    scanf("%d%d", &n, &m);
    while (m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    printf("%d\n", Dijkstra(1, n));
}
2.存在负边权

贝尔曼的原理嘛,是一个叫做三角不等式的松弛操作实现的,但是由于是双重循环把所有的边都遍历了一遍,所以时间复杂度为O(nm),而相对于下面的SPFA算法嘛,一般都比较常用spfa。

(1)Bellman-ford O(nm)

你看这个可以在1->2->3->4->2走无穷次,导致最终结果为负无穷 

但是他可以走有限条边,即使是万能的spfa也不行,因为这就是遍历的一步。

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible

注意:图中可能 存在负权回路 。

输入格式

第一行包含三个整数 n,m,k。

接下来 m 行,每行包含三个整数x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

点的编号为 1∼n。

输出格式

输出一个整数,表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径,则输出 impossible

数据范围

1≤n,k≤500,
1≤m≤10000,
1≤x,y≤n,
任意边长的绝对值不超过 10000。

输入样例:
3 3 1
1 2 1
2 3 1
1 3 3
输出样例:
3

代码实现:

#include<bits/stdc++.h>
#include<cstring>
#include<iomanip>
#include<iostream>
using namespace std;
const int N=510,M=1e4+10;
int n,m,k;
int dis[N],backup[N];
struct tu
{
    int a,b,w;
}edge[M];
void Bellman_ford(){
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    for(int i=0;i<k;i++){
        memcpy(backup,dis,sizeof dis);
        for(int j=0;j<m;j++){
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            dis[b]=min(dis[b],backup[a]+w);
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++){
        int a,b,w;
        cin>>a>>b>>w;
        // edge[i].a=a,edge[i].b=b,edge[i].w=w;
        edge[i]={a,b,w};
    }
    Bellman_ford();
    if(dis[n]>0x3f3f3f3f/2)cout<<"impossible";
    else cout<<dis[n];
}
(2)SPFA O(m),最坏O(nm)-->贪心

前提是:

不含负环,但是同样适用于dijkstra题目

这个算法虽然不能适用于求负环的最短路,但是他可以判断是不是含有负环,详细看注释掉的部分。

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出 impossible

数据范围

1≤n,m≤10^5,
图中涉及边长绝对值均不超过 10000。

输入样例:
3 3
1 2 5
2 3 -3
1 3 4
输出样例:
2

 代码实现:

#include<cstring>//memset函数的头文件
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100010;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool vis[N];
int n, m;
// int cnt[N];
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    queue<int> q;
    q.push(1);
    vis[1]=true;

    while(q.size()){
       int t=q.front();
       q.pop();
       vis[t]=false;
       for(int i=h[t];i!=-1;i=ne[i]){
          int j=e[i];
          if(dist[j]>dist[t]+w[i]){
            dist[j]=dist[t]+w[i];
            // cnt[j]=cnt[t]+1;
            // if(cnt[j]>=n)return true;//判断是不是存在负环
            if(!vis[j]){
                q.push(j);
                vis[j]=true;
            }
          }
       }
    }
    return dist[n];
    // return false;
}
signed main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while(m -- ){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int t=spfa();
    if(t==0x3f3f3f3f) puts("impossible");
    else printf("%d",t);
    // if(spfa())puts("Yes");
    // else puts("No");
}

多源汇最短路 Floyd O(n^3)-->dp

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,边权可能为负数。

再给定 k 个询问,每个询问包含两个整数 x 和 y,表示查询从点 x 到点 y 的最短距离,如果路径不存在,则输出 impossible

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 n,m,k。

接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

接下来 k 行,每行包含两个整数 x,y,表示询问点 x 到点 y 的最短距离。

输出格式

共 k 行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出 impossible

数据范围

1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。

输入样例:
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例:
impossible
1

 代码实现:

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=200+10,INF=1e9;
int m,n,Q;
int d[N][N];
void floyd(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
}

signed main(){
    scanf("%d%d%d",&n,&m,&Q);
    //init
    for(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;
    //input
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        d[a][b]=min(d[a][b],c);
    }
    floyd();
    while(Q--){
        int a,b;
        scanf("%d%d",&a,&b);
        if(d[a][b]>INF/2)
        puts("impossible");
        else
        printf("%d",d[a][b]);
    } 
}

以上就是求最短路的所有方法啦。

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

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

相关文章

【EFCore仓储模式】介绍一个EFCore的Repository实现

阅读本文你的收获 了解仓储模式及泛型仓储的优点学会封装泛型仓储的一般设计思路学习在ASP.NET Core WebAPI项目中使用EntityFrameworkCore.Data.Repository 本文中的案例是微软EntityFrameworkCore的一个仓储模式实现&#xff0c;这个仓储库不是我自己写的&#xff0c;而是使…

Eyes Wide Shut? Exploring the Visual Shortcomings of Multimodal LLMs

大开眼界&#xff1f;探索多模态模型种视觉编码器的缺陷。 论文中指出&#xff0c;上面这些VQA问题&#xff0c;人类可以瞬间给出正确的答案&#xff0c;但是多模态给出的结果却是错误的。是哪个环节出了问题呢&#xff1f;视觉编码器的问题&#xff1f;大语言模型出现了幻觉&…

章鱼网络 Community Call #17|打造全新 Omnity 跨链协议

香港时间2024年1月8日12点&#xff0c;章鱼网络举行第17期 Community Call。 对于 Octopus Community 而言&#xff0c;2023年是一个分水岭。我们如期兑现我们的承诺&#xff0c;成功上线了包括 $NEAR Restaking 和 Adaptive IBC 在内的完整的 Octopus 2.0。 自从我们在2023年…

HarmonyOS 应用开发入门

HarmonyOS 应用开发入门 前言 DevEco Studio Release版本为&#xff1a;DevEco Studio 3.1.1。 Compile SDK Release版本为&#xff1a;3.1.0&#xff08;API 9&#xff09;。 构建方式为 HVigor&#xff0c;而非 Gradle。 最新版本已不再支持 &#xff08;”Java、JavaScrip…

Leetcode的AC指南 —— 栈与队列:225.用队列实现栈

摘要&#xff1a; **Leetcode的AC指南 —— 栈与队列&#xff1a;225.用队列实现栈 **。题目介绍&#xff1a;请你仅使用两个队列实现一个后入先出&#xff08;LIFO&#xff09;的栈&#xff0c;并支持普通栈的全部四种操作&#xff08;push、top、pop 和 empty&#xff09;。 …

web渗透安全学习笔记:2、HTML基础知识

目录 前言 HTML的标题 段落链接与插入图片 HTML元素 HTML属性 HTML头部 HTML与CSS HTML与JavaScript 表格与列表 HTML区块 布局 HTML表单 HTML与数据库 音频与视频 HTML事件 前言 HTML的标题 <!DOCTYPE html> <html> <head> <meta chars…

Spring+SprinMVC+MyBatis注解方式简易模板

SpringSprinMVCMyBatis注解方式简易模板代码Demo GitHub访问 ssm-tpl-anno 一、数据准备 创建数据库test&#xff0c;执行下方SQL创建表ssm-tpl-cfg /*Navicat Premium Data TransferSource Server : 127.0.0.1Source Server Type : MySQLSource Server Version :…

HCIP-BGP实验3

实验步骤 配置IP地址 R1 [r1]int g0/0/0 [r1-GigabitEthernet0/0/0]ip add 12.1.1.1 24 [r1-GigabitEthernet0/0/0]int loopback0 [r1-LoopBack0]ip add 192.168.1.1 24 [r1-LoopBack0]int loopback1 [r1-LoopBack1]ip add 192.168.2.1 24 [r1-LoopBack1]int loopback3 [r1-…

OCS2 入门教程(六)- Double Integrator

系列文章目录 前言 双积分器示例是我们最简单的问题。它模拟了一个沿 x 方向移动的一维点质量。模型是线性的&#xff0c;成本函数是二次函数。目标点通过参考管理器模块设置为二次成本。 一、查看文件结构 1.1 ocs2_double_integrator 文件夹 . ├── auto_generated ├─…

LSTM时间序列预测

本文借鉴了数学建模清风老师的课件与思路&#xff0c;可以点击查看链接查看清风老师视频讲解&#xff1a;【1】演示&#xff1a;基于LSTM深度学习网络预测时间序列&#xff08;MATLAB工具箱&#xff09;_哔哩哔哩_bilibili % Forecast of time series based on LSTM deep learn…

Pyro —— Velocity Voxel Scale

Velocity Voxel Scale是H19.5引入的新参数&#xff0c;该参数可单独定义volume和速度体素&#xff1b;根据参数设置&#xff0c;可观察到模拟时间的显著变化&#xff1b; Velocity Voxel Scale对DOP和SOP均可用&#xff1b;对DOP设置&#xff0c;该参数在Smoke Object&#xf…

Java安全 CC链1分析

Java安全之CC链1分析 什么是CC链环境搭建jdk下载idea配置创建项目 前置知识Transformer接口ConstantTransformer类invokerTransformer类ChainedTransformer类 构造CC链1CC链1核心demo1demo1分析 寻找如何触发CC链1核心TransformedMap类AbstractInputCheckedMapDecorator类readO…

RT-Thread 瑞萨 智能家居网络开发:RA6M3 HMI Board 以太网+GUI技术实践

不用放大了&#xff0c; 我在包里找到张不小的…… 以太网HMI线下培训-环境准备 这是社群的文档&#xff1a;【腾讯文档】以太网线下培训&#xff08;HMI-Board&#xff09; https://docs.qq.com/doc/DY0FIWFVuTEpORlNn 先介绍周六的培训是啥&#xff0c;然后再介绍一下要准…

赛车游戏简单单车C语言版

#include<stdio.h> #include<easyx.h> #include<time.h>#define WIDTH 512 #define HEIGHT 768//定义一个汽车类 struct FCar {//坐标float x, y;// 汽车种类int type;//汽车速度float speed; };//定义全局变量 图片坐标 IMAGE BG_IMG; //背景图片坐标 float…

[小程序]使用代码渲染页面

一、条件渲染 1.单个控制 使用wx:if"{{条件}}"来判断是否需要渲染这段代码&#xff0c;同时可以结合wx:elif和wx:else来判断 <view wx:if"{{type0}}">0</view> <view wx:elif"{{type1}}">1</view> <view wx:else>…

linux网络协议栈2--网络包接收发送流程

上文我们讲了报文格式&#xff0c;应该对数据传输格式有了一定了解&#xff0c;这篇文章主要讲述的是网络包接收和发送的流程&#xff0c;主要是大方面来介绍。 网络包接收流程 当网络数据帧通过网络传输到达网卡时&#xff0c;网卡会将网络数据帧通过DMA的方式放到环形缓冲区…

nginx日志分割

日志切割是线上常见的操作&#xff0c;能够控制单个日志文件的大小&#xff0c;便于对日志进行管理 给nginx主进程发送一个重新打开的信号&#xff0c;让nginx重新生成新的日志文件 nginx -s reopen 这个命令等同于kill -USR1 cat nginx.pid 切割日志文件shell命令 #!/bin/bas…

Flink处理函数(3)—— 窗口处理函数

窗口处理函数包括&#xff1a;ProcessWindowFunction 和 ProcessAllWindowFunction 基础用法 stream.keyBy( t -> t.f0 ).window( TumblingEventTimeWindows.of(Time.seconds(10)) ).process(new MyProcessWindowFunction()) 这里的MyProcessWindowFunction就是ProcessWi…

rk1126, 实现 yolov8 目标检测

基于 RKNN 1126 实现 yolov8 目标检测 Ⓜ️ RKNN 模型转换 ONNX yolo export model./weights/yolov8s.pt formatonnx导出 RKNN 这里选择输出 concat 输入两个节点 onnx::Concat_425 和 onnx::Concat_426 from rknn.api import RKNNONNX_MODEL ./weights/yolov8s.onnxRKNN_MOD…

C语言练习day8

变种水仙花 变种水仙花_牛客题霸_牛客网 题目&#xff1a; 思路&#xff1a;我们拿到题目的第一步可以先看一看题目给的例子&#xff0c;1461这个数被从中间拆成了两部分&#xff1a;1和461&#xff0c;14和61&#xff0c;146和1&#xff0c;不知道看到这大家有没有觉得很熟…