Schilcote
Schilcote

Reputation: 2394

Algorithm for finding cheapest path when effect of adding a node is unknown

I need to find the cheapest path between nodes a and b on a directed, weighted, cyclic graph, cheapest defined as eliciting the smallest return value from a given arbitrary costfunc. Normally Djikstra's would be the best choice I'd think, except costfunc takes an entire path - the effect of adding a single node is unknown (I suppose I could just run the costfunc with and without the given node and use the difference...).

How might I go about this?

Upvotes: 1

Views: 92

Answers (1)

user2512323
user2512323

Reputation:

Without some constraints on costfunc you can't do much better than trying every possible path. Suppose

costfunc = 1 / (sum of edge weights)

Then your problem (on cyclic graph) is NP hard Longest Path Problem.

And for

costfunc =
   sum of edge weights if path length = N
   infinity otherwise

you have well known NP complete Travelling salesman problem

Upvotes: 4

Related Questions