Search code examples
algorithmgraphgraph-algorithmpath-finding

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?

Solution

  • 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