gonum / graph / 1455

67%

push

travis-ci

path: introduce an optimisation for function DijkstraFrom (proposal) (#196)

path: introduce an optimisation for function DijkstraFrom

If the distance is greater than the value stored in this distance node, then there already exist a better path to reach this node k. Indeed, the priority queue might contain several distanceNode for the same node k (each time it is updated), because this version of the dijkstra algorithm does not use a decrease-key operation. Therefore, these distanceNodes should be discarded. Otherwise, the adjacent vertices of k could be traversed more than once in the for loop.

7 of 7 new or added lines in 1 file covered. (100.0%)

4892 of 6024 relevant lines covered (81.21%)

3.72 hits per line