Historic Algorithms Help Unlock Shortest-Path Problem Breakthrough

Computer science pioneer Edsger Dijkstra's algorithms form the backbone of many computer subroutines, thanks to their elegant efficiency. However, seemingly subtle changes in requirements can lead to these often conceptually simple formulations failing to provide an accurate answer. The replacement algorithms provide the correct answers but are frequently orders of magnitude slower. A recent breakthrough in combinatorial techniques has shown how these early algorithms can be revived. Shortest-path problems provide good examples of the sensitivity of an algorithm to the specifics of their requirements.