搜索与图论 - 搜索与图在算法中的应用【中】

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

目录

迪杰斯特拉算法Dijkstra

 Dijkstra求最短路 I

Dijkstra求最短路 II

贝尔曼-福特算法 bellman-ford

有边数限制的最短路

SPFA算法

spfa求最短路

 spfa判断负环

Floyd

Floyd求最短路


搜索与图论 - 搜索与图在算法中的应用【中】

 

迪杰斯特拉算法Dijkstra

该算法不能存在负权边

 Dijkstra求最短路 I

搜索与图论 - 搜索与图在算法中的应用【中】

思路:

  1. 初始化距离数组, dist[1] = 0, dist[i] = inf;
  2. for n次循环 每次循环确定一个min加入S集合中,n次之后就得出所有的最短距离
  3. 将不在S中dist_min的点->t
  4. t->S加入最短路集合
  5. 用t更新到其他点的距离

搜索与图论 - 搜索与图在算法中的应用【中】

 更新为其他到起点的最短路径

1、

int g[N][N];    用g[x][[y]表示x、y之间的距离
int dist[N];    用于记录每一个点距离第一个点的距离
bool st[N];     用于记录该点的最短距离是否已经确定 

然后开启n次操作,每次操作依次找到节点最短路

2、设第一个点为源点,令dist[1]==0,dist[i]==正无穷(若该点与源点不相连,则距离无穷)

搜索与图论 - 搜索与图在算法中的应用【中】

3、

for循环遍历所有点,找到最短距离没有确定的点中的 距离该点最近的点;并用该点更新其他点距离

搜索与图论 - 搜索与图在算法中的应用【中】

 解析:

(第一次操作)从源点开始找,因为第一个点为源点,所以自己到自己的距离为0,于是找到第一个点成为离源点最近的点;确定了第一个点到源点的最短距离;用该点(一号点)更新到其他点到源点最短距离(二号点距离为2,三号距离4)

4、

搜索与图论 - 搜索与图在算法中的应用【中】

 解析:

(第二次操作)从上次确定最短距离的点开始找,找距离该点最短的点(二号点);确定了二号点到源点的最短距离;用该点(二号点)更新其他点到源点最短距离(得三号点距离为3)

5、有n个节点,我们操作n次,最终得到n节点到源点的最短路

核心操作: 找到距离源点最近的节点t,然后用t更新其他节点

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=510;

int g[N][N];    //为稠密阵所以用邻接矩阵存储,用g[x][[y]表示x、y之间的距离
int dist[N];    //用于记录每一个点距离第一个点的距离
bool st[N];     //用于记录该点的最短距离是否已经确定

int n,m;

int Dijkstra()
{
    memset(dist, 0x3f,sizeof dist);     //初始化距离  0x3f代表无限大
    dist[1]=0;  //第一个点到自身的距离为0


    for(int i=0;i<n;i++)      //有n个点所以要进行n次操作 
    {
        int t=-1; //t存储当前访问的点,值为-1只是为了标记第一个搜到的节点(因为题目中无负值,-1不会影响结点判断)

        for(int j=1;j<=n;j++)   //从1号点开始遍历 dist 数组,找到没有确定最短路径的节点中 距离源点最近的点t
            if(!st[j]&&(t==-1||dist[t]>dist[j]))
                t=j;    

        st[t]=true;   

        for(int j=1;j<=n;j++)     //找到了距离已经确定最短路的点t,用点t去更新其他的点到源点的距离
            dist[j]=min(dist[j],dist[t]+g[t][j]);   
                                
    }

    if(dist[n]==0x3f3f3f3f) return -1;  //如果第n个点路径为无穷大即不存在最短路径
    return dist[n];
}
int main()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof g);    //初始化图 因为是求最短路径
                                //所以每个点初始为无限大

    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);     //如果发生重边的情况则保留最短的一条边,x到y的距离为z
    }

    cout<<Dijkstra()<<endl;
    return 0;
}

