What's the role of "overbuffer" in dijkstra algorithm source code?

asked 2021-04-06 10:06:26 -0500

Heho gravatar image

updated 2021-04-07 08:34:48 -0500

My understanding of the code is as follows:

  1. Instead of recording the shortest way, the algorithm will calculate the protential of cells in searching area and use the protential array to lead to the shorest path. As for protential, I think it is more about distance.
  2. The algorithm will calculate the protential array level by level, it just a little similar with BFS but it will backtrack to previous cells if it get a smaller potential value. And this job is token by currentbuff array and nextbuff array: current array will save the search cells and next array will save its neighbor cells (if it gets a lower protential).

The question is here! I could not understand what's the role of overbuffer array among the searching.

In line 203, if pot < threshold, the program will enter overflow section. "pot" is likely mean the minimum distance of this cell. And threshold was equals to lethal_cost in line 84.

The value of distance compare with a value of cell cost? I was totally run into chaos after this step.

So, what is the complete flow of the entire algorithm? Is there any deviation from what I understand?

In addition, in the calculatepotential function(line 65), what occasion does precise=ture apply?

Thank you!

edit retag flag offensive close merge delete