Question

如何用C或C++编程实现Dijkstra算法求最短路径问题，不是求最短距离，而是将最短路径给出来

其中顶点个数应是任意数n，节点间边上的权自己赋

Answer 1

每次更新节点的最短路的时候，记录是由哪个节点更新过来的，求完最短路后，从终端回溯，直到始点
伪代码一下：
void GetMinDistPath()
{
int dist[nVertex]; //各个点到start_point的距离
int father[nVertex]; //记录是哪个节点更新过来的
int g[nVertex][nVertex]; //邻接矩阵存图，没有边记为infinity
bool vis[nVertex]; //是否已经确定最短路

read_graphy();

init_distance_as_infinity();
init_vis_as_false();

dist[start_point] = 0; vis[start_point] = true;
father[start_point] = -1;

for(int i = 1;i < nVertex;i ++) {
int u = get_not_vis_min_dist_point();
vis[u] = true;
for(int j = 0;j < nVertex;j ++)
if(dist[j] > dist[u] + g[u][j]) {
dist[j] = dist[u] + g[u][j];
father[j] = u; //更新father
}
}

//打印最短路径：start_point <--- end_point
for(int u = end_point;u != -1;u = father[u]) printf("%d ",u);
return;
}

Answer 2

大概是这样

我们不是有这样一个步骤吗
if(dist[u]+weight[u][v] < dist[v])
dist[v]=dist[u]+weight[u][v];
在这里加上一句，变成
if(dist[u]+weight[u][v] < dist[v])
{

dist[v]=dist[u]+weight[u][v];
path[v]=u;

}
之后沿着path数组一路找回来就可以了

Answer 3

同求

Answer 4

求最短路径的时候 同时记录最短路径的权值，这样就可以了吧。

有时间再用代码给出来。