2026-06-11 dijkstra doesn't hold

dijsktra doesn't hold

just as for today, a new paper popped up in my attention, stating something incredible: the dijkstra algorithm, which is the gold standard when it comes to finding the shortest path in a graph, is not optimal, contrary to what was stated before. the paper is here for everybody to look at: breaking the sorting barrier for directed single-source shortest paths i'm not gonna discuss the paper in detail, which would be a bit ridiculous, because it's not the topic i am firm with. this is another brilliant example, why in science, you shouldn't stop looking for better solutions if something is not prooven to be optimal. mathematics is the only science, where a proof can be 100% correct. as computer scientists, we are basically daughters of this proficion. but we still have so many things and assumptions about algorithms we think of as optimal, but efficiently they aren't. now, it took science 60 years to come up with a theoretical breakthrough for this seemingly trivial problem. i am glad to be alive to witness this.

back