这里以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;
}