时间复杂度分析
        寻找路径最短的点:O(n^2)
        加入集合S:O(n)
        更新距离:O(m)
        所以总的时间复杂度为O(n^2)

Dijkstra求最短路 II

搜索与图论 - 搜索与图在算法中的应用【中】

思路:最小堆优化 

1. 一号点的距离初始化为零,其他点初始化成无穷大。
2. 将一号点放入堆中。
3. 不断循环,直到堆空。每一次循环中执行的操作为:
    弹出堆顶(与朴素版diijkstra找到S外距离最短的点相同,并标记该点的最短路径已经确定)。
    用该点更新临界点的距离,若更新成功就加入到堆中。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int N=1e6+10;

int h[N],e[N],ne[N],idx;//数据范围大,稀疏图,邻接表存储
int w[N];
int dist[N];//到源点的距离
bool st[N];
int n,m;

void add(int x,int y,int c)
{
    w[idx]=c;//存x到y边长
    e[idx]=y;ne[idx]=h[x];h[x]=idx++;//邻接表存储
}

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    //利用小根堆,根据距离从小到大排序
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    
    heap.push({0,1});//{距离,节点号},顺序不能变,pair排序根据先first在根据second排
    while(heap.size())
    {
        PII k=heap.top();
        heap.pop();
        int ver=k.second,distance=k.first;//取节点号 和 源点距离ver的距离
        
        if(st[ver]) continue;//如果距离已经确定,则跳过该点(防止重边)
        st[ver]=true;
        
        for(int i=h[ver];i!=-1;i=ne[i])//更新ver所连接的节点距离
        {
            int j=e[i];
            if(dist[j]>distance+w[i])//该点到源点距离>ver到源点距离+ver到该点距离
            {
                dist[j]=distance+w[i];
                heap.push({dist[j],j});//只将被更新的点入堆
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--)
    {
        int x,y,c;
        cin>>x>>y>>c;
        add(x,y,c);
    }
    cout<<dijkstra()<<endl;
    return 0;
}

在priority_queue[PII,vector<PII>, greater<PII> > heap;中将返回堆顶
利用堆顶来更新其他点,并加入堆中类似宽搜

贝尔曼-福特算法 bellman-ford

注意连锁想象需要备份, struct Edge{inta,b,c} Edge[M];
初始化dist, 松弛dist[x.b] = min(dist[x.b], backup[x.a]+x.w);
松弛k次,每次访问m条边

有边数限制的最短路

搜索与图论 - 搜索与图在算法中的应用【中】

核心算法:

1、松弛操作

所谓松弛操作,就是看一看dist[v]和dist[u]+u到v的距离哪个大一点。

如果前者大一点,就说明当前的不是最短路,就要赋值为后者,这就叫做松弛。

dist[b]=min(dist[b],dist[a]+w);

每次取出两点以及他们连接的边的权重(a,b,w表示a—>b的一条边);

用从起点到a的当前最短距离+权重来更新从起点到b的当前最短距离;

2、backup数组

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);//dist[b] = min(dist[b], dist[a] + w);
    }
}
  • backup[j]表示每次进入第2重循环的dist数组的备份;
  • 由题意得k==1,因为有边数限制,所以不能走上面两条边的最短路程2,只能走下路得到最短路程3;
  • 假设没有backup备份数组,虽然只k了一次,但是我们在第一轮松弛操作的时候就可以直接将二三号点的最短距离求出,则得出三号点最短路为2,显然这是错误的

搜索与图论 - 搜索与图在算法中的应用【中】

搜索与图论 - 搜索与图在算法中的应用【中】

  • 使用backup备份数组,防止发生串联更新
memcpy(backup,dist,sizeof dist);
dist[b]=min(dist[b],backup[a]+w);

