【图论】最短路算法

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

1、Dijkstra算法

不能处理边权为负的情况,复杂度O(nlogn)

步骤与基本思路

(1)初始化距离数组dist[N],将其所有值赋为0x3f,并将起点1的dist初始化为0,存入优先队列heap中

(2)从所有未被遍历的点中找到与起点1的距离dist[i]最小的点,并将该点标记为已遍历

(3)利用刚刚遍历的这个点 i 更新所有 i 的出边所连的点与起点1的距离,更新后存入heap中

(4)重复操作(2)(3)直至heap空

Dijkstra板子

int dijkstra() // 返回起点到终点的距离
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1}); // first为dist second为具体的点

    while (heap.size())
    {
        auto t = heap.top(); // 即取出与起始距离最短点
        heap.pop();

        int distance = t.first, ver = t.second;

        if (st[ver]) continue;
        st[ver] = true;

        // 遍历所有与ver相邻的点 更新他们的dist
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1; // 说明起点到不了终点
    return dist[n];
}

2、Bellman-Ford算法

可以解决对边数有要求的最短路问题,复杂度O(n^2)

步骤与基本思路

(1)初始化距离数组dist[N],将其所有值赋为0x3f,并将起点1的dist初始化为0

(2)遍历 k 次,第 i 次表示这一轮的最短路最多经过 i 条边:每轮先复制上一轮的dist(防止本轮前面的dist更新对后面的更新有影响),然后遍历所有边,更新dist为最小值

Bellman-Ford板子

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

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i ++ )
    {
        memcpy(last, dist, sizeof dist); // 将本轮还没有更新的dist值赋给last
        for (int j = 0; j < m; j ++ )
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.w);
        }
    }
}

3、SPFA算法

可以解决有负权边的情况,还可以判断负环,复杂度O(n^2)

步骤与基本思路

(1)初始化距离数组dist[N],将其所有值赋为0x3f,并将起点1的dist初始化为0

(2)建立队列q,将起点1存入队列中。同时建立st数组记录哪些点入队

(3)每轮取出队头,遍历与队头相连的所有点,更新这些点的dist,并将不在队中的点入队

(4)重复(3),直到队空

SPFA板子

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

4、Floyd算法

数据范围小时用该方法合适,可以处理负权边,时间复杂度O(n^3)

步骤与基本思路

设置 k 为中转站,每轮更新 i -> j 距离为 i -> j 和 i -> k k -> j 的最小值文章来源地址https://www.toymoban.com/news/detail-605299.html

Floyd板子

void floyd()
{
    for (int k = 1; k <= n; k ++ ) // 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]);
            }
        }
    }
}

到了这里,关于【图论】最短路算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C语言数据结构——图的最短路径算法解决实例问题

    一、问题描述 W公司在某个地区有6个产品销售点,现根据业务需要打算在其中某个销售点上建立一个中心仓库,负责向其他销售点提供产品。由于运输线路不同,运输费用也不同。假定每天需要向每个销售点运输一次产品,那么应将中心仓库建在哪个销售点上,才能使运输费

    2024年02月08日
    浏览(45)
  • 数据结构实验任务六 :基于 Dijsktra 算法的最短路径求解

    本次代码为实验六:基于 Dijsktra 算法的最短路径求解实现。本实验的重点在于对于Dijsktra算法的理解。有关Dijsktra的资料可以参考有关博文: 图论:Dijkstra算法——最详细的分析,图文并茂,一次看懂!-CSDN博客 以下附上实现代码: 以上代码仅供参考,欢迎交流。

    2024年02月04日
    浏览(46)
  • 数据结构 -最短路径dijkstra(迪杰斯特拉)算法讲解及代码实现

            迪杰斯特拉算法是一种广义的贪心算法,求出局部最优解,再去求全局最优解 举例图:(起始点为1) 辅助数组: s:记录了目标顶点到其他顶点的最短路径是否求得(求得为1,否则为0) p:目标顶点到其他顶点的最短路径的前驱节点 (如,求得1-7-5的最短路径,那

    2024年02月11日
    浏览(34)
  • 数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)

    目录 问题分类  无权图单源最短路径算法 思路 伪代码 时间复杂度 代码实现(C语言) 有权图单源最短路径算法 Dijkstra(迪杰斯特拉)算法 伪代码  时间复杂度  代码实现(C语言) 多源最短路径算法 两种方法 Floyd算法 代码实现(C语言) 最短路径问题的抽象 在网络中,求

    2024年02月08日
    浏览(57)
  • 数据结构与算法 —— 最短路径Dijkstra算法(迪杰斯特拉)详细图解以及python实现

    目录 前言 1. 介绍 2. 加权图 2.1 概念 3. 最短路径 -- Dijkstra 算法 3.1 历史 3.2 Dijkstra 算法的基本思路 3.3 Dijkstra 算法图解 4.  python中dijkstra算法的实现 5. 总结  前两章我们讲到了关于图的基本知识,和广度/深度优先搜索。 本章,我们将介绍 加权图 和 最短路径 的相关知识。 最

    2024年02月12日
    浏览(51)
  • C语言算法与数据结构,旅游景区地图求最短路径

    本次作业要求完成一个编程项目。请虚构一张旅游景区地图,景区地图包括 景点(结点)和道路(边):地图上用字母标注出一些点,表示景点(比如,以点 A、B、C、D、E、F等(至少6个点)多个表示,其中的 两个字母 A 和 B 分别表示景区的入口和出口 );点与点之间的连

    2024年02月04日
    浏览(42)
  • 数据结构(12)Dijkstra算法JAVA版:图的最短路径问题

    目录 12.1.概述 12.1.1.无权图的最短路径  12.1.2.带权图的最短路径 1.单源最短路径 2.多源最短路径 12.2.代码实现 无权图的最短路径,即最少步数,使用BFS+贪心算法来求解最短路径,比较好实现,此处不做展开讨论。 有权图的最短路径,不考虑权重为负数的情况,因为权重为负

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

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

    2024年02月03日
    浏览(49)
  • 【数据结构】最短路径算法实现(Dijkstra(迪克斯特拉),FloydWarshall(弗洛伊德) )

    最短路径问题 :从在带权有向图G中的某一顶点出发,找出一条通往另一顶点的最短路径,最短也就是沿路径各边的权值总和达到最小。 单源最短路径问题:给定一个图G = ( V , E ) G=(V,E)G=(V,E),求源结点s ∈ V s∈Vs∈V到图 中每个结点v ∈ V v∈Vv∈V的最短路径 针对一个带权

    2024年02月04日
    浏览(47)
  • 数据结构的应用场景:如社交网络、路由算法、图论、网络协议等

    作者:禅与计算机程序设计艺术 数据结构(Data Structure)是计算机科学中存储、组织、管理数据的方式,主要用于解决信息检索、处理和运算时的效率及空间占用问题。它是指数据元素(elements)之间的关系、顺序和逻辑结构,以及相互作用的算法。数据结构通常采用抽象数据类

    2024年02月14日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包