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.