搜索与图论 - 搜索与图在算法中的应用【中】

  • 用上轮节点2更新的距离--无穷大,来更新节点3, 再取最小值,无穷+1大于无穷,节点3仍然无穷,所以最后更新节点3离起点的距离是3。

总结:利用backup数组保证每次更新只对两点之间的一条边

3、

为什么表示无穷不是 ==

if(t==0x3f3f3f3f) puts("impossible");
 else cout<<t<<endl;

而是 

if(t>0x3f3f3f3f/2) puts("impossible");
 else cout<<t<<endl;

 解析:

  1. 如下图所示,4,5号点无法与源点连接,所以距离都是无穷,但是无穷并不都是是标准的0x3f3f3f3f;
  2. 由于算法的松弛遍历,最终4号点距离为0x3f3f3f3f,而5号点距离为0x3f3f3f3f-2;
  3. 最恶心的情况就是一号点(源点)不相连,其余499个节点相连且距离都为-10000,那么n号点距离为0x3f3f3f3f-499*10000;
  4. 而最短路最大距离为500*10000,所以t大于的范围为【500*10000,0x3f3f3f3f-499*10000】 ,显然0x3f3f3f3f/2在其中(即大于这个范围的数会输出“impossible”,而不是输出t值)

(0x3f3f3f3f == 1061109567)

搜索与图论 - 搜索与图在算法中的应用【中】

#include<iostream>
#include<cstring>
using namespace std;

const int N=1e5+10;
int dist[N],backup[N];
int n,m,k;

struct edge
{
    int a,b,w;
}edge[N];

int bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=1;i<=k;i++)
    {
        memcpy(backup,dist,sizeof dist);
        for(int j=1;j<=m;j++)
        {
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    return dist[n];
}

int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i]={a,b,c};
    }
    int t=bellman_ford();
    if(t>0x3f3f3f3f/2) puts("impossible");
    else cout<<t<<endl;
    return 0;
}

SPFA算法

Bellman_ford优化:

Bellman_ford算法会遍历所有的边,但是有很多的边遍历了其实没有什么意义,我们只用遍历那些到源点距离变小的点所连接的边即可,只有当一个点的前驱结点更新了,该节点才会得到更新;因此考虑到这一点,我们将创建一个队列每一次加入距离被更新的结点。

 该算法不可存在如图负权回路

搜索与图论 - 搜索与图在算法中的应用【中】

spfa求最短路

搜索与图论 - 搜索与图在算法中的应用【中】

思路:

  1. 建立一个队列,初始时队列里只有起始点。
  2. 再建立一个数组记录起始点到所有点的最短路径(该表格的初始值要赋为极大值,该点到他本身的路径赋为0)。
  3. 再建立一个数组,标记点是否在队列中。
  4. 队头不断出队,计算始点起点经过队头到其他点的距离是否变短,如果变短且被点不在队列中,则把该点加入到队尾。
  5. 重复执行直到队列为空。
  6. 在保存最短路径的数组中,就得到了最短路径。
#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;
        //如果t变小了,那么t所连接的所有节点都有可能变小
        
        for (int i = h[t]; i != -1; i = ne[i])//检查t所连接的所有节点
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j]) //如果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;
}

 spfa判断负环

搜索与图论 - 搜索与图在算法中的应用【中】

思路: 一个通俗易懂的想法

  1. 如果存在负环,那么程序就会在环里面一直转永远不会停,因为路径会一直减小
  2. 如果不存在负环,有n个节点,那么最短路径长度次数不会超过n-1,因为大于n-1说明有一个点走了至少两次

我们利用cnt[]记录走的边的个数,如果走的边超过n-1那么就有负环

