CODEWITHSUNDEEP
javagraph-algorithm
Rafael Angarita
Rafael Angarita

Reputation: 787

How to find path with maximum cost

I have a directed graph whose vertices have costs. I would like to find the path with maximum cost between two vertices, but I have only found algorithms to solve the path with minimum cost.

Also, I'm using Java.

Upvotes: 2

Views: 2467

Answers (3)

sigalor
sigalor

Reputation: 1389

This is the Longest path problem, which (assuming you are looking for simple paths, i.e. paths in which no node is visited multiple times) is NP-hard, meaning that no algorithm that computes it in polynomial time exists unless P=NP. The proof for that is related to the Hamiltonian path problem, which is also NP-hard. Looking for paths that are not simple doesn't make much sense, because you could just keep looping through a cycle with positive cost, resulting in infinite total cost.

If you're sad about this fact, listen to this.

Yet, you have a directed acyclic graph (DAG), there is a method using topological sorting, which is explained in the linked Wikipedia article. This problem has to do with the Critical path method used for scheduling a set of project activities.

Upvotes: 1

Renato
Renato

Reputation: 13720

Just modify the evaluation function of the algorithm used. If for the shortest path, the function returns a greater value for shorter paths, in your case you would want to return a smaller value for shorter paths.

Upvotes: 1

calebds
calebds

Reputation: 26238

  1. Normalize all costs so that the minimum cost is greater than 0.
  2. Change all costs to (1/cost).
  3. Run minimum cost algorithm.

The resulting path is the maximum cost path on the original graph.

Upvotes: 3

Related Questions