首页 > 其他分享 >第三章 图论与搜索二

第三章 图论与搜索二

时间:2023-02-12 23:33:41浏览次数:44  
标签:图论 第三章 int 短路 存储 算法 搜索 dist 号点

最短路问题

常见的最短路问题可以分成两大类

  • 单源最短路
  • 多源汇最短路在最短路问题中,源点 也就是 起点汇点 也就是 终点

单源最短路

单源最短路,指的是求一个点,到其他所有点的最短距离。(起点是固定的,单一的)

单元最短路问题又分成两种(n:点数,m:边数):

  1. 所有边权都是正数
  • 朴素Dijkstra O(n2)
  • 堆优化Dijkstra O(mlogn)两者孰优孰劣,取决于图的疏密程度(取决于点数n,与边数m的大小关系)。当是稀疏图(n和m是同一级别)时,可能堆优化版的Dijkstra会好一些。当是稠密图时(m和n2是同一级别),使用朴素Dijkstra会好一些。
  1. 存在负权边
  • Bellman-Ford O(mn)
  • SPFA 一般:O(m),最坏:O(mn)

多源汇最短路

  • Floyd O(n3)

最短路问题的核心在于,把问题抽象成一个最短路问题,并建图。图论相关的问题,不侧重于算法原理,而侧重于对问题的抽象。

Dijkstra基于贪心,Floyd基于动态规划,Bellman-Ford基于离散数学。

算法的选用:通常来说,单源最短路的,如果没有负权重的边,用Dijkstra,有负权重边的,通常用SPFA,极少数用Bellman-Ford;多源最短路的,用Floyd

算法思路

朴素Dijkstra

用一个集合s来存放最短距离已经确定的点。

  1. 初始化dist,dist[1] = 0, 其他dist[i] = INF
  2. 循环n次:每次从距离已知的点中,选取一个不在s集合中,且距离最短的点t(这一步可以用小根堆来优化),把t加入到集合s中,遍历t的所有出边,更新这些出边所连接的点的距离。
  3. 当所有点都都被加入到s中,表示全部点的最短距离都已经确定完毕

朴素Dijkstra对应稠密图,因此用邻接矩阵来存储

算法模板

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路,如果不存在则返回-1
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[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

堆优化Dijkstra

堆可以自己手写(用数组模拟),也可以使用现成的(C++的STL提供了priority_queue,Java的JDK中提供了PriorityQueue)特别注意,插入堆的操作,由于更新距离时,可能对一些距离已知的点进行更新(更新为更小的距离),此时不能因为这个点已经在堆中就不进行插入了,因为其距离已经变了,堆中原有的节点已经无效了,按理说,应该修改堆中对应节点的距离值,然后做调整,实际上,可以直接插入一个新的节点(此时对于同一个节点,堆中有两份),但没有关系,堆中的重复节点不会影响最终的结果。

算法模板

typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离,如果不存在,则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离,second存储节点编号

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

Bellman-Ford

算法思路

  • 循环n次
  • 每次循环,遍历图中所有的边。对每条边(a, b, w),(指的是从a点到b点,权重是w的一条边)更新d[b] = min(d[b], d[a] + w)

(可以定义一个类,或者C++里面的结构体,存储a,b,w。表示存在一条边a点指向b点,权重为w)。则遍历所有边时,只要遍历全部的结构体数组即可

循环的次数的含义:假设循环了k次,则表示,从起点,经过不超过k条边,走到每个点的最短距离。

该算法能够保证,在循环n次后,对所有的边(a, b, w),都满足d[b] <= d[a] + w。这个不等式被称为三角不等式。上面的更新操作称为松弛操作。

该算法适用于有负权边的情况,注意:如果有负权环的话,最短路就不一定存在了。

该算法可以求出来,图中是否存在负权回路。如果迭代到第n次,还会进行更新,则说明存在一条最短路,路径上有n条边,n条边则需要n + 1个点,而由于图中一共只有n个点,所以这n + 1个点中一定有2个点是同一个点,则说明这条路径上有环;有环,并且此次进行了更新,说明这个环的权重是负的(只有更新后总的距离变得更小,才会执行更新)。

但求解负权回路,通常用SPFA算法,而不用Bellman-Ford算法,因为前者的时间复杂度更低。

代码模板

int n, m;       // n表示点数,m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边,a表示出点,b表示入点,w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离,如果无法从1走到n,则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式,就说明存在一条长度是n+1的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

SPFA

若要使用SPFA算法,一定要求图中不能有负权回路。只要图中没有负权回路,都可以用SPFA,这个算法的限制是比较小的。

SPFA其实是对Bellman-Ford的一种优化。

它优化的是这一步:d[b] = min(d[b], d[a] + w)

我们观察可以发现,只有当d[a]变小了,才会在下一轮循环中更新d[b]

考虑用BFS来做优化。用一个队列queue,来存放距离变小的节点。(当图中存在负权回路时,队列永远都不会为空,因为总是会存在某个点,在一次松弛操作后,距离变小)(和Dijkstra很像)

代码模板

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离,如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto 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])     // 如果队列中已存在j,则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

