dijkstra和spfa求单源最短路径

[c++]代码库

#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>

using namespace std;

const int maxn = 500 + 5;
const int INF = 1e8;

struct Node
{
	int id;
	int dis;
	Node(int _id,int _dis):id(_id),dis(_dis){}
	bool operator < (const Node &b)const
	{
		return dis > b.dis;
	}
};

vector<Node> G[maxn];
int dis[maxn];
int vis[maxn];

void init()
{
	for(int i = 0;i < maxn;i++)
	{
		vis[i] = 0;
		dis[i] = INF;
		G[i].clear();
	}
}

void dijkstra(int v0)//找点，稠密图
{
	dis[v0] = 0;
	priority_queue<Node> pq;
	pq.push(Node(v0,0));
	while(!pq.empty())
	{
		Node ct = pq.top();
		pq.pop();
		if(vis[ct.id]) continue;
		vis[ct.id] = 1;
		for(int i = 0;i < G[ct.id].size();i++)
		{
			Node nt = G[ct.id][i];
			if(vis[nt.id]) continue;
			if(dis[nt.id] > dis[ct.id] + nt.dis)
			{
				dis[nt.id] = dis[ct.id] + nt.dis;
				pq.push(Node(nt.id,dis[nt.id]));
			}

		}
	}
}

void spfa(int v0)//找一遍边，稀疏图
{
	queue<int> q;
	q.push(v0);
	vis[v0] = 1;
	dis[v0] = 0;
	while(!q.empty())
	{
		int ct = q.front();
		q.pop();
		vis[ct] = 0;
		for(int i = 0;i < G[ct].size();i++)
		{
			Node nt = G[ct][i];
			if(dis[nt.id] > dis[ct] + nt.dis)
			{
				dis[nt.id] = dis[ct] + nt.dis;
				if(!vis[nt.id])
				{
					vis[nt.id] = 1;
					q.push(nt.id);
				}
			}
		}
	}
}


int main()
{
	int N,M;
	while(scanf("%d%d",&N,&M) != EOF)
	{
		init();
		for(int i = 0;i < M;i++)
		{
			int A,B,X;
			scanf("%d%d%d",&A,&B,&X);
			G[A].push_back(Node(B,X));
			G[B].push_back(Node(A,X));
		}
		int s,e;
		scanf("%d%d",&s,&e);
		//dijkstra(s);//78ms
		spfa(s);//0ms
		if(dis[e] != INF)
			printf("%d\n",dis[e]);
		else
			printf("-1\n");
	}
	return 0;
}

[源代码打包下载]