Dijkstra 访问的第一个节点

Question

我正在用 C++ 实现 Dijkstra 程序，遇到一些问题，让我解释一下：

目前我一直在遵循以下代码： http://www.geeksforgeeks.org/printing-paths-dijkstras-shortest-path-algorithm/

此代码打印从源到所有其他顶点的完整路径。我正在使用数组 int parent[num_vertexs];存储路径。但问题是我不想要完整路径，只想要访问的第一个顶点。

如何才能只访问第一个节点？有什么方法可以只打印每个节点的父数组的第一个节点吗？

非常感谢您的宝贵时间。

编辑：我将向您展示我用于打印父数组的函数，其中包含从源顶点到所有其他顶点的完整路径。

void printPath(int parent[], int j){
// Base Case : If j is source
if (parent[j]==-1)
    return;

printPath(parent, parent[j]);

printf("%d ", j);

}

此函数打印完整路径，但我只想要路径的第一个顶点。问题是我不知道如何为每个顶点只打印第一个，因为 printf 指令打印完整路径。你能告诉我该怎么做吗？谢谢！

Answer 1

这个函数是递归的；它调用自己来打印除最后一个顶点之外的所有路径，然后打印最后一个顶点。将其限制为打印第一个顶点的简单粗暴的方法是排除其余部分：

void printFirstStep(int parent[], int j){
  // Base Case : If j is source
  if (parent[j]==-1)
    return;

  printFirstStep(parent, parent[j]);

  if (parent[parent[j]]==-1)
    printf("%d ", j);
}

更好的方法是将代码从递归更改为迭代（即非递归）：

void printFirstStep(int parent[], int j){
  // Base Case : If j is source
  if (parent[j]==-1)
    return;

  while(parent[parent[j]] != -1)
    j = parent[j];

    printf("%d ", j);
}

（从你的问题中不清楚你是否理解递归。请注意，如果你不理解这些函数，将它们粘贴到你的代码中是行不通的非常好。）

Dijkstra 访问的第一个节点

Dijkstra first node visited

c++

printing

path

dijkstra