How to find Minimum Cost Path in a directed graph

Question

I was researching code about finding Minimum Cost Path in a directed graph online and I came across this code in geeksforgeeks here is the code.

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Stores minimum-cost of path from source
int minSum = INT_MAX;
 
// Function to Perform BFS on graph g
// starting from vertex v
void getMinPathSum(unordered_map<int,
                                 vector<pair<int,
                                             int> > >& graph,
                   vector<bool>& visited,
                   vector<int> necessary,
                   int source, int dest, int currSum)
{
    // If destination is reached
    if (source == dest) {
        // Set flag to true
        bool flag = true;
 
        // Visit all the intermediate nodes
        for (int i : necessary) {
 
            // If any intermediate node
            // is not visited
            if (!visited[i]) {
                flag = false;
                break;
            }
        }
 
        // If all intermediate
        // nodes are visited
        if (flag)
 
            // Update the minSum
            minSum = min(minSum, currSum);
        return;
    }
    else {
 
        // Mark the current node
        // visited
        visited = true;
 
        // Traverse adjacent nodes
        for (auto node : graph) {
            if (!visited[node.first]) {
 
                // Mark the neighbour visited
                visited[node.first] = true;
 
                // Find minimum cost path
                // considering the neighbour
                // as the source
                getMinPathSum(graph, visited,
                              necessary, node.first,
                              dest, currSum + node.second);
 
                // Mark the neighbour unvisited
                visited[node.first] = false;
            }
        }
 
        // Mark the source unvisited
        visited = false;
    }
}
 
// Driver Code
int main()
{
    // Stores the graph
    unordered_map<int, vector<pair<int,
                                   int> > >
        graph;
    graph[0] = { { 1, 2 }, { 2, 3 }, { 3, 2 } };
    graph[1] = { { 4, 4 }, { 0, 1 } };
    graph[2] = { { 4, 5 }, { 5, 6 } };
    graph[3] = { { 5, 7 }, { 0, 1 } };
    graph[4] = { { 6, 4 } };
    graph[5] = { { 6, 2 } };
    graph[6] = { { 7, 11 } };
 
    // Number of nodes
    int n = 7;
 
    // Source
    int source = 0;
 
    // Destination
    int dest = 6;
 
    // Keeps a check on visited
    // and unvisited nodes
    vector<bool> visited(n, false);
 
    // Stores intemediate nodes
    vector<int> necessary{ 2, 4 };
 
    getMinPathSum(graph, visited, necessary,
                  source, dest, 0);
 
    // If no path is found
    if (minSum == INT_MAX)
        cout << "-1\n";
    else
        cout << minSum << '\n';
    return 0;
}

but when the code is ran there were errors like this (this is just a small snipped of errors of the code)

main.cpp:68:19: error: no match for ‘operator=’ (operand types are ‘std::vector’ and ‘bool’)
main.cpp:60:45: error: no match for ‘operator+’ (operand types are ‘int’ and ‘std::vector >’)
main.cpp:46:19: error: no match for ‘operator=’ (operand types are ‘std::vector’ and ‘bool’)

Can someone show me how to fix this im not that good at debugging good

Tip: You can declare `graph` in one go, no need to fill it in manually like that. Also a `map` with an `int` key that uses sequential numbers starting at `0` is really just a `std::vector` with extra steps. — tadman, Mar 24 '21 at 23:10
Note: `vector` is so weird that it gets its own [documentation page](https://en.cppreference.com/w/cpp/container/vector_bool). Make sure it's the right choice for you. — user4581301, Mar 24 '21 at 23:20
Side note: Geeks for geeks has quality control issues. Some of the material's good, but it seems just as much will make you a worse programmer. My general rule of thumb is to treat any code that starts with [`#include `](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [`using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) as suspect and give it a much closer examination for correctness. — user4581301, Mar 24 '21 at 23:31
There's no need to add [solved]. Marking the answer accepted indicates that it's been solved. — Ryan M, Jun 23 '21 at 07:29

score 1 · Answer 1 · answered Mar 24 '21 at 23:14

1

The error is quite self-explanatory. 1st error: On line 68 you have

visited = false;

where you try to assign a bool to a vector<bool>. 3rd error too.

2nd error is that you try to add an integer and a vector of pairs.

answered Mar 24 '21 at 23:14

Yuren Huang

61
5

score 1 · Accepted Answer · answered Mar 24 '21 at 23:24

minPathSum is implemented incorrectly. Seems as if it was improperly refactored at some point and was not even attempted to be compiled.

The lone visited occurrences should be visited[source]. and for (auto node : graph) should be for (auto node : graph[source]). Altogether:

void getMinPathSum(unordered_map<int,
                                 vector<pair<int,
                                             int> > >& graph,
                   vector<bool>& visited,
                   vector<int> necessary,
                   int source, int dest, int currSum)
{
    // If destination is reached
    if (source == dest) {
        // Set flag to true
        bool flag = true;
 
        // Visit all the intermediate nodes
        for (int i : necessary) {
 
            // If any intermediate node
            // is not visited
            if (!visited[i]) {
                flag = false;
                break;
            }
        }
 
        // If all intermediate
        // nodes are visited
        if (flag)
 
            // Update the minSum
            minSum = min(minSum, currSum);
        return;
    }
    else {
 
        // Mark the current node
        // visited
        visited[source] = true;
 
        // Traverse adjacent nodes
        for (auto node : graph[source]) {
            if (!visited[node.first]) {
 
                // Mark the neighbour visited
                visited[node.first] = true;
 
                // Find minimum cost path
                // considering the neighbour
                // as the source
                getMinPathSum(graph, visited,
                              necessary, node.first,
                              dest, currSum + node.second);
 
                // Mark the neighbour unvisited
                visited[node.first] = false;
            }
        }
 
        // Mark the source unvisited
        visited[source] = false;
    }
}

Example

How to find Minimum Cost Path in a directed graph

2 Answers2