The New Dijkstra’s Algorithm: Shortest Route from Data to Insights (and Action)?

LayoutIntroductionA practical perspective to the new reform in the “Shortest Path”Understanding the “Sorting Step:” The ProcessUnderstanding the Heap & the Bucket: The TechShortest Path from Data to Insights (& Actions): Drawing the ParallelShortest Path Architecture When Translated to Big Data SystemsCore PrincipleComponents (each exists to reduce distance)Algorithm Parallels / Architecture SpecificsZooming Into Some Algorithm Parallels / Architecture SpecificsFinding PivotsBounded Multi-Source Shortest PathArchitecture at a GlanceResearchers have finally found a faster way to run Dijkstra’s shortest path algorithm: something people thought couldn’t really be improved in a meaningful way. The paper, “Breaking the Sorting Barrier for Directed Single-Source Shortest Paths,” is a breakthrough for Modern Systems which still use a 70-year-old algorithm to “travel from point A to point B.”For decades, the “bottleneck” in Dijkstra’s algorithm has been the priority queue (the structure that decides which node to process next). The best known limit was O(m + n log n), where log n comes from sorting-like operations inside that queue. It was assumed this was the limit, that we couldn’t beat the “sorting barrier.