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

Answer 1

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

Answer 2

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.