Math
Der billigste Weg
Gelände, in dem ein Schritt den Preis der betretenen Zelle kostet, und die Welle geschlossener Knoten breitet sich nach PREIS aus, nicht nach Entfernung. Ein Regler legt eine negative Kante aufs Feld und hat drei gemessene Bereiche.
Was passiert
Ein Schritt kostet hier den Preis der Zelle, die man betritt, also breitet sich die Welle geschlossener Knoten nicht in Kreisen aus: durch eine billige Senke läuft sie weit, an einem teuren Rücken bleibt sie stehen. Dieses Bild ist der ganze Unterschied zwischen der Breitensuche und diesem Verfahren. Solange die Gewichte nicht negativ sind, ist die Antwort beweisbar kürzest, und geprüft wird sie hier gegen Bellman-Ford bis zum Fixpunkt - nie gegen einen zweiten Lauf desselben Algorithmus - und auf kleinen Gittern gegen die vollständige Aufzählung einfacher Wege. Auf ebenem Gelände hat der Preis die geschlossene Form w(i + j), denn jeder monotone Weg kostet gleich viel. Auch die Zähler sind Identitäten: jeder Knoten wird genau einmal geschlossen, jede Kante genau einmal relaxiert, 4m(m−1) Stück. Dann legt der Regler eine einzelne gerichtete negative Kante aufs Feld, und sie hat drei Bereiche, alle gemessen statt behauptet. Bis −15 bricht nichts: eine negative Kante allein ist kein Problem. Von −16 bis −50 antwortet Dijkstra 93, wo die Wahrheit 92, dann 78, dann 58 lautet - immer ZU GROSS, weil ein geschlossener Knoten nie wieder geöffnet wird - und neben dem gelben Weg erscheint der wahre, damit der Fehler sichtbar ist statt bloß behauptet. Bei −51 entsteht ein negativer Kreis: es gibt gar keinen kürzesten Weg, Bellman-Ford sagt das, und Dijkstra druckt seelenruhig dieselben 93.
Gleichungen des Moduls
Gleichungen Gelände auf einem m x m Gitter, jede Zelle mit dem Preis 1..9, ein Schritt kostet den Preis der Zelle, die man betritt; Start oben links, Ziel unten rechts bei nichtnegativen Gewichten hat Dijkstra recht - geprüft gegen Bellman-Ford, bis zum Fixpunkt relaxiert, und auf 3x3 und 4x4 gegen eine VOLLSTÄNDIGE Aufzählung einfacher Wege ebenes Gelände hat eine geschlossene Form: Kosten bis (i, j) = w(i + j), das Ziel kostet also w·2(m−1) - 120 für w = 5, m = 13 abgeschlossene Knoten = m² (jeder genau einmal abgeschlossen); Relaxationen = Kanten = 4m(m−1) = 624 bei m = 13; Heap-Einfügungen 169 auf dem Standardgelände Standard 13x13, Rabatt aus: billigster Weg zum Ziel 93, dieselben 93 von Bellman-Ford, 25 Zellen im Weg, 0 Zellen, in denen die beiden nicht übereinstimmen eine gerichtete Rabattkante von (0,7) nach (5,0), und der Schieberegler hat DREI Bereiche, alle gemessen: bis hinunter zu −15: überhaupt kein Fehler - eine negative Kante ist für sich genommen kein Problem −16 bis −50: Dijkstra liefert 93, während die Wahrheit 92, 78, 58 ist - immer ZU GROSS, und die Antworten weichen auf 65, 122, 159 der 169 Zellen voneinander ab −51 und darunter: ein negativer Zyklus - es gibt keinen kürzesten Weg, Bellman-Ford sagt das, und Dijkstra gibt trotzdem 93 aus die Enden der Rabattkante wurden durch Aufzählung aller Paare gewählt: das Fenster braucht d(fern) − d(nah) < k < cost(nah nach fern), und es ist leer, wenn der billige Weg zur fernen Zelle durch die nahe führt
