establish edge ordering: edges in denser areas of the network are processed earlier
create empty octilinear grid graph
O and corresponding auxiliary graph
A
use edge ordering to iterate over edges; for each edge:
- find candidate nodes for start and endpoint (two disjoint sets S, T)
- make temporary changes to A edge costs
- find cheapest path S → T using A*
- undo temporary changes to A edge costs
- make permanent changes to A edge costs
