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

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 = %.3fnt", 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时，它将其设置为&;visited&;同样，但它不是目的地，它再次在节点5和节点4上递归地调用该函数。现在你可以看到，节点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 = %.3fnt", 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;
}
}
}
}