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.

  • $\begingroup$ Unfortunately I don't think there is an easy solution. Mathematica still seems to fall a bit short on Path Algorithms. $\endgroup$ – Thomas Fankhauser Aug 7 '15 at 10:49
  • 1
    $\begingroup$ Could you please explain what this implementation would be able to do what FindShortestPath cannot already? $\endgroup$ – Szabolcs Oct 17 '15 at 21:34
  • $\begingroup$ 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. $\endgroup$ – Eckhard Oct 18 '15 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.