Algorytm Dijkstry

25.11.2009 - Krzysztof Nowicki
TrudnośćTrudność

Indukcja

 

Załóżmy, że mamy policzoną taką drogę dla pewnej grupy miast (białe miasta). Powiedzmy, że jest tych miast $ k $ oraz ponumerujmy je od 1 do $ k $. Miastu $ A $ dajmy numer 1 (oznaczenia te mam nadzieję pomogą ogarnąć całą tą indukcję) teraz każdemu sąsiadowi (czerwony zbiór) $ j $-tego miasta przypiszmy jakąś odległość od miasta 1. Będzie to najkrótsza droga po białych miastach, powiedzmy, że ma długość $ k $. Możemy go teraz traktować jako "sąsiada" $ A $ oddalonego o $ k $ i umieścić z tą odległością w czerwonym zbiorze. Weźmy teraz miasto o najmniejszej odległości od $ A $ (niebieskie), takie, które nie jest żadnym z miast ponumerowanych od 1 do $ k $, nazwijmy go $ H $. Jeśli się przyjrzeć tak bliżej temu miastu, to najkrótsza droga z miasta $ A $ do $ H $ ma właśnie taką długość jak obecnie obliczana droga z $ A $ do $ H $.

 

Dowód analogiczny (nie wprost)

Dowieść można tego analogicznie jak wcześniej dla miast $ A $ i $ X $. załóżmy, że istnieje inna droga do $ H $. jeśli prowadzi tylko przez miasta, które należą do białej grupy to znaleźlibyśmy właśnie tą drogę (bo jest krótsza), a jeśli prowadzi przez jakieś kolorowe miasto, to do tego miasta, przez które ta droga prowadzi, moglibyśmy dotrzeć krótszą drogą niż do $ H $. Jednak zdefiniowaliśmy $ H $ jako miasto, do którego można dotrzeć najkrótszą ścieżką z $ A $, które jeszcze nie zostało ponumerowane, więc nie może istnieć miasto kolorowe, do którego można dotrzeć krótszą drogą. Zatem długość drogi którą obecnie mamy policzoną z wierzchołka $ A $ do $ H $ faktycznie jest najkrótszą (jedną z najkrótszych) ścieżek z miasta $ A $ do $ H $.




Zatem mam kolejne $ k+1 $ białe miasto do którego znam moją odległość, a do zbioru czerwonych "sąsiadów" mogę dorzucić wszystkich bezpośrednich sąsiadów $ H $ z odległością &m& od $ A $ równą sumie odległości od $ A $ do $ H $ i długości bezpośredniej drogi do $ H $. Nie ma sensu jednak wrzucać od razu wszystkich bez namysłu. Jeśli popatrzę na takiego bezpośredniego sąsiada $ H $ (nazwę go $ M $) to nie zawsze warto go wrzucać do zbioru "sąsiadów".

-Jeżeli $ M $ należy do zbioru białych wierzchołków to nigdy nie musimy go wrzucać do czerwonych "sąsiadów", bo znamy już dla niego odpowiedź (czyli na pewno jest nie gorsza od naszej propozycji).

-Jeżeli $ M $ należy do zbioru czerwonych "sąsiadów" to musimy porównać długość drogi, którą mieliśmy dla niego już wcześniej z tą prowadzącą przez wierzchołek $ H $ i wybrać krótszą z nich jako kandydata na odległość od wierzchołka $ A $.  

-W pozostałych przypadkach nie mieliśmy propozycji odpowiedzi dla $ M $, więc wrzucamy $ M $ do czerwonych "sąsiadów" z odległością, którą policzyliśmy przez $ H $.

Możemy teraz postępować dalej, gdyż mamy $ k+1 $ miast o tej samej własności (odpowiedzi dla nich są poprawne) oraz pewien zbiór czerwonych "sąsiadów".

Jeśli nie ma już żadnych miast w zbiorze czerwonych "sąsiadów", dla których moglibyśmy obliczyć odległość, to nie ma już żadnych miast do których w ogóle możemy dojechać. Zatem obliczyliśmy drogi dla wszystkich miast, do których da się dojechać.

Otóż na samym początku aby uzyskać pewną spójność w całości rozumowania możemy powiedzieć, że ponumerowanych mamy 0 miast, jedynym znanym nam sąsiadem jest samo miasto $ A $ w odległości 0.Warto też mieć jakąś tablicę zawierającą odpowiedzi. Dla miasta $ A $ możemy od razu wpisać 0. O wszystkich pozostałych miastach nie wiemy, czy jest możliwość dojechania tam, czy nie, możemy myśleć o nich, że znajdują się nieskończenie daleko od naszego miasta (co z pewnych przyczyn jest wygodne później), więc do tabliczy odpowiedzi możemy im wpisać jakąś dużą liczbę udającą nieskończoność.

3.3
Twoja ocena: Brak Ocena: 3.3 (10 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com