Is there an algorithm for finding the path of length k with the highest cost in a undirected graph

user_10712863 0
Viewed 120

I have been thinking about this problem for a few weeks but can't wrap my head around an efficient solution.

So basically imagine that you have a undirected graph where every node has a value assigned to it (only positive values). I want to find a path of length k (start and end node don't matter) that has, if you sum up the values of the visited nodes, the highest "cost". You can visit nodes only once.

Let's take this graph for example:

    d
    |
a - b - c
|   |
e - f

With the following values for the nodes:

a: 5
b: 10
c: 2
d: 3
e: 6
f: 7

The path with the highest cost with the length k=3 would be e-f-b, because the sum is 23.

I found a solution that solves this in O(n^k) time by basically finding every possible path for every node and then finding the one with the highest cost, but i think that there must be a more optimal solution.

graph-algorithm graph algorithm
1 Answers

Step1 Having the costs assigned to the nodes is awkward. The Dijsktra algorithm expects the costs to be on the links. So it would be good to transform the nodes to links and the links to nodes

(a,cost ac) -> (b,cost bc)

becomes

() - cost ac > () - cost bc > ()

Step2 Dijsktra calculates the lowest cost path. So you have recalculate every cost as

c = max cost - c

Step3 Now you can use Dijkstra to find the most expensive path

LOOP n1 over nodes
    Dijsktra
    LOOP n2 over nodes starting at n1 + 1
       IF n1 to n2 most expensive so far
           Save n1 to n2
user_165820
Related