Find the most expensive path from s to t using DFS

问题:

In a given graph G=(V,E) each edge has a cost c(e). We have a starting node s and a target node t. How can we find the most expensive path from s to t using following DFS algorithm?

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

What I have tried:

So first we create an array to maintain the cost to each node:

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]

Second we should still visit a node event if it is gray to update its cost:

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

and we don't want to go pass t. What do you think? Is my approach correct?

回答1:

Unfortunately this problem is NP-Complete. Proof is by a simple reduction of Longest Path Problem https://en.wikipedia.org/wiki/Longest_path_problem to this.

Proof:
If suppose we had an algorithm that could solve your problem in polynomial time. That is find longest path between two nodes s & t. We could then apply this algorithm for each pair of nodes (O(n^2) times) and obtain a solution for the Longest Path Problem in polynomial time.

If a simple but highly inefficient algorithm suffices, then you can adapt the DFS algorithm so that at each node, you conduct DFS of its adjacent nodes in all permuted orders. Keep track of the minimum cost obtained for each order.