Method for Determining the Shortest Path through a Network

A new method is presented for finding a path connecting two locations in a network of connections. The approach is different from methods such as Dijkstra (or the popular A* approach) and, depending on usage, shows several benefits over other methods. Though the approach does not guarantee that the best possible path is found in all cases, it provides a significant speed benefit under the assumption that the grid within which the path is to be found does not change frequently. The method allows for a step by step determination of the path without requiring that the full path be determined prior. As an additional benefit, it also allows determination of whether two locations are connected without calculating the path at all.

For cases where the speed is more important than the absolute accuracy of the path, this method shows significant benefits in both speed and accuracy over even the simplest algorithms such as Greedy (Best-First search) or similar approaches without the drawback of the possibility of the path becoming trapped by an enclosure. Determination of whether two locations are connected can be achieved by scalar comparison of one value within the matrix

Attached files:
MStar_WhitePaper.pdf

Patents:
US 10,063,462 issued 2018-08-28   [MORE INFO]

Type of Offer: Sale or Licensing



Next Patent »
« More Computer Science Patents
« More Optimization Patents

Share on      


CrowdSell Your Patent