For decades, Dijkstra algorithm for finding the shortest paths was a fundamental “Textbook” algorithm.

Well, not (always) anymore.
A team of researchers from China have recently presented a new algorithm, that may, in some situation, have a smaller complexity.

The original algorithm finalizes paths “one at a time”, in a way that, effectively, sorts all of the edges. The new algorithm suggests running forward several steps each time, in a way that can finalize a few paths together. This way, one can get all of the paths finalized without fully sorting them — and, in some cases, reduce complexity.

The Dijkstra algorithm is still proven the be the best one for the general problem under any settings. But even though, this is a real breakthrough that changes the computer science textbooks.