搜索与图论(二)-Toy模板网

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

最短路

单源最短路

所有边权都是正数

朴素Dijkstra算法

基本思路:从1号点到其他点的最短距离

步骤:

定义一个s集合包含当前已确定最短距离的点

1、初始化距离dis[1] = 0,dis[其它] = 正无穷

2、for i 0-n循环n次

2.1找到不在s中的距离最近的点 ->t

2.2把t加到s当中去

2.3用t来更新其它点的距离

模板代码如下:

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

using namespace std;

const int N = 510;
int n,m;
int g[N][N];
//dis表示从1号点到其它点的距离
int dist[N];
//st表示每个点的最短路是否确定
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[i][j]);
    }

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

    return dist[n];
}
int main()
{
    scanf("%d%d", &n, &m);

    //初始化
    memset(g,0x3f,sizeof g);

    int t = dijkstra();

    printf("%d\n",t);

    return 0;
}

堆优化版的Dijkstra算法

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

using namespace std;

const int N = 100010;
int n,m;
//存储方式改为邻接表的形式
int h[N],w[N],e[N],ne[N],idx;
//dis表示从1号点到其它点的距离
int dist[N];
//st表示每个点的最短路是否确定
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;
}

存在负权边

Bellman-Ford算法

基本思路:n次迭代，每次循环所有边，每次循环更新最短距离

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

using namespace std;

const int M = 100010, N = 510;

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

struct Edge
{
    int a,b,w;

}edges[M];

int bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

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

SPFA算法

对Bellman-Ford算法的一个优化

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

using namespace std;

const int N = 100010;
int n,m;
//存储方式改为邻接表的形式
int h[N],w[N],e[N],ne[N],idx;
//dis表示从1号点到其它点的距离
int dist[N];
//st表示每个点的最短路是否确定
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);
   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();

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

    return 0;
}

多源汇最短路

Floyd

利用临界矩阵来存储文章来源地址https://www.toymoban.com/news/detail-624907.html

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

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");
        printf("%d\n",d[a][b]);
    }

    return 0;
}

到了这里，关于搜索与图论(二)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！