如何打印从节点到另一个节点的所有可能路径的成本？

Question

我想打印从源节点到目标节点的所有路径以及这些路径的成本。

到目前为止，我有以下代码：

// Find all paths from source to destination.
void search(Graph* graph, int src, int dst)
{
    // Mark the current node and store it in path.
    graph->visited[src] = true;
    graph->path[graph->index] = src;
    graph->index++;

    // If current vertex is same as destination.
    if (src == dst)
    {
        for (int i = 0; i < graph->index; i++)
        {
            if (i != graph->index - 1)
            {
                printf("%d -> ", graph->path[i] + 1);
            }
            else
            {
                printf("%d = %.3f\n\t", graph->path[i] + 1, graph->distance);
            }
        }
    }
    else
    {
        // For all unvisited vertices adjacent to current vertex.
        for (Node* adj = graph->array[src]; adj; adj = adj->next)
        {
            if (!graph->visited[adj->vertex])
            {
                graph->distance += adj->weight;
                search(graph,adj->vertex, dst);
            }
        }
    }

    // Remove current vertex from path and mark it as unvisited.
    graph->index--;
    graph->distance -= graph->array[graph->index]->weight;
    graph->visited[src] = false;
}

它可以部分工作，正确打印路径和成本，直到需要返回到先前的节点为止。此时，程序以错误代码结束。

这是一个如何发生的示例：

Paths from 1 to 5:
        1 -> 3 -> 5 = 39.576
        1 -> 3 -> 2 -> 5 = 46.172
        1 -> 3 -> 2 -> 4 -> 5 = 52.768

Process finished with exit code -1073741819 (0xC0000005)

预期的结果将是算法返回节点2，并从那里搜索其他路径。然后打印这样的结果：

Paths from 1 to 5:
        1 -> 3 -> 5 = 39.576
        1 -> 3 -> 2 -> 5 = 46.172
        1 -> 3 -> 2 -> 4 -> 5 = 52.768
        1 -> 2 -> 5 = 39.576
        1 -> 2 -> 4 -> 5 = 46.172

Process finished with exit code 0

有人可以帮助我解决这个问题吗？

Answer 1

它没有回到节点2的原因是节点2被设置为“访问”，并且没有机会回到“未访问”。

基于您的预期输出，您的图应该是这样的：

   3 
 / | \
1  |  5
 \ |/  \
   2----4

您要查找的路径是从节点1到节点5。

现在，想象您的代码当前正在检查节点3，它获得了两个相邻的节点：节点5和节点2，都“尚未访问”。在第二个“ for循环”中，它首先递归检查节点5，很棒，它是目标节点，因此代码不在递归中，并将节点5设置为“未访问”（仅访问”（仅节点5，而不是节点3）。但是，当涉及节点2时，它也将其设置为“访问”，但它不是目的地，它在节点5和节点4上再次递归调用该功能。
现在您会看到，Node 2从未通过您的代码回到“未访问”，与节点3和节点4相同。基本上，您的代码仅将节点5设置为“未访问”。

因此，您需要做的是，在递归呼叫“ search（）”之后，您必须立即将其放回原处。

  void search(Graph* graph, int src, int dst){
    // Mark the current node and store it in path.
    graph->visited[src] = true;
    graph->path[graph->index] = src;
    graph->index++;

    // If current vertex is same as destination.
    if (src == dst)
    {
        for (int i = 0; i < graph->index; i++)
        {
            if (i != graph->index - 1)
            {
                printf("%d -> ", graph->path[i] + 1);
            }
            else
            {
                printf("%d = %.3f\n\t", graph->path[i] + 1, graph->distance);
            }
        }
    }
    else
    {
        // For all unvisited vertices adjacent to current vertex.
        for (Node* adj = graph->array[src]; adj; adj = adj->next)
        {
            if (!graph->visited[adj->vertex])
            {
                graph->distance += adj->weight;
                search(graph,adj->vertex, dst);
                graph->index--;
                graph->distance -= adj->weight;
                graph->visited[adj->vertex] = false;
            }
        }
    }
}