3
$\begingroup$

Mathematica is incredibly powerful. More often than not, for whatever it is one wishes to do all the supporting functions already exist in Mathematica. This makes development incredibly quick and painless. However, sometimes Mathematica's abstraction can get in the way. A great example is FindPath.

There are a ton of questions about FindPath in as well as elsewhere on this site. Some are simple about use cases, but there are a handful of "modification" questions e.g. the question Restricting FindPath etc. using forbidden edge sequences. However the answer to such questions (answer to linked question) often rely on post processing modifications. This can be a bit sub-par.

One of the most common applications of path finding is to find the best (or k best) paths. Depending on the algorithm distance (generic weight) is used (as in Dijkstra's) and sometimes (or in addition to) a heuristic is used (as in A*). FindPath[g,s,t,kspec,n] returns n paths bounded by kspec and for weighted graphs, FindPath[g,s,t,k] gives all paths with total weights less than k.

What if I wanted to add a heuristic in addition to distance? I could convolve this into a new weight, but that is messy.

What if I wanted a dynamic heuristic as the weight?

To my knowledge neither of these are directly implementable with FindPath.

I can of course implement my own version of the corresponding path finding algorithm I wish. However, nothing I have tried is as fast as FindPath, especially when I want k best paths rather than just one.

I have tried variants of:

  • Finding Top K Shortest Simple Paths with Improved Space Efficiency
  • Eppstein k-best
  • A* and some of its many variants e.g. A* Prune
  • A K-Best Paths Algorithm for Highly Reliable Communication Networks
  • Ant colony / Bee sensor based approaches
  • bi-directional approaches
  • greedy variants of DFS and BFS (with and without max depth cut offs)
  • Yen's algorithm with Lawler's improvements

I am considering trying Yin and Yang, 2015. but given that FindPath was released with v10 (I think), the underlying algorithm is not likely to be something so recent...

So my question is as follows:

Either, how can I have a dynamic heuristic function in FindPath as the "weights" or what is the underlying algorithm of FindPath so I can implement a time efficient version with a dynamic heuristic function (which will of course dampen this time somewhat).

$\endgroup$

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.