最短路

最短路

---

Bellman_Ford

bool bellman(int p)
{
	for(int i=1;i<=n;i++)	dist[i]=(i==p?0:inf);
	for(int i=1;i<=n;i++)	//实际上n-1即可，因为每次至少增加一条边 
		for(int j=0;j<V.size();j++)
		{
			int u=V[j].t1,v=V[j].t2,w=V[j].dig;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				if(i==n)	return false;
			}
		}
	return true;
}

---

SPFA

bool SPFA(int s)
{
	queue<int> que;
	memset(cnt,0,sizeof(cnt));
	memset(inq,0,sizeof(inq));
	inq[s]=true;	que.push(s);
	while(!que.empty())
	{
		int tmp=que.front();	que.pop();
		inq[tmp]=false;
		for(int i=0;i<V[tmp].size();i++)
			if(dist[V[tmp][i].t1]>dist[tmp]+V[tmp][i].dig){
				dist[V[tmp][i].t1]=dist[tmp]+V[tmp][i].dig;
				cnt[V[tmp][i].t1]=cnt[tmp]+1;
				if(cnt[V[tmp][i].t1]>=n)	return false;
				if(!inq[V[tmp][i].t1])	que.push(V[tmp][i].t1),inq[V[tmp][i].t1]=true;
			}
	}
	return true;
 } 

---

Dijkstra

for(int i=1;i<=n;i++)	dist[i]=inf;
for(int i=1;i<=m;i++)
{
	int x,y,tempd;
	cin>>x>>y>>tempd;
 	a[x].push_back(node {y,tempd});
}//构建图 	 
u.push(node {s,0});
while(!u.empty())
{
	node temp=u.top();	u.pop();
	if(b[temp.name])	continue;
	dist[temp.name]=temp.digit;
	b[temp.name]=true;
	for(int i=0;i<a[temp.name].size();i++)
		if(!b[a[temp.name][i].name])
			if(temp.digit+a[temp.name][i].digit<dist[a[temp.name][i].name])
			{
				dist[a[temp.name][i].name]=temp.digit+a[temp.name][i].digit;
				u.push(node {a[temp.name][i].name,dist[a[temp.name][i].name]});
			}
}

---

Floyed

for(int k=1;k<=n;i++)
    for(int j=1;j<=n;j++)
        for(int i=1;i<=n;i++)
            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

---