Search code examples
c++graphbreadth-first-searchdijkstra

Finding the heaviest path of an undirected graph

I am trying to solve a particular problem but i cannot find any suitable solution. I'll explain ... 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. The peculiarity of this problem, however, is that I can only cross the same bridge once BUT it is possible to pass several times on the same node.

to be even more precise, if I have a graph of this type

enter image description here

Starting from the node 1, the solution I should get would be this : 1->2->0->1->4 with a total weight of 23.

I tried to apply known algorithms such as Dijkstra or Prime but I don't think they are the right solution. I couldn't find much on the internet. Is anyone able to provide me with any explanation or suggestions? Could thinking about coloring the arches and not the knots lead me to a solution in your opinion? A thousand thanks

Solution

  • I solved the problem using a dfs variant like this:

    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];
        path.push_back(u);
    }
    else {
        best = max(best, dp[u]);
        last_node = u;
    }
    return check;
}