学习日志_最短路径之标号法

吴文虎图论中的一个求最短路的方法

只需要O(ElogE)的时间复杂度就可以求出单源结点的所有最短路径, 实现的时候使用优先队列来维护可选的弧集,代码如下:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 110;
struct gnode;
vector<gnode> g[MAXN];
int mark[MAXN],d[MAXN];
struct gnode
{
	int v,val;
};
struct node
{
   int u,v;
   int dist;
   bool operator < (const node &n) const
   {
	   return dist>n.dist;
   }
};
void clear()
{
	for(int i=0;i<MAXN;i++)g[i].clear();
}
int shortest_way(int s,int n)
{
	memset(mark,0,sizeof(mark));
	memset(d,-1,sizeof(d));
	d[s]=0;
	mark[s]=1;
	priority_queue<node> PQ;
	node now;
	int i,cnt=0;
	for(i=0;i<g[s].size();i++)
	{
		now.u = s; now.v = g[s][i].v;
		now.dist = d[s]+g[s][i].val;
		PQ.push(now);
	}
	while(!PQ.empty())
	{
		do
		{
			if(PQ.empty())return cnt;
			now = PQ.top();
			PQ.pop();
			//cnt++;
		}while(mark[now.v]);
		//cout<<now.v<<endl;
		d[now.v] = now.dist;
		mark[now.v] = 1;int v = now.v;
		for(i=0;i<g[v].size();i++)
		{
			if(!mark[g[v][i].v]){
				now.u = v; now.v = g[v][i].v;
				now.dist = d[v]+g[v][i].val;
				PQ.push(now);
			}
		}
	}
	return 0;
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m),n||m)
	{
		clear();
		gnode gnow;
		for(int i=0;i<m;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			gnow.v = b; gnow.val = c;
			g[a].push_back(gnow);
			gnow.v = a; gnow.val = c;
			g[b].push_back(gnow);
		}
		int cnt = shortest_way(1,n);
		cout<<d[n]<<endl;
	}
	return 0;
}