A new approach beats the classic algorithm taught in textbooks.
Forty years ago, researchers designing shortest-paths algorithms ran up against this “sorting barrier.” Now, a team of researchers has devised a new algorithm that breaks it(opens a new tab). It doesn’t sort, and it runs faster than any algorithm that does.
“The authors were audacious in thinking they could break this barrier,” said Robert Tarjan(opens a new tab), a computer scientist at Princeton University. “It’s an amazing result.”