首页 OI 模板

# 最短路的各个算法

# 一、Floyd

时间复杂度为O(n3)O(n^3)，但优点是可以计算图中任意两点之间的最短距离

Code:

int dis[N][N];

void Floyd()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            if(i!=k)
            {
                for(int j=1;j<=n;j++)
                {
                    if(j!=i && j!=k && dis[i][k]+dis[k][j]<dis[i])
                        dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }
    return;
}

例题：牛大赛

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=101;
int n,m,win[N],lose[N];
bool flag[N][N];

int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		flag[a][b]=true;
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			if(i!=k)
			{
				for(int j=1;j<=n;j++)
				{
					if(j!=i && j!=k && flag[i][k] && flag[k][j])
						flag[i][j]=true;
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(flag[i][j])
				win[i]++,lose[j]++;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(win[i]+lose[i]+1==n)
			ans++;
	printf("%d\n",ans);
	return 0;
}

# 二、Dijskra

时间复杂度正常的是O(n2)O(n^2)，用堆优化后可以达到O(nlogn)O(nlogn)，优点是快，不容易被卡（相对于SPFASPFA 而言），缺点是只能求一个点到其他点的最短距离

Code:

int dis[N]

void Dijskra()
{
      //普通版O(n^2)
    for(int i=1; i<=n; i++)
        dist[i]=dis[st][i];
    flag[S]=true;
    for(int i=1; i<n; i++)
    {
        int minn=0x7f7f7f7f;
        int to=0;
        for(int j=1; j<=n; j++)
        {
            if(!flag[j] && d[j]<minn)
            {
                minn=d[j];
                to=j;
            }
        }
        if(to==0)
            break;
        flag[to]=true;
        for(int j=1; j<=n; j++)
        {
            if(dist[j]>dist[to]+dis[to][j] && !flag[j])
                dist[j]=dist[to]+dis[to][j];
        }
    } 
}
//------------------------------------------------
struct node 
{
    long long to;
    long long len;
    node(int tt,int ll)
    {
        to=tt;
        len=ll;
    }
    node()
    {
    }
};
vector <node> v[N];

struct edge
{
    int to;
    int dis;
    edge(int tt,int dd)
    {
        to=tt;
        dis=dd;
    }
    edge()
    {
    }
    bool operator < (const edge & ot) const
    {
        return dis>ot.dis;
    }
};
priority_queue <edge > q; 

int dis[N];

void Dijskra_heap()
{
    //堆优化版O(nlogn)
     for(int i=2;i<=n;i++)
        dis[i]=0x7f7f7f7f;
    dis[1]=0;
    q.push(edge(1,0));
    while(q.size())
    {
        int t=q.top().to;
        q.pop();
        if(flag[t]) 
            continue;
        flag[t]=true;
        int size=v[t].size();
        for(int i=0;i<size;i++)
        {
            int to=v[t][i].to;
            int len=v[t][i].len;
            if(dis[to]>dis[t]+len)
            {
                dis[to]=dis[t]+len;
                q.push(edge(to,dis[to]));
            }
        }
    }
    return;
 }

例题：单源最短路径

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=300001;
long long n,m,S,dis[N];
bool vis[N];
struct node
{
	long long to,len;
	node(long long tt,long long ll)
	{
		to=tt,len=ll;
	}
	node()
	{
	}
};
vector <node > g[N];
struct edge
{
    long long to;
    long long dis;
    edge(long long tt,long long dd)
    {
        to=tt;
        dis=dd;
    }
    edge()
    {
    }
    bool operator < (const edge & ot) const
    {
        return dis>ot.dis;
    }
};
priority_queue <edge > q; 
void Dijskra_heap()
{
     for(int i=2;i<=n;i++)
        dis[i]=9999999999999;
    dis[1]=0;
    q.push(edge(1,0));
    while(q.size())
    {
        long long t=q.top().to;
        q.pop();
        if(vis[t]) 
            continue;
        vis[t]=true;
        long long size=g[t].size();
        for(int i=0;i<size;i++)
        {
            long long to=g[t][i].to;
            long long len=g[t][i].len;
            if(dis[to]>dis[t]+len)
            {
                dis[to]=dis[t]+len;
                q.push(edge(to,dis[to]));
            }
        }
    }
    return;
} 
int main()
{
	scanf("%lld %lld %lld",&n,&m,&S);
	for(int i=1;i<=m;i++)
	{
		long long a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		g[a].push_back(node(b,c));
	}
	Dijskra_heap();
	for(int i=1;i<=n;i++)
	{
		if(i!=n)
			printf("%lld ",dis[i]==9999999999999?-1:dis[i]);
		else
			printf("%lld\n",dis[i]==9999999999999?-1:dis[i]);
	}
	return 0;
}

# 三、SPFA

众所周知，SPFASPFA 已经死了，如果你不知道，那就不知道吧

那我为什么要写这个算法呢，因为 SPFA 有一个最大的好处，那就是好写好记，时间复杂度为O(kE)O(kE)，其中kk 是一个常数，EE 是边数，但是最坏时间复杂度是O(VE)O(VE)，VV 是图中点的数目，它也可以求单源最短路径，但是你用SPFASPFA 做DijskraDijskra 的例题会 T 掉，所以例题是另一个

例题：单源最短路（弱化版）

Code:

#include <bits/stdc++.h>
using namespace std;
const long long N=200001;
struct node
{
    long long to;
    long long len;
    node(long long tt,long long ll)
    {
        to=tt;
        len=ll;
    }
    node()
    {
    }
};
vector <node> g[N];
queue <long long > q;
long long st,n,m,cnt[N],dis[N];
bool flag[N];
void spfa()
{
    q.push(st),flag[st]=true,dis[st]=0;
    while(!q.empty())
    {
        long long t=q.front();
        q.pop();
        flag[t]=false;
        long long size=g[t].size();
        for(long long i=0;i<size;i++)
        {
            long long to=g[t][i].to;
            long long len=g[t][i].len;
            if(dis[to]>dis[t]+len)
            {
                dis[to]=dis[t]+len;
                if(!flag[to])
             	   q.push(to),flag[to]=true;
            }
        }
    }
    return;
}
int main()
{
	scanf("%lld %lld %lld",&n,&m,&st);
	for(int i=1;i<=n;i++)
		dis[i]=2147483647;
	for(long long i=1;i<=m;i++)
	{
	    long long x,y,z;
	    scanf("%lld %lld %lld",&x,&y,&z);
	    g[x].push_back(node(y,z));
	}
	spfa();
	for(long long i=1;i<=n;i++)
		printf("%lld ",dis[i]);
    return 0;
}