Thorup's algorithm for single source shortest path for undirected graph has the time complexity O(m), lower than Dijkstra.
Basic ideas are the following. (Sorry, I didn't try implementing it yet, so I might miss some minor details. And the original paper is paywalled so I tried to reconstruct it fr...