由于可能不是连通图,需要对每个点进行检验,即每个点都入队

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

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int w[N];
int dist[N]
int cnt[N];//记录每个点到起点的边数,当cnt[i] >= n 表示出现了边数>=结点数,必然有环,而且一定是负环!
bool st[N];//判断当前的点是否已经加入到队列当中了;已经加入队列的结点就不需要反复的把该点加入到队列中了
//就算此次还是会更新到起点的距离,那只用更新一下数值而不用加入到队列当中。
//意味着,st数组起着提高效率的作用,不在乎效率的话,去掉也可以

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;
    // 这里不需要初始化,让dist为0即可,因为有负环dist会不断减小,不断更新

    
    queue<int> q;//用于检测所有点是否有负环
    for (int i = 1; i <= n; i ++ )
    {
        //判断负环,只从一个点出发,有可能到达不了负环那里,需要一开始就把所有结点放入队列,且标记进入了队列提高效率
        q.push(i);
        st[i] = true;
    }

    
    while (q.size())//spfa求最短路套路模板
    {
        
        int t = q.front();
        q.pop();
        
        st[t] = false;

        //更新与t邻接的边
        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];//结点j可以通过中间点t降低距离
                cnt[j] = cnt[t] + 1;//那么结点j在中间点t的基础上加一条到自己的边

                if (cnt[j] >= n) return true;//边数不小于结点数,出现负环,函数结束

                if (!st[j])//若此时j没在队列中,则进队。已经在队列中了,上面已经更新了数值。重复加入队列降低效率
                {
                    
                    q.push(j);//将被改变距离的结点入队
                    st[j] = true;
                }
            }
        }
    }
    return false;//走到这了,函数还没结束,意味着边数一直小于结点数,不存在负环
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    if (spfa()) puts("Yes");
    else puts("No");


    return 0;
}

Floyd

算法不能应用于负权回路

Floyd求最短路

搜索与图论 - 搜索与图在算法中的应用【中】

基于动态规划思想

算法模板:

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

记忆: k表示阶段,最外层;取i到j不经过k这个节点和经过k这个节点最短路

#include<iostream>
#include<cstring>
using namespace std;

const int N=210,INF=1e9;

int n,m,q;
int d[N][N];//d[i][j]表示从i到j的距离

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()
{
    cin>>n>>m>>q;
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)//初始化距离数组d
            if(i==j) d[i][j]=0;//如果是自己到自己则距离为0,否则无穷
            else d[i][j]=INF;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        d[a][b]=min(d[a][b],c);
    }
    
    floyd();
    
    while(q--)
    {
        int a,b;
        cin>>a>>b;
        
        int t=d[a][b];
        if(t>INF/2) puts("impossible");
        else cout<<t<<endl;
    }
    return 0;
}

搜索与图论 - 搜索与图在算法中的应用【中】文章来源地址https://www.toymoban.com/news/detail-403921.html

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

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

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

