# A* algorithm for finding shortest path in a graph

FindShortestPath finds the shortest path between two vertices in an edge-weighted graph, allowing a choice between the Dijkstra and Bellman-Ford algorithms. In my (limited) understanding, both of these algorithms fall into the breadth-first category.

My question is if there are accessible implementations of depth-first shortest path algorithms like A* for edge-weighted graphs in Mathematica.

I am aware of the question How to display each step of an A star algorithm?, but before delving into modifying that code so as to work with weighted graphs I wanted to make sure that I don't re-invent the wheel.

In fact, I haven't been able to locate an efficient implementation (using fancy data structures etc.) of A* for edge-weighted graphs in any programming language, but that would probably be a question for another site.

-
Unfortunately I don't think there is an easy solution. Mathematica still seems to fall a bit short on Path Algorithms. – Thomas Fankhauser Aug 7 '15 at 10:49
Could you please explain what this implementation would be able to do what FindShortestPath cannot already? – Szabolcs Oct 17 '15 at 21:34
Thanks for your comment @Szabolcs. I'm not a computer scientist, but when I wrote the question, my undertanding was that A star can have a better run time compexity on certain types of graphs than Dijstra or Bellman-Ford. I agree that it would likely not add functionality as such to FindShortestPath. – Eckhard Oct 18 '15 at 8:47