Edsger Wybe Dijkstra ist tot

Der Informatikprofessor und Computerpionier Edsger Wybe Dijkstra ist im Alter von 72 Jahren gestorben. Er wurde berühmt durch einige der ersten Simulationen für Luftfahrt und Architektur. Aber auch viele andere heute selbstverständliche Anwendungen wie Routenplaner gehen auf seine Algorithmen zurück. Die Programmiersprache Algol, grundlegend unter anderem für Pascal, Basic und C, entstammte ebenfalls seinem Schaffen.

Geboren wurde Dijkstra am 11. Mai 1930 in Rotterdam, 1944 musste er das Land verlassen. Ein Jahr später kehrte er in die Niederlande zurück und nahm 1948 das Studium der Physik an der Uni Leiden auf. 1951 wurde er an der Uni Cambridge erstmals mit dem Programmier-Virus infiziert: Er arbeitete am EDSAC-Rechner, der am 6. Mai 1949 von Wilkes und Renwick fertig gestellt worden war. Es war der erste Computer, der das Programm und die Daten zusammen im Speicher ablegte und dort auch verändern konnte.

1956 begann Dijkstra seinen Doktor in Theoretischer Physik am Mathematical Centre in Amsterdam und nahm dort anschließend eine Vollzeitstelle an. Noch im selben Jahr veröffentlichte er erste wegweisende Arbeiten zum „Shortest Path“. Der nach ihm benannte Algorithmus wird noch heute von Navigationssystemen eingesetzt. Ein Jahr später heiratete Dijkstra. 1959 schloss er seine Promotion mit einer Arbeit zum „Real-Time Interrupt Handler“ ab.

1962 wurde der Niederländer Mathematik-Professor an der technischen Uni Eindhoven. In den folgenden zehn Jahren beschäftigte er sich mit dem „Dining Philosophers Problem“, „Bankers Algorithm“ zur Vermeidung von Deadlocks, „The Structure of the THE-Multiprogramming System“, „GoTo Statement Considered Harmful“ sowie „Notes on Structured“ und erhielt 1972 den ACM Turing Award. 1984 folgte er dem Ruf an die Uni Texas als Informatik- und Mathematik-Professor.

Heutige Routenplaner, wie sie auch im Internet als Dienste angeboten werden, dienen zur Berechnung eines gesuchten Weges zwischen zwei Orten. Natürlich ist dabei der kürzeste Weg am interessantesten. Dijkstras in den 50er Jahren vorgestellter Algorithmus, bestimmt diesen: Beim Dijkstra- oder Shortest Path-Algorithmus wird in jedem Knoten die zurückliegende Entfernung zum Startknoten gespeichert. Falls der Weg mitbestimmt werden soll, wird zusätzlich die Distanz zum dem am nächsten liegenden Vorgänger gespeichert. Wie bei der Tiefen- und Breitensuche in einer Baumstruktur werden die vom Startknoten aus gesehenen Nachbarn und wiederum deren Nachbarn rekursiv aufgesucht. Dabei wird jeweils die Distanzen durch Addition der Kantenlänge mit der Distanz des Vorgängers berechnet. Falls nun eine Distanz kleiner ist als eine vorher ermittelte, wird die größere von beiden überschrieben.