寻找无向图的最重路径

Question

我正在尝试解决一个特定问题，但我找不到任何合适的解决方案。我会解释......我有一个图表，其中每个节点都有一个数值。从我选择的节点开始，我必须找到节点值之和最重的路径。然而，这个问题的特殊之处在于，我只能通过同一个桥一次，但可以在同一个节点上通过多次。

更准确地说，如果我有这种类型的图表

从节点1开始，我应该得到的解决方案是这样的： 1->2->0->1->4 总权重为23.

我尝试应用已知的算法，例如 Dijkstra 或 Prime，但我认为它们不是正确的解决方案。我在互联网上找不到太多。有谁能给我任何解释或建议吗？考虑给拱门上色而不是结上色是否可以让我找到你认为的解决方案？一千个感谢

Answer 1

我使用这样的 dfs 变体解决了这个问题：

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

寻找无向图的最重路径

Finding the heaviest path of an undirected graph

c++

graph

dijkstra

breadth-first-search