The performance results seem a little, uh, disingenuous? First, using a 4ary heap means the performance is closer to O((E+V)logV) instead of the E + VlogV you

The performance results seem a little, uh, disingenuous? First, using a 4ary heap means the performance is closer to O((E+V)logV) instead of the E + VlogV you can get using a Fibonacci heap. So it removes the drawback to the new method, which is that it goes from VlogV to ELog2/3 V. If you look at that term, it means the new method is only asymptotically faster when log1/3(n) > m/n, IF you're comparing to the actual VlogV version of Dijkstra's... For m/n = 3, that cutover is at about 140M nodes. Second, the "opt" seems to be applied only to the new method. There's no apples to apples comparison here.