First, note that this complexity is actually worse for highly dense graphs, where `m` (number of edges) dominates rather than `n` (number of nodes) [note that a useful graph always has `m > n`, and often `m <= 2d n`, where `d` is the number of dimensions and the 2 is because we're using directed edges. Ugh, how do we compare log powers?].

Additionally, the `n` in the complexity only matters if for the Dijkstra approach you actually need a frontier of size proportional to `n` [remember that for open-grid-like graphs, the frontier is limited is limited to `sqrt(n)` for a plane, and for linear-ish graphs, the frontier is even more limited].

Also note that the "sorting barrier" only applies to comparison-based sorts, not e.g. various kinds of bucket sorts (which are easy to use when your weights are small integers). Which seems to be part of what this algorithm does, though I haven't understood it fully.