最短路问题路径还原

这里以dijkstra算法的路径还原为例，其他算法也可以用类似的方法进行最短路的还原。

//Dijkstra_002.cpp -- 最短路问题路径还原
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
typedef long long ll;
using namespace std;
typedef pair<int, int> P;
const int maxV = 1000 + 10;
const int maxE = 1000 + 10;
const int INF = 0x3f3f3f3f;
bool used[maxV];
struct edge{
	int to, cost;
};
int d[maxV], V, E;
vector<edge> G[maxV];
int prev[maxV];
void Dijkstra(int s)
{
	priority_queue<P, vector<P>, greater<P> > pque;
	fill(d, d+V, INF);
	memset(used, 0, sizeof(used));	// 优化算法
	memset(prev, -1, sizeof(prev));	// 初始化为-1。
	d[s] = 0;
	pque.push(P(0, s));
	while( !pque.empty() )
	{
		P p = pque.top();
		pque.pop();
		int v = p.second;
		if( used[v] || d[v]<p.first )
			continue;
		used[v] = 1;
		for( int i=0; i<G[v].size(); i++ )
		{
			edge e = G[v][i];
			if( !used[e.to] && d[e.to]>d[v]+e.cost )
			{
				d[e.to] = d[v] + e.cost;
				pque.push(P(d[e.to], e.to));
				prev[e.to] = v;
			}
		}
	}
}
// 要得到路径其实有多种方法，自己想下还有哪些。
vector<int> get_path(int t)
{
	vector<int> path;
	for( ; t!=-1; t=prev[t] )	// 不断沿着prev[t]走直到t=s
		path.push_back(t);
	// 这样得到的是按照t到s的顺序，所以翻转之
	reverse(path.begin(), path.end());	
	return path;
}
int main()
{
	while( cin>>V>>E && V )
	{
		int a, b, c;
		for( int i=0; i<V; i++ )
			G[i].clear();
		for( int i=0; i<E; i++ )
		{
			cin>>a>>b>>c;
			G[a].push_back((edge){b, c});
			G[b].push_back((edge){a, c});
		}
		Dijkstra(0);
		for( int i=1; i<V; i++ )
		{
			vector<int> k = get_path(i);
			for( int j=0; j<k.size(); j++ )
				cout<<k[j]<<endl;
		}
	}
	return 0;
}