【蓝桥杯--图论】Dijkstra、Ballman-Ford、Spfa、Floyd

这篇具有很好参考价值的文章主要介绍了【蓝桥杯--图论】Dijkstra、Ballman-Ford、Spfa、Floyd。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【蓝桥杯--图论】Dijkstra、Ballman-Ford、Spfa、Floyd,数据结构与算法,蓝桥杯,图论

【蓝桥杯--图论】Dijkstra、Ballman-Ford、Spfa、Floyd,数据结构与算法,蓝桥杯,图论

今日语录:每一次挑战都是一次成长的机会


【蓝桥杯--图论】Dijkstra、Ballman-Ford、Spfa、Floyd,数据结构与算法,蓝桥杯,图论
如上所示即为做题时应对的方法

朴素DIjkstra

引用与稠密图,即m<n^2

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510;

int n, m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    // 将距离初始化为无穷大
    dist[1] = 0;

    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                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()
{
    scanf(" % d % d", &n, &m);

    memset(g, 0x3f, sizeof g);

    while (m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }

    int t = dijkstra();
    
    printf("%d\n", t);
    return 0;
}

堆优化的Dijkstra

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

using namespace std;

typedef pair<int, int>PII;

const int N = 10010;

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 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;

        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] == 0x3f3f3f3f)return -1;
    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 = dijkstra();
    
    printf("%d\n", t);
    return 0;
}

Ballman-Ford

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

using namespace std;

const int N = 510,M = 10010;

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

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

int bellman_ford()
{

    memset(dist, 0x3f, sizeof dist);
    for (int i = 0; i < k; i++)
    {
        memcpy(backup, dist, sizeof dist);
        for (int j = 0; j < m; j++)
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2)return -1;
    return dist[n];
}

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

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

    int t = bellman_ford();

    if (t == -1)puts("impossible");
    else printf("%d\n", t);

    return 0;
}

Floyd

#include<iostream>
#include<cstring>
#include<algorithm>
#define _CRT_SECURE_NO_WARNINGS

using namespace std;
const int N = 210,INF = 1e9;

int n, m,Q;
int d[N][N];

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()
{
	scanf("%d%d%d", &n, &m, &Q);

	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;

	while (m--)
	{
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);

		d[a][b] = min(d[a][b], w);
	}

	floyd();
	while (Q--)
	{
		int a, b;
		scanf("%d%d", &a, &b);

		if (d[a][b] > INF / 2)puts("impossible");
		else printf("%d\n", d[a][b]);
	}
	return 0;
}

Spfa(求最短路)

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

using namespace std;

typedef pair<int, int>PII;

const int N = 10010;

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;
                }
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f)return -1;
    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();

    printf("%d\n", t);
    return 0;
}

Spfa(求是否含有负权)

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

using namespace std;
typedef pair<int, int>PII;
const int N = 10010;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N],cnt[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()
{
    queue<int>q;
    for (int i = 1; i <= n; i++)
    {
        st[i] = true;
        q.push(i);
    }

    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];

                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n)return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

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);
    }

    if (spfa())puts("Yes");
    else puts("No");
    return 0;
}

【蓝桥杯--图论】Dijkstra、Ballman-Ford、Spfa、Floyd,数据结构与算法,蓝桥杯,图论文章来源地址https://www.toymoban.com/news/detail-817548.html

