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

问题描述

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

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

我尝试过的事情:

因此，首先我们创建一个数组来维护每个节点的成本:

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?

推荐答案

不幸的是，此问题是NP-Complete.证明是通过简单地减少最长路径问题 https://en.wikipedia.org/wiki/Longest_path_problem对此.

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.

证明:
如果假设我们有一个可以在多项式时间内解决您的问题的算法.那就是找到两个节点之间的最长路径. t.然后，我们可以将该算法应用于每对节点(n(n ^ 2)次)，并获得多项式时间内最长路径问题的解决方案.

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.

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

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.

这篇关于使用DFS查找从s到t的最昂贵路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！