tree d1785ddfef62a25162fd05074e4b9164eff314c5
parent b9f237b10c25509064640dfd925b5c7b2774d596
author León Illanes <lillanes@cs.toronto.edu> 1602791610 -0400
committer bluss <bluss@users.noreply.github.com> 1610313949 +0100

Avoid some unnecessary re-visits in A*

Nodes can appear multiple times in the priority queue `visit_next`. To
guarantee the so-called runtime optimality (no other general algorithm
can visit fewer nodes than A* given the same information), we must check
that we re-visit a node if and only if we found a better path to it.
This commit adds a guard to ensure that we don't visit nodes for which
better paths have already been seen.

This also includes a test that counts the number of times `edge_cost` is
called throughout a run of `astar`. This serves as a proxy for the
number of nodes visited, which cannot be accessed directly.