Graphen (Abstände Korrektheit )

	Leistet der Algorithmus von Moore denn auch immer das Verlangte? Das kann nur ein formaler Beweis beantworten.
Vorüberlegungen	Weil der Algorithmus von Moore auf der Breitensuche beruht, ist schon mal Folgendes klar: Für jeden Knoten w ist d(w) < genau dann, wenn w von v aus erreichbar ist. Für jeden Knoten w mit d(w) < ist d(w) die Länge eines Weges von v nach w. (Ein solcher Weg wird im Algorithmus mit den gemerkten Vorgängern auch aufgebaut.) Dass d(w) wirklich kleinstmöglich ist, muss noch gezeigt werden. Wir fügen dazu wieder Assertions in den Algorithmus ein. Dabei unterscheiden wir (zunächst) zwischen der berechneten Zahl d(w) und dem tatsächlichen Abstand a(w) von Knoten w von v. Wir wollen also zeigen: d(w) = a(w) für alle von v aus erreichbaren Knoten w, und wissen bereits a(w) ≤ d(w) für alle von v aus erreichbaren Knoten w.
und noch etwas	In dem Beweis muss es ja wohl darauf ankommen, dass D eine Queue ist. Um dies berücksichtigen zu können, nummerieren wir die Knoten entsprechend dem Zeitpunkt, zu dem sie entdeckt werden. Die Nummer bezeichnen wir mit t(v). Weil D eine Schlange ist, gilt dann stets Wird w aus D entnommen, so ist t(w) < t(x) für alle x in D.
bewege die Maus über die Assertions (bewege das Fenster so weit, dass du das gesamte gelbe Feld siehst)