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  the weights per edge (making them negative instead of positive) and  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  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  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?