How to print the costs of all possible paths from a node to another?-CodePudding

I want to print all paths from source node to destination node, and the costs of these paths.

So far, I have the following code:

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

It works partially, correctly prints the paths and costs, until it needs to go back to the previous nodes. At this point, the program ends with an error code.

Here's an example of how it happens:

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)

The expected result would be for the algorithm to return to node 2, and search for the other paths from there. And then print the results like this:

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

Could anyone help me to solve this problem?

CodePudding user response：

the reason that it did not go back to node 2 was that the node 2 was set to "visited", and did not get the chance to set back to "not visited".

Based on your expected output, your graph should be something like this:


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

and that path you're looking for is from node 1 to node 5.

Now imagine, your code is currently checking node 3, it gets two adjacent nodes: node 5 and node 2, both are"not visited" yet. In the second "for loop", it recursively checks node 5 first, and great it is the destination node, so the code is out of the recursion and set node 5 to "not visited" (only node 5, not node 3). But when it comes to node 2, it sets it to "visited" as well, but it was not the destination, it calls the function again recursively on node 5 and node 4. Now you see, node 2 was never set back to "not visited" by your code, same as node 3 and node 4. Basically your code only set the node 5 back to "not visited".

so what you need to do is, after your recursive call of "search()", you have to set it back immediately.

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