(FunkyPathfinding is so much better! :-)

GraphSearchPal

An experimental/research GUI application for demonstrating pathfinding algorithms.

My aim is to come up with a definitive collection of pathfinding algorithms + minimum priority queue implementations and put them all under a single GUI application. The app allows users to draw their maze, set up the source/target nodes and choose the algorithm/heap combination after which the progress is displayed in real-time.

Pathfinding algorithms

• Dijkstra's algorithm
• Bidirectional Dijkstra's algorithm
• A*
• Bidirectional A*
• New Bidirectional A* (NBA*) [1]
• Parallel Bidirectional A* (PNBA*) [2], (works as expected on large graphs, yet fails on jUnit tests)

Priority queues

• BinomialHeap
• DaryHeap: this is the generalization of a binary heap (d = 2) that allows d children for each element in the heap.
• FibonacciHeap
• PairingHeap

References

• [1] Pijls, Wim and Post, Henk: Yet another bidirectional algorithm for shortest paths
• [2] Rios, Luis Henrique Oliveira and Chaimowicz, Luiz: A Parallel Bidirectional Heuristic Search Algorithm