代码之家 › 专栏 › 技术社区 › flowero

Dijkstra第一个访问的节点

dijkstra path printing c++

-2

flowero · 技术社区 · 8 年前

我正在用C++实现一个Dijkstra程序,我遇到了一些问题,让我解释一下:

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

此代码打印从源到所有其他顶点的完整路径。我使用数组int parent[num\u 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指令打印完整路径。你能告诉我怎么做吗?非常感谢。

1 回复 | 直到 8 年前

Beta 8 年前

该函数是递归的;它调用自身来打印除最后一个顶点以外的所有路径,然后打印最后一个顶点。将其限制为打印第一个顶点的简单而粗糙的方法是排除其余顶点:

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);
}

(从你的问题来看,你不清楚你是否理解递归。请注意,如果你不理解懂将这些函数粘贴到代码中对您没有多大好处。)