Math
Najtańsza droga
Teren, w którym krok kosztuje cenę komórki, do której wchodzisz, a fala zamkniętych wierzchołków rozchodzi się po CENIE, nie po odległości. Suwak kładzie na mapie ujemną krawędź i ma trzy zmierzone zakresy.
Co się dzieje
Krok kosztuje tu cenę komórki, do której się wchodzi, więc fala zamkniętych wierzchołków nie rozchodzi się kołami: przez tanią nieckę biegnie daleko, o drogi grzbiet się zatrzymuje. Ten obraz to cała różnica między przeszukiwaniem wszerz a tym algorytmem. Dopóki wagi są nieujemne, odpowiedź jest dowodliwie najkrótsza i sprawdza się ją tu Bellmanem-Fordem zrelaksowanym do punktu stałego - nigdy drugim przebiegiem tego samego algorytmu - a na małych siatkach pełnym przeglądem ścieżek prostych. Na płaskim terenie koszt ma postać zamkniętą w(i + j), bo każda monotoniczna droga kosztuje tyle samo. Liczniki też są tożsamościami: każdy wierzchołek zamyka się dokładnie raz, każda krawędź relaksuje dokładnie raz, jest ich 4m(m−1). Potem suwak kładzie jedną skierowaną ujemną krawędź i ma trzy zakresy, wszystkie zmierzone, nie opisane. Do −15 nic się nie psuje: ujemna krawędź sama w sobie nie jest problemem. Od −16 do −50 Dijkstra odpowiada 93 tam, gdzie prawdą jest 92, potem 78, potem 58 - zawsze ZA DUŻO, bo zamkniętego wierzchołka się nie otwiera ponownie - a obok żółtej drogi pojawia się prawdziwa, żeby błąd było widać, a nie ogłoszony. Przy −51 powstaje ujemny cykl: najkrótszej drogi nie ma wcale, Bellman-Ford to mówi, a Dijkstra drukuje te same 93 bez mrugnięcia.
Równania modułu
Równania teren na siatce m x m, każda komórka ma cenę 1..9, krok kosztuje tyle, ile wynosi cena komórki, do której wchodzisz; start w lewym górnym rogu, cel w prawym dolnym przy wagach nieujemnych algorytm Dijkstry jest poprawny - sprawdzony względem algorytmu Bellmana-Forda relaksowanego do punktu stałego oraz, na 3x3 i 4x4, względem PEŁNEGO wyliczenia ścieżek prostych płaski teren ma postać zamkniętą: koszt do (i, j) = w(i + j), więc cel kosztuje w·2(m−1) - 120 dla w = 5, m = 13 zamknięte wierzchołki = m² (każdy zamykany dokładnie raz); relaksacje = krawędzie = 4m(m−1) = 624 przy m = 13; wstawienia do kopca 169 na terenie domyślnym domyślnie 13x13, zniżka wyłączona: najtańsza droga do celu 93, te same 93 z algorytmu Bellmana-Forda, 25 komórek na trasie, 0 komórek, w których oba wyniki się różnią jedna skierowana krawędź zniżkowa z (0,7) do (5,0), a suwak ma TRZY reżimy, wszystkie zmierzone: do −15: brak jakiegokolwiek błędu - ujemna krawędź sama w sobie nie jest problemem od −16 do −50: algorytm Dijkstry zwraca 93, podczas gdy prawda to 92, 78, 58 - zawsze ZA DUŻO, a odpowiedzi różnią się na 65, 122, 159 z 169 komórek −51 i niżej: ujemny cykl - nie istnieje najkrótsza ścieżka, algorytm Bellmana-Forda to stwierdza, a algorytm Dijkstry nadal wypisuje 93 końce krawędzi zniżkowej wybrano, wyliczając wszystkie pary: okno wymaga d(daleko) − d(blisko) < k < cost(blisko do daleko), a jest puste, gdy tania droga do dalekiej komórki prowadzi przez bliską
