Dual Dijkstra search for planning multiple paths

摘要

The dual Dijkstra search for planning multiple paths is performed by: (1) calculating a first shortest cost from start to all nodes by utilizing an algorithm known as the Dijkstra algorithm; (2) calculating a second shortest cost from goal to all nodes by utilizing the Dijkstra algorithm; (3) summing up the first shortest cost and the second shortest cost to obtain a summed up shortest cost; and (4a) storing at all nodes the summed up shortest cost as a cost of shortest path from start to goal via respective nodes, or, (4b) obtaining at all nodes a shortest path from start to goal via respective nodes with reference to the summed up shortest cost, thereby searching a path from start to goal.