Maximum cost path in an Undirected Graph such that no edge is visited twice

Viewed 189

I have a graph where each node has a numeric value. Starting from a node of my choice, I have to find the path where the sum of the node values is the heaviest. However I can only cross the same bridge once BUT it is possible to pass several times on the same node.

For example if I have a undirected graph like this:

EDGES 

    0 1 
    0 2 
    0 3
    1 2
    1 4

and each node have a weight like this:

Node  weight 
0    -> 4
1    -> 3
2    -> 7
3    -> 2
4    -> 9  

If I start from the source "1", the path's output should be like this 1->2->0->1->4 with total weight of 23.

I'm trying to solve this problem with DFS in this way:

int dfs(vector<vector<int> >& g, int* cost, int u, int pre)
{
    vis[u] = true;
    dp[u] = cost[u];
    bool check = 1;
 
    int cur = cost[u];
    for (auto& x : g[u]) {
        if (vis[x] && x != pre) {
            check = 0;
        } else if (!vis[x]) {
            check &= dfs(g, cost, x, u);
            cur = max(cur, cost[u] + dp[x]);
        }
    }

    dp[u] = cur;
 
    if (!check) { 
        canTake += cost[u];
    } else { 
        best = max(best, dp[u]);
    }
 
    return check;
}
 
int FindMaxCost(vector<vector<int> >& g,int* cost, int source)
{
    dfs(g, cost, source, -1);
    cout << canTake + best;
}
 

With this I can find the right total weight but I don't know how to save the right path.

I'm trying to take the path picking u-node in this code:

       if (!check) { 
            canTake += cost[u];
           // taking the u-node
        } else { 
            best = max(best, dp[u]);

          // taking here the last node in global variable 
        }

but the path is not correct.

0 Answers
Related