Question about the optimality

[geass88]

Hi,
testing your implementation with the sample graph, I noticed that with tway the query: q 1 6 returns a result not great. I expected the path 1->2->4->6, instead I obtained 1->3->5->6.
While, testing the same query with astar returns the expected result.

[sroycode]

Thanks for pointing this out, I have changed the default heuristic function, please have a look.

[geass88]

The problem persist because if you run:
./test_astar ../data/sample.gr ../data/sample.co ../data/sample.p2p
and
./test_tway ../data/sample.gr ../data/sample.co ../data/sample.p2p
using the graph in sample.gr (not sample2.gr) you will obtain two different result:
[1 -> 6] - 1 - 2 - 4 - 6 //with astar
[1 -> 6] - 1 - 3 - 5 - 6 //with tway
I don't think it is an heuristic problem, but rather a problem in the termination condition (intersection found).

[sroycode]

Please uncomment the line
#define USE_MANHATTAN_DISTANCE 1
in TestProgram.cc
I am getting consistent result though not optimal

However, you are right in observing that this is presenting the first found path.