Haeupler, Hladík, Rozhoň, Tarjan und Tětek präsentieren 2024 neue Erkenntnisse über Dijkstras Algorithmus, indem sie erstmals ein für sequentielle Graphalgorithmen unübliches Komplexitätsmaß – universelle Optimalität – auf diesen klassischen SSSP-Algorithmus anwenden. Informell ausgedrückt ist ein Algorithmus universell optimal, wenn er für jede beliebige Graphtopologie die bestmögliche asymptotische Laufzeit erzielt. Sie entwickeln einen Heap mit dem sogenannten working-set property und beweisen, dass diese Implementierung von Dijkstras Algorithmus universell optimal bezüglich Laufzeit ist. Ihre Arbeit wird durch van der Hoog, Rotenberg und Rutschmann aufgegriffen. Sie entwickeln eine alternative Heap-Eigenschaft namens timestamp optimality und behaupten, dass ihr Heap-Design und ihr Beweis der Laufzeitoptimalität signifikant einfacher seien.

Diese Abschlussarbeit vergleicht die Heap-Designs und Beweisführung beider Paper, um der Frage nachzugehen, welcher der beiden Ansätze einfacher ist. Zur Formalisierung von Beweiseinfachheit führe ich eine Literaturrecherche über Introspektiven praktizierender Mathematiker:innen und Publikationen aus der Philosophie der Mathematik durch. Während van der Hoog, Rotenberg und Rutschmann die Frage nach der Einfachheit ihres Beweises an die Lesenden delegieren, ergibt meine strukturierte Analyse, dass ihr timestamp-Ansatz den entwickelten Einfachheitskriterien standhalten kann, und somit unser Verständnis von Dijkstras Algorithmus erweitert.