到了这里,关于【蓝桥杯--图论】Dijkstra、Ballman-Ford、Spfa、Floyd的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

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

    终于是学完了,这个最短路我学了好几天,当然也学了别的算法啦,也是非常的累啊。 话不多说下面看看最短路问题吧。 最短路问题是有向图,要求的是图中一个点到起点的距离,其中我们要输入点和点之间的距离,来求最短路。 下面分为几类题目: 单源汇最短路--一个起

    2024年01月21日
    浏览(43)
  • 8.3.1 蓝桥杯图论之Floyd&Dijkstra

    在蓝桥杯等算法竞赛中,图论问题占据了重要地位,其中路径查找是一个经常出现的主题。Floyd-Warshall算法和Dijkstra算法是解决图中最短路径问题的两种经典算法。本篇博客将介绍这两种算法的原理和实现,以及它们的应用场景。 Floyd-Warshall算法是一种计算图中所有最短路径的

    2024年02月19日
    浏览(40)
  • 单源最短路径(spfa,Dijkstra, bellman-ford)

    目录  Dijkstra 原理:基于贪心。 为什么 Dijkstra 不能处理有负边的情况 Bellman-ford 原理:动态规划, 实质见floyd的另一篇博客 1,能找负环, 2,有变数限制的最短路径 spfa 原理 spfa怎么求负环, 原理:基于贪心。 第一步 初始化距离,dist[1] = 0, 一号点到起点的距离为0, 其他点

    2024年02月04日
    浏览(50)
  • 最短路Dijkstra,spfa,图论二分图算法AYIT---ACM训练(模板版)

    最短路Dijkstra,spfa,图论二分图算法AYIT—ACM训练(模板版) A — Dijkstra B — spfa/Dijkstra C — 二分图 D — 二分图 E — 二分图 F — 二分图 G — Dijkstra H — Topsort Dijkstra算法基础模板题 💬 模板演示: 朴素版本Dijkstra: 💬 代码演示: 🚩 运行结果: spfa算法: 💬 代码演示: 🚩

    2024年02月10日
    浏览(49)
  • 图论14-最短路径-Dijkstra算法+Bellman-Ford算法+Floyed算法

    https://github.com/Chufeng-Jiang/Graph-Theory/tree/main/src/Chapter11_Min_Path 2.4.1 判断某个顶点的连通性 2.4.2 求源点s到某个顶点的最短路径 存放节点编号和距离 这里的缺点就是,更新node时候,会重复添加节点相同的node,但是路径值不一样。不影响最后结果。 更新pre数组 输出路径 初始化两

    2024年02月04日
    浏览(35)
  • 图搜索算法详解 - DFS、BFS、Bellman-Ford、Dijkstra

    图搜索算法是许多应用程序的基础,例如社交网络分析、路径规划、数据挖掘和推荐系统。在本文中,我们将深入探讨图搜索算法的世界,探索它们的定义、重要性和实际应用。 图搜索算法是一种用于遍历图的技术,图是由 关系 连接的 节点集合 。在社交网络、网页或生物

    2024年02月16日
    浏览(42)
  • C++ | 数据结构与算法 | 单源最短路径 | Dijkstra && Bellman Ford

    (关于代码实现的图结构,可以看图结构的实现这篇文章) Dijkstra的实现与Prim的实现相似,两者都是通过贪心思想实现,它们有什么不同呢?首先Prim算法是针对无向图的最小生成树的,而Dijkstra算法是针对 有向图 的最短路径生成。一个的目的是连接图中的所有顶点,生成一

    2024年02月03日
    浏览(49)
  • Dijkstra算法和Floyd算法详解(MATLAB代码)

    Dijkstra 算法是由 E.W.Dijkstra 于 1959 年提出,又叫迪杰斯特拉算法,它应用了贪心算法模式,是目前公认的最好的求解最短路径的方法。算法解决的是有向图中单个源点到其他顶点的最短路径问题,其主要特点是每次迭代时选择的下一个顶点是标记点之外距离源点最近的顶点。

    2024年02月16日
    浏览(39)
  • 【图论】SPFA求负环

    算法提高课笔记 负环 :环上权值之和是负数 求负环的常用方法 基于SPFA 统计每个点入队次数,如果某个点入队n次,则说明存在负环(完全等价于Bellman-Ford算法) 统计当前每个点的最短路中所包含的边数,如果某点的最短路包含的边数大于等于n,则说明存在负环 玄学结论:

    2024年02月09日
    浏览(40)
  • 第十八章 SPFA算法以及负环问题(利用dijkstra推导出该算法,超级详细!!)

    我们回顾一下之前的dijkstra算法的证明过程。如果大家没看过之前的dijkstra算法的简易证明的话,作者在这里建议先去看一下。 传送门: 第十六章 Dijkstra算法的讲解以及证明(与众不同的通俗证明) 那么假设你已经看过这篇文章,我们发现,我们将每次松弛操作后的最小距离

    2024年02月02日
    浏览(57)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包