相关文章

  • 搜索与图论2.2-Floyd算法

    (Floyd) 算法是一种可以快速求解图上所有顶点之间最短路径的算法。 (Bellman-Ford) 和 (Dijkstra) 算法求解的都是从一个起始点开始的最短路。如果想要求解图中所有顶点之间的最短路,就需要枚举每个点做为起点,这样十分低效。 (Floyd) 算法(也称 (Floyd-Warshall) 算法)处理用

    2024年02月08日
    浏览(34)
  • acwing算法基础之搜索与图论--kruskal算法

    kruskal算法的关键步骤为: 将所有边按照权重从小到大排序。 定义集合S,表示生成树。 枚举每条边(a,b,c),起点a,终点b,边长c。如果结点a和结点b不连通(用并查集来维护),则将这条边加入到集合S中。 kruskal算法的时间复杂度为O(mlogm),它用来解决稀疏图的最小生成树问题

    2024年02月05日
    浏览(42)
  • 【算法基础:搜索与图论】3.3 拓扑排序

    https://oi-wiki.org/graph/topo/ 本文主要学习拓扑排序相关知识。 拓扑排序的英文名是 Topological sorting。 拓扑排序要解决的问题是给一个 有向无环图 的 所有节点排序 。 我们可以拿大学每学期排课的例子来描述这个过程,比如学习大学课程中有:程序设计,算法语言,高等数学,

    2024年02月16日
    浏览(47)
  • 【算法基础:搜索与图论】3.2 树与图的dfs和bfs

    要学会建树、建图的通用方法。 dfs 和 bfs 的代码框架。 https://www.acwing.com/problem/content/848/ 在 dfs 的过程中,统计各个节点作为断点时的连通块最大值。 https://www.acwing.com/problem/content/849/ 看到最短距离就可以想到使用宽搜。 注意! :题目中说明了 a 和 b 表示存在一条从 a 走到

    2024年02月16日
    浏览(38)
  • Acwing-基础算法课笔记之搜索与图论

    bellman-ford算法适用于负权边的图,求 1 到 n 的最多经过k条边的最短距离。 如图所示: 1 2 3 dist 0 ∞ infty ∞ ∞ infty ∞ ⇓ Downarrow ⇓ 1 2 3 dist 0 1 ∞ infty ∞ ⇓ Downarrow ⇓ 1 2 3 dist 0 1 2 此过程中出现了串联的结果,所以是错误的,此时需要进行备份操作。 备份操作如下: 为了

    2024年01月20日
    浏览(53)
  • acwing算法基础课(第三讲 搜索与图论)

    void dfs(int u){ if(n == u){ for(int i = 0;i n;i++) puts(g[i]); puts(“”); return; } for(int i = 0;i n;i++){ if(!col[i] !dg[u+i] !udg[n - u + i]){ g[u][i] = ‘Q’; col[i] = dg[u+i] = udg[n - u + i] = true; dfs(u+1); col[i] = dg[u+i] = udg[n - u + i] = false; g[u][i] = ‘.’; } } } int main(){ scanf(“%d”,n); for(int i = 0;i n;i++){ for(int j = 0;j

    2024年04月10日
    浏览(53)
  • 【AcWing算法基础课】第三章 搜索与图论

    本专栏文章为本人AcWing算法基础课的学习笔记,课程地址在这。如有侵权,立即删除。 特点 :尽可能先向 纵深方向 搜索。使用 stack 实现。所需空间 O(h) (h为深度)。不具有“最短性”。 题目链接 :842. 排列数字 1.1题目描述 给定一个整数 n,将数字 1∼n 排成一排,将会有

    2024年02月12日
    浏览(67)
  • 二十九、搜索与图论——克鲁斯卡尔算法(Kruskal 算法,稀疏图)

    解决问题: 多个城市中铺公路,使城市之间可以相互联通,问如何才能让铺设公路的长度最短——铺设的路径即为最小生成树。 思想: 从小到大枚举每条边,从小到大试图将每条边假如生成树,只要这条边对应的两个点不在一个集合,则把这条边加到集合中来。 主要面对的

    2024年02月05日
    浏览(45)
  • 【算法基础:搜索与图论】3.5 求最小生成树算法(Prim&Kruskal)

    最小生成树 有关树的定义 生成子图 :生成子图是从原图中选取部分节点以及这些节点之间的边所组成的图。生成子图中的所有节点和边都必须在原图中存在。 生成树 :一个连通 无向图 的 生成子图 ,同时要求是树。也即在图的边集中选择 n - 1 条,将所有顶点连通。 我们

    2024年02月16日
    浏览(40)
  • ✔ ★ 算法基础笔记(Acwing)(三)—— 搜索与图论(17道题)【java版本】

    1. 排列数字(3分钟) 每次遍历dfs参数是 遍历的坑位 原题链接 2. n-皇后问题 原题链接 方法 1. 按行遍历(过程中有回溯、剪枝) 思想: 每次递归中,遍历一行的元素,如果可以放皇后,就递归到下一行,下一行中不行了,就返回来,回溯, 方法2. 按每个元素遍历(没有减枝)

    2024年02月05日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包