最短路徑問題三種算法板子

Dijkstra算法

這個(gè)算法解決單源最短路問題。

從起點(diǎn)s出發(fā)，將與s點(diǎn)相連的點(diǎn)入隊(duì)，然后更新每一個(gè)點(diǎn)的距離。

第二步從入隊(duì)的點(diǎn)里找一個(gè)s到其距離最小的點(diǎn)，然后再以這個(gè)點(diǎn)進(jìn)行拓展更新，如果到達(dá)一個(gè)點(diǎn)能夠?qū)⑵涓拢⑶胰晕慈腙?duì)，則將這個(gè)點(diǎn)入隊(duì)。

不斷地取隊(duì)里s到其距離最小的點(diǎn)，然后再進(jìn)行更新。如果更新了的點(diǎn)未入隊(duì)，則入隊(duì)。

一直重復(fù)到不能夠更新位置。

每一次更新，代表會(huì)有一個(gè)點(diǎn)入隊(duì)，所以隊(duì)為空即為全部更新完畢。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<queue>

using namespace std;

const int oo=2147483647;

int n,m,s;
int pi,p[100005],nex[500005],cost[500005],to[500005];
int val[100005];
bool vis[100005];
struct Dij{
	int t,value;
	friend bool operator < (Dij i,Dij j)
	{
		return i.value > j.value;
	}
};

priority_queue<Dij> q;

void in_map(int u,int v,int c)
{
	pi++; nex[pi]=p[u]; p[u]=pi; cost[pi]=c; to[pi]=v;
}

void read_in()
{
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int x,y,c;
		cin>>x>>y>>c;
		in_map(x,y,c); 
	}
	for(int i=1;i<=n;i++)
	  val[i]=oo;
}

void Dijkstra()
{
	val[s]=0;
	Dij S;
	S.t=s;
	q.push(S);
	while(!q.empty())
	{
		Dij U=q.top();q.pop();
		int u=U.t;
		if(vis[u]) continue;
		vis[u]=true;
		for(int k=p[u],v=to[k];k;k=nex[k],v=to[k])
		{
			if(val[v] > val[u] + cost[k])
			{
				val[v]=val[u]+cost[k];
				Dij V;V.t=v;V.value=val[v];
				q.push(V);
			}
		}
	}
	for(int i=1;i<=n;i++)
	  cout<<val[i]<<' ';
}

int main()
{ 
	read_in();
	Dijkstra();
	return 0;
}

SPFA算法

SPFA算法雖說好用，但是據(jù)說會(huì)被一些數(shù)據(jù)卡。

它還是只是解決單源最短路。

先從源點(diǎn)出發(fā)，然后將與源點(diǎn)相連的點(diǎn)更新，如果更新的點(diǎn)仍未入隊(duì)，則入隊(duì)。

然后按照入隊(duì)順序取隊(duì)里第一個(gè)元素，將與之相連的點(diǎn)進(jìn)行松弛，如果松弛了的點(diǎn)為入隊(duì)則繼續(xù)入隊(duì)。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>

using namespace std;

const int INF=2147483647;
int pi,p[10005],nex[500005],to[500005],cost[500005];
int n,m,s;
int val[10005];
bool vis[10005];
queue<int> q;

void read_into(int u,int v,int c)
{
	pi++; nex[pi]=p[u]; p[u]=pi; to[pi]=v; cost[pi]=c;
}

void read_in()
{
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,c;
		cin>>u>>v>>c;
		read_into(u,v,c);
	}
	for(int i=1;i<=n;i++)
	  val[i]=INF;
}

void SPFA()
{
	val[s]=0;vis[s]=true;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		vis[u]=false;
		for(int k=p[u],v=to[k];k;k=nex[k],v=to[k])
		{
			if(val[v] > val[u] + cost[k])
			{
				val[v]=val[u]+cost[k];
				if(!vis[v])
				{
					q.push(v);
					vis[v]=true;
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	  cout<<val[i]<<' ';
}

int main()
{
	read_in();
	SPFA();
	return 0;
}

Floyd算法

Floyd算法可以解決多源問題，它類似于DP。

假設(shè)要找i到j(luò)的距離，我們可以找到一個(gè)中間點(diǎn)k，用i到k的距離和k到j(luò)的距離進(jìn)行相加得到i到j(luò)的距離。

f[i][j]=min(f[i][j],f[i][k]+f[k][j])

利用這個(gè)式子來推。

#include<iostream>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,s;
int f[10005][10005];
void read_in()
{
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    f[i][j]=INF;
	for(int i=1;i<=m;i++)
	{
		int u,v,c;
		cin>>u>>v>>c;
		f[u][v]=min(f[u][v],c);
	}
}
void Floyd()
{
	
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				  f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
			}
		}
	}
	f[s][s]=0;
	for(int i=1;i<=n;i++)
	  cout<<f[s][i]<<' ';
}
int main()
{
	read_in();
	Floyd();
	return 0;
}