五种最短路算思路及其代码实现【全】_最短路算法实现-程序员宅基地

技术标签: 算法  个人总结  队列  数据结构  

刚看完Acwing上面y总的最短路视频,过来写一篇博客总结一下,也希望能帮助到别人
首先安利一波这个网站,里面有很多视频题解,算法模板,还能进行匹配对战
AcWing
AcWing
AcWing

先上一张图,刚用这个画图软件,可能画的比较拙劣
在这里插入图片描述
根据图片我们可以知道,最短路问题分为单源最短路和多源最短路。
单源最短路:只有一个出发点。求出来的应该是一个一维数组,保存该点到各点最短距离
多源最短路:有多个出发点,那么求出来应该是一个二维数组,每行表示一个上面的一维数组。

Flyod

首先说一下多源最短路把。Floyd算是这几个算法里面最简单无脑的方法了,就是三重循环,暴力遍历所有的点。它的实现思想:从任意节点i到任意节点j的最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j。所以,算法假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点k,算法检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从i到k再到j的路径比i直接到j的路径短,便设置Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当遍历完所有节点k,Dis(i,j)中记录的便是i到j的最短路径的距离。

下面上这个算法实现的一个基本模板,具体代码要根据具体问题进行更改

 for(int k=1;k<=n;k++){//代表中转顶点从1到n
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(dis[i][j]>dis[i][k]+dis[k][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];

Dijkstra

这个算法应该是大部分人刚接触最短路时最先学到的算法。Dijkstra其实是基于贪心的思想,采用了广度优先搜索的策略,以起始点为中心向外层层扩展,直到扩展到终点为止。。

原理:
设G=(V,E)是一个带权有向图,把图中顶点集合V分为两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),
第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径的的递增次序依次把第二组中的顶点加入S中。在加入的过程中,总保持从源点v到S中各个顶点的最短路径长度不大于从源点v到U中任何路径的长度。
此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前路径的最短长度。
然后下面提供一个比较好用的模板:

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int dist[N],g[N][N],n,m;
bool st[N];
int dijkstra()
{
    
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	for(int i=0;i<n-1;i++)
	{
    
		int t=-1;
		for(int j=1;j<=n;j++)
			if(!st[j]&&(t==-1||dist[j]<dist[t]))
				t=j;
		st[t]=true;
		for(int j=1;j<=n;j++)
			dist[j]=min(dist[j],dist[t]+g[t][j]);
	}
	if(dist[n]==0x3f3f3f3f)	return -1;
	return dist[n];
}
int main()
{
    
	memset(g,0x3f,sizeof g);
	cin>>n>>m;
	while(m--)
	{
    
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c);
	}
	cout<<dijkstra();
}

优化版的Dijkstra

