As an alternative to Dijkstra's algorithm, we can employ DAG shortest paths.
It has a time complexity of O(|V| + |E|) compared to Dijkstra's O(|E|*log(|V|)).
This algorithm requires:
A directed acyclic graph (which we have)
The vertices to be sorted into topological order
As it turns out, with our ladder-esque graph structuring we have a topologically sorted vertex set already. Boost has an implementation, but I haven't tested it. It may have to run through a sort on an already sorted list first.
I have tested the algorithm in my own code (see #179), and it is a significant improvement to the search portion (5 - 10x) while taking less code / space.
As an alternative to Dijkstra's algorithm, we can employ DAG shortest paths.
It has a time complexity of
O(|V| + |E|)compared to Dijkstra'sO(|E|*log(|V|)).This algorithm requires:
As it turns out, with our ladder-esque graph structuring we have a topologically sorted vertex set already. Boost has an implementation, but I haven't tested it. It may have to run through a sort on an already sorted list first.
I have tested the algorithm in my own code (see #179), and it is a significant improvement to the search portion (5 - 10x) while taking less code / space.