SPFA的好处:

能解决无负权边的问题,也能解决有负权边的问题,并且效率还比较高。但是当需要求在走不超过k条边的最短路问题上,就只能用Bellman-Ford算法了。

Floyd

求解多源汇最短路问题,也能处理边权为负数的情况,但是无法处理存在负权回路的情况。

使用邻接矩阵来存储图。初始使用d[i][j]来存储这个图,存储所有的边

算法思路:三层循环

算法模板

初始化:
    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;

// 算法结束后,d[a][b]表示a到b的最短距离
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]);
}

循环结束后,d[i][j]存的就是点i到j的最短距离。

原理是基于动态规划(具体原理在后续的动态规划章节再做详解)。

其状态表示是:d(k, i, j),从点i,只经过1 ~ k这些中间点,到达点j的最短距离

标签:图论,第三章,int,短路,存储,算法,搜索,dist,号点
From: https://www.cnblogs.com/chenjq12/p/17115014.html

相关文章

  • 第三章 图论与搜索一
    普通DFS与BFS概述DFS:深度优先搜索(Depth-First-Search)BFS:宽度优先搜索(Breadth-First-Search)DFS和BFS的对比DFS使用栈(stack)来实现,BFS使用队列(queue)来实现DFS所需要......
  • 基于Astar算法的栅格地图目标最短路径搜索算法MATLAB仿真,带GUI界面
    1.算法描述       Astar算法是一种图形搜索算法,常用于寻路。它是个以广度优先搜索为基础,集Dijkstra算法与最佳优先(bestfit)算法特点于一身的一种算法。它通过......
  • 基于GA算法的TSP最短路径搜索matlab仿真
    1.算法描述(1)编码:将问题的候选解用染色体表示,实现解空间向编码空间的映射过程。遗传算法不直接处理解空间的决策变量,而是将其转换成由基因按一定结构组成的染色体。编码方......
  • 【DFS】LeetCode 108. 将有序数组转换为二叉搜索树
    题目链接108.将有序数组转换为二叉搜索树思路类似于二分搜索,定位到数组中间mid,然后左边的子数组构成左子树,右边的子数组构成右子树,mid处的数字构成根结点。递归构建......
  • 【DFS】LeetCode 669. 修剪二叉搜索树
    题目链接669.修剪二叉搜索树思路若root.val小于边界值low,则root的左子树必然均小于边界值,我们递归处理root.right即可;若root.val大于边界值high,则root的......
  • 【DFS】LeetCode 98. 验证二叉搜索树
    题目链接98.验证二叉搜索树思路依据BST的定义:左子树的结点都比根结点小,右子树的结点都比根结点大。我们在递归过程中传递根节点的值,判断当前结点值与根结点值的大小......
  • 【数据结构与算法】图论算法(C++实现)
    一些基本概念图一个图\(G=(V,E)\)由顶点集V和边集E组成。每一条边就是一副顶点对\((u,v)\),其中\(u,v\inV\)。顶点u和顶点v邻接当且仅当\((u,v)\inE\)......
  • 推导部分和(图论)
     #include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintmaxn=1e5+10;intn,m,q;structedge{intv;llw;edge(){}......
  • 计算机体系结构第三章习题存档
    3Pipelining3.1 ASimpleImplementationofDLXBasicsteps:IF→ID→EX→MEM→WBReadPage3-3to3-5fordetails.3.2 TheBasicPipelineforDLXDuringMEM......
  • 微信公众号搜索量排名
    1:公众号排名的概念微信公众号搜索量排名是根据公众号在微信内的搜索量来进行排名的。由于微信公众号的搜索是实时的,所以公众号的搜索量也是实时变化的。目前,微信公众号搜......