使用 DFS 找到从 s 到 t 的最昂贵路径

Question

在给定的图中 G=(V,E) 每条边都有一个成本 c(e)。我们有一个起始节点 s 和一个目标节点 t。我们如何使用以下 DFS 算法找到从 s 到 t 的最昂贵路径？

DFS(G,s):
    foreach v in V do
        color[v] <- white; parent[v] <- nil
    DFS-Visit(s)

DFS-Visit(u)
    color[u] <- grey
    foreach v in Adj[u] do
        if color[v] = white then 
            parent[v] = u; DFS-Visit(v)
    color[u] <- black

我尝试过的：

所以首先我们创建一个数组来维护每个节点的成本：

DFS(G,s,t):
    foreach v in V do
        color[v] <- white; parent[v] <- nil; cost[v] <- -inf
    DFS-Visit(s,t)
    return cost[t]

其次，如果它是灰色的，我们仍然应该访问一个节点事件来更新它的成本：

DFS-Visit(u,t)
    color[u] <- grey
    foreach v in Adj[u] do
        if color[v] != black then 
            parent[v] = u;
            if cost[u] < cost[v] + c(u,v) then
                cost[v] = cost[v] + c(u,v)
            if t != v then 
                DFS-Visit(v)
    color[u] <- black

而且我们不想通过 t。你怎么看？我的做法正确吗？

Answer 1

不幸的是，这个问题是 NP 完全的。证明是将最长路径问题 https://en.wikipedia.org/wiki/Longest_path_problem 简单地简化为这个。

证明：
如果假设我们有一个算法可以在多项式时间内解决您的问题。即找到两个节点 s & t 之间的最长路径。然后我们可以将此算法应用于每对节点（O(n^2) 次）并在多项式时间内获得最长路径问题的解决方案。

如果一个简单但效率极低的算法就足够了，那么您可以调整 DFS 算法，以便在每个节点上，以 所有排列顺序 对其相邻节点进行 DFS。跟踪每个订单获得的最低成本。

使用 DFS 找到从 s 到 t 的最昂贵路径

Find the most expensive path from s to t using DFS

algorithm

graph-theory

depth-first-search