A* to find the longest path in a directed cyclic graph

Question

I have written an A* algorithm to find the shortest path through a directed cyclic graph. I am trying to modify it to find the longest path through the same graph.

My attempt was to write it so that all I change is [1] the weights per edge (making them negative instead of positive) and [2] the heuristic function.

I seem to be having trouble getting it to do this. It is pretty good at finding the longest path sometimes, but it is not guaranteed.

It seems that the problem lies with [2] the heuristic -- for shortest path an L2 norm is a good optimistic way to get it to head towards the goal, but for longest path I want the heuristic to point it at paths that are further from the goal to continue to increase total length.

If I set the heuristic to return 0 so that it's a Dijkstra's search, it's less predictable as there's no incentive to search from nodes further away (using [1] negative weights per edge).

I think if I keep the weights positive and try to maximize the score instead of minimize it may work, but I was attempting to do this without changing the algorithm, only the edge weights and the heurstic.

I have found similar posts on stackExchange but they don't answer my specific questions:

Q1) Can this be done with A*

Q2) Is setting the weights negative the right thing to do

Q3) Is the only way to do this is to set the heuristic to zero and keep the weights positive and try to maximize the score instead of minimize it?

Answer 1

First of all, bear in mind that the Longest Path Problem (LPP) is a NP-complete problem whereas finding the Shortest Path Problem (SPP) is a problem known to be in P. The proof for the NP-completeness of LPP is trivial and consists of a reduction from the Hamiltonian Circuit (HC) problem which is already known to be NP-complete.

In other words, if you could find a simple way (in the sense of the modifications taking only polynomial time) to modify A* to solve the LPP problem you would actually make a nice discovery! :)

This is not to say that A* can not be used, but it should be expected to take longer. I recently co-authored a paper about the "Target Value Search Problem" with other two people. This problem is stated as follows:

Given a graph $G(V,E)$ and a natural number $T$ find the path between the vertices $s, t\in V$ whose cost (or length in case of unary costs) is as close as possible to the given target value $T$.

Obviously, if $T=+\infty$ then you are seeking the longest path between any arbitrary pair of vertices, $s, t$. If, in addition, $s=t$ then you are looking for the longest path that joins both vertices. You can verify in $O(1)$ whether the length equals the number of vertices. If so, you found a Hamiltonian path.

Regarding your questions:

• Q1: Can this be done with $A^*$? Certainly yes (indeed, we modified A* to get T*, our implementation of the Target Value Search problem that can be used to solve this variant) but you should not expect for it to be as fast as when solving SPP. As a matter of fact, we provided a simple modification of A$^*$ that can be used to solve the LPP as well (and it is certainly complete but terribly inefficient)

• Q2: Is setting the weights negative the right thing to do? Well, the real problem is that you need a heuristic function that returns an upper bound on the path to the goal $t$ instead of a lower bound (as when solving the SPP) and these sort of heuristics seem particularly hard to derive (how would you do it? there is no concept such as "relaxation" here, maybe you should constraint the problem further to derive a heuristic)

• Q3: Is the only way to do this is to set the heuristic to zero and keep the weights positive and try to maximize the score instead of minimize it? Well, you can do it but that is just a brute-force approach. Note that this approach forces you to consider all paths. Even if you find a path which seems to be too large you are still forced to expand other nodes in OPEN until you CLOSE them all. In the absence of a heuristic that is all you can do. This is, indeed, what our variant of A* for the Target Value Search problem does if $T=+\infty$ ---however $T^*$ is more efficient even to solve LPP.

Hope this helps,