优化原理:
优化Dijkstra有两个版本,一个是用优先队列优化,一个是用堆来进行优化。首先我们要分析哪里需要优化,为什么这样优化?
先回答第一个问题:从上面Dijkstra的原理和代码我们可以看出来。我们每次在找最近的点的时候(就是代码中每次给t赋值的这个过程)上面这个过程的代码是O(n^2)的,那么我们可以考虑用一种存储形式,让他每次直接返回一个最小的,就达成了优化。
然后第二个问题:小根堆和优先队列(设置出队顺序)正好符合这个要求。
优化代码:

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+10;
int n,m,h[N],w[N],e[N],ne[N],idx,dist[N];
bool st[N];
void add(int a,int b,int c)
{
    
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int dijkstra()
{
    
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	priority_queue<PII,vector<PII>,greater<PII>>heap;
	heap.push({
    0,1});
	while(heap.size())
	{
    
		auto t=heap.top();
		heap.pop();
		int ver=t.second,distance=t.first;
		if(st[ver])	continue;
		st[ver]=true;
		for(int i=h[ver];i!=-1;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[n]==0x3f3f3f)	return -1;
	return dist[n];
}
int main()
{
    
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--)
	{
    
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	cout<<dijkstra()<<endl;
}

Bellman-Ford

这个算法应该算是除了Flyod之外最简单且最容易理解的算法了。
Bellman-Ford算法的优点是可以发现负圈,缺点是时间复杂度比Dijkstra算法高。

算法流程:
(1)初始化:将除起点s外所有顶点的距离数组置无穷大 d[v] = INF, d[s] = 0
(2)迭代:遍历图中的每条边,对边的两个顶点分别进行一次松弛操作,直到没有点能被再次松弛
(3)判断负圈:如果迭代超过V-1次,则存在负圈

根据上面这个流程可以知道,我们只需要把输入数据按边存储,然后依次遍历完就ok了,算是一个比较傻的算法,这里就不多做解释了。
然后这个算法因为是按边进行处理的,所以有一个优势,就是当题目限制了最短路能有几条边的时候,只有这个算法可以使用。下面我们上一道例题 题目代码来源AcWing 853. 有边数限制的最短路
在这里插入图片描述
代码如下:

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, M = 10010;

struct Edge
{
    
    int a, b, c;
}edges[M];

int n, m, k;
int dist[N];
int last[N];

void bellman_ford()
{
    
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    for (int i = 0; i < k; i ++ )
    {
    
        memcpy(last, dist, sizeof dist);
        for (int j = 0; j < m; j ++ )
        {
    
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
}

int main()
{
    
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 0; i < m; i ++ )
    {
    
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {
    a, b, c};
    }

    bellman_ford();

    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else printf("%d\n", dist[n]);

    return 0;
}

作者:yxc
链接:https://www.acwing.com/activity/content/code/content/48523/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

SPFA

SPFA算法就是用优先队列优化后的Bellman—Ford算法,所以原理我们就不在赘述了。
这个算法算是使用最为普遍的,很多问题不管是正权图还是带负权图,都可以用SPFA算法。
优化原理:
Bellman—Ford算法的时间复杂度比较高,原因在于Bellman—Ford算法要递推n次,每次递推,扫描所有的边,在递推n次的过程中很多判断是多余的,SPFA算法是Bellman—Ford算法的一种队列实现,减少了不必要的冗余判断。
大致流程:
用一个队列来进行维护。初始时将源点加入队列。每次从队列中取出一个顶点,并与所有与它相邻的顶点进行松弛,若某个相邻的顶点松弛成功,则将其入队。重复这样的过程直到队列为空时算法结束。
代码模板:

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[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);
    st[1] = true;

    while (q.size())
    {
    
        int t = q.front();
        q.pop();

        st[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];
                if (!st[j])
                {
    
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

int 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\n", t);

    return 0;
}

作者:yxc
链接:https://www.acwing.com/activity/content/code/content/48498/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_44622401/article/details/104466457

智能推荐

概率论总结_p(∪n i=1ai) ≤ pn i=1 p(ai)-程序员宅基地

文章浏览阅读823次,点赞2次,收藏13次。随机事件与概率基本概念随机试验试验可以在相同的条件下重复进行试验所有可能结果是明确可知道的,并且不止一个每一次试验会出现哪一个结果,事先并不确定事件随机事件A,B,C...A,B,C...A,B,C...必然事件Ω\OmegaΩ不可能事件∅\varnothing∅样本空间样本点:随机试验的每一个可能结果称为样本点,记为ω\omegaω样本空间:样本点的全体组成的集合称为样本空间,记为Ω\OmegaΩ基本事件:由一个样本点构成的事件称为基本事件随机事件AAA是由若干个基本_p(∪n i=1ai) ≤ pn i=1 p(ai)

Nuxt中使用Vuex(新版,简单入门)_nuxt vuex-程序员宅基地

文章浏览阅读8.5k次,点赞2次,收藏17次。1.前言因为我学的是后端开发,前端不是很厉害,如果有什么不对的地方请评论指出,谢谢!看这篇文章你需要对Vuex有一定的了解 官方链接做课设的时候使用到了Nuxt框架,需要做登录,也就结识了Vuex,其实以前就学过Vuex,但是一直不知道这个东西有什么优势,特点。这次我在实际使用中就用到了一个非常好用的特点,官方的解释如下:Vuex 的状态存储是响应式的。当 Vue 组件从 store ..._nuxt vuex

vue点击按钮改变按钮样式_vue点击按钮切换样式-程序员宅基地

文章浏览阅读3.7k次。【代码】vue点击按钮改变按钮样式。_vue点击按钮切换样式

图论学习-最短路模型-程序员宅基地

文章浏览阅读2k次,点赞20次,收藏44次。这里只是我对于最短路模型学习的一个记录,不正确的地方希望大家指出。文章目录最短路模型一、 什么是最短路?1.1 概念1.2 基本术语二、主要模型2.1 dijkstra2.1.1 步骤2.1.2 画图理解2.1.3 为什么dijkstra不能处理负权边?2.2 堆优化的dijkstra2.3 bellman_ford2.3.1 三角形不等式2.3.2 步骤2.3.3 代码实现2.4 spfa2.4.1 步骤2.4.2 代码实现2.4.3 主要问题2.5 floyd三、练习题目四、参考最短路模型一、 什_最短路模型

20210409因为内存条的兼容问题引起的编译aosp10莫名的异常_aosp 编译 segmentation fault-程序员宅基地

文章浏览阅读2.7k次。20210409因为内存条的兼容问题引起的编译aosp10莫名的异常内存使用2条32GB的内存条(3000MHz)https://item.jd.com/10025021240070.html酷兽(CUSO)ddr4 32g台式机内存 32g 3000MHz 酷兽夜枭系列【京选存储.稳定兼容】酷兽存储.实惠装机能手(内存终身保固.以换代修)京 东 价¥ 769.00 降价通知32g 3000MHz电脑使用的:dell的Inspiron-3880rootroot@rootroot-Ins_aosp 编译 segmentation fault

SSL_1072&&P2347【砝码称重】-程序员宅基地

文章浏览阅读72次。砝码称重题目设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其总重<=1000),要求:输入方式:a1 a2 a3 a4 a5 a6(表示1g砝码有a1个,2g砝码有a2个,…,20g砝码有a6个)输出方式:N(N表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况)Sample Input1 1 0 0 0 0(注:下划线表示空格)Sample Output3//表示可以称出1g,2g,3g三种不同的重量。解析啊就这?!堂堂1996年分区联赛提高组第

随便推点

BZOJ 2301 [HAOI2011]Problem b(莫比乌斯反演)_[bzoj2301][haoi2011]-程序员宅基地

文章浏览阅读139次。题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2301咱也不知道莫比乌斯函数,莫比乌斯反演怎么来的,直接用就得了...①莫比乌斯函数:else表示质因子分解后有质因子出现一次以上莫比乌斯函数跟着欧拉筛跑一遍就可以求出来②莫比乌斯反演的两种写法:其中f(i)是题目询问的东西,你发现直接求求..._[bzoj2301][haoi2011]

SpringBoot多文件压缩包下载(多附件zip格式)_springboot下载多个文件-程序员宅基地

文章浏览阅读7.4k次。文章目录前言 : 此 Demo 为 Windows 环境下演示,部署到服务器的话路径需改成服务器的路径。一、自定义工具类DownLoadZipUtil二、Dao层分析与sqlmapper层代码(DAO)三、Service层代码三、Controller层代码注意 : 文件的打包下载这里用到了临时路径,下面只需要关注方法ZipTempDownLoad即可,下面的代码实际需根据自己的逻辑需求去写。四、前端部分代码,此Demo前端用的vue五、效果展示前言 : 此 Demo 为 Windows 环境下演示,部_springboot下载多个文件

meta SEO(给搜索引擎看的meta标签 name keywords)_搜索 <meta name="keywords" content="氢能源、燃料、电池技术、清洁能源-程序员宅基地

文章浏览阅读1.8k次。<!-- 你挂载到域名上才有用 --> <meta name="keywords" content="游戏,音乐,体育">_搜索

CVPR2019 主动学习方面论文_cvpr 2019 active learning-程序员宅基地

文章浏览阅读498次。1 Learning Loss for Active Learning 论文下载直接预测样本的LossCVPR2019 论文接受列表_cvpr 2019 active learning

通信原理chapter2总结(内含多径效应和多普勒效应MATLAB仿真)_多普勒效应和多径效应 建模-程序员宅基地

文章浏览阅读4.8k次,点赞12次,收藏67次。第二章总结1.信道:通信系统中信道是指发送设备到接收设备之间信号传输的通道,是通信系统中的一个重要组成部分。2.分类:1)按照传输媒介:无线信道和有线信道;2)根据信道研究对象不同:调制信道,编码信道3)按照信道的冲激响应是否随时间变化:恒参信道,随参信道4)按照信道输入和输出符号是否离散:离散信道,连续信道3. 简介1)有线信道:利用人造的传导电或光信号的媒质来传输信号,如明线,..._多普勒效应和多径效应 建模

富士通01018z平板电脑评测_微软Surface Pro 7详细评测:仍旧是最好的二合一平板电脑...-程序员宅基地

文章浏览阅读1k次。今年10月初,当人们还沉浸在国庆放假的喜悦中的时候,大洋彼岸的微软在纽约召开新品发布会,一口气发布了6款Surface设备,除了惊艳的双屏电脑Surface Neo以及传说中的“Surface Phone”以不一样的形态和消费者见面之外,升级版的微软Surface Pro 7也是本次发布会的最大看点之一,微软Surface Pro 7跟着英特尔的节奏升级到了10代酷睿处理器,另外的一个看点则是增加..._farq01018z

推荐文章

热门文章

相关标签