Zastosowania algorytmu BFS
Algorytm Dijkstry: uogólnienie algorytmu BFS przeszukiwania grafu wszerz do grafów z wagami.
ASD240 - Algorytmy i struktury danych  p.2
Zastosowania algorytmu BFS
Algorytm Dijkstry: uogólnienie algorytmu BFS przeszukiwania grafu wszerz do grafów z wagami.
Dane:
graf skierowany G = (V, E) i funkcja wagowa w : E R+
(BFS: "e w(e) = 1)
ASD240 - Algorytmy i struktury danych  p.2
Zastosowania algorytmu BFS
Algorytm Dijkstry: uogólnienie algorytmu BFS przeszukiwania grafu wszerz do grafów z wagami.
Dane:
graf skierowany G = (V, E) i funkcja wagowa w : E R+
(BFS: "e w(e) = 1)
1 4
c
a
e
2
2
5
3
s
1
1 3
6
b
d f
2
2
ASD240 - Algorytmy i struktury danych  p.2
Zastosowania algorytmu BFS
Algorytm Dijkstry: uogólnienie algorytmu BFS przeszukiwania grafu wszerz do grafów z wagami.
Dane:
graf skierowany G = (V, E) i funkcja wagowa w : E R+
(BFS: "e w(e) = 1)
1 4
c
a
e
2
2
5
3
s
1
1 3
6
b
d f
2
2
Pytanie 1: Mając dane wierzchołki u i v, jaka jest
najkrótsza ścieżka z u do v?
ASD240 - Algorytmy i struktury danych  p.2
Zastosowania algorytmu BFS
Algorytm Dijkstry: uogólnienie algorytmu BFS przeszukiwania grafu wszerz do grafów z wagami.
Dane:
graf skierowany G = (V, E) i funkcja wagowa w : E R+
(BFS: "e w(e) = 1)
1 4
c
a
e
2
2
5
3
s
1
1 3
6
b
d f
2
2
Pytanie 1: Mając dane wierzchołki u i v, jaka jest
najkrótsza ścieżka z u do v?
Pytanie 2: Mając dany wierzchołek początkowy s, jaka
jest najkrótsza ścieżka z s do każdego z pozostałych
wierzchołków?
ASD240 - Algorytmy i struktury danych  p.2
Algorytm Dijkstry
Wejście: graf skierowany G = (V, E), wierzchołek
poczÄ…tkowy s, funkcja wagowa w : E R+
ASD240 - Algorytmy i struktury danych  p.3
Algorytm Dijkstry
Wejście: graf skierowany G = (V, E), wierzchołek
poczÄ…tkowy s, funkcja wagowa w : E R+
Dla ścieżki P = (v1, v2, . . . , vk) definiujemy jej długość (wagę)
k-1

w(P ) = w(vi, vi+1), najkrótsza ścieżka to ścieżka o
i=1
minimalnej wadze.
ASD240 - Algorytmy i struktury danych  p.3
Algorytm Dijkstry
Wejście: graf skierowany G = (V, E), wierzchołek
poczÄ…tkowy s, funkcja wagowa w : E R+
Dla ścieżki P = (v1, v2, . . . , vk) definiujemy jej długość (wagę)
k-1

w(P ) = w(vi, vi+1), najkrótsza ścieżka to ścieżka o
i=1
minimalnej wadze.
ASD240 - Algorytmy i struktury danych  p.3
Algorytm Dijkstry
Wejście: graf skierowany G = (V, E), wierzchołek
poczÄ…tkowy s, funkcja wagowa w : E R+
Dla ścieżki P = (v1, v2, . . . , vk) definiujemy jej długość (wagę)
k-1

w(P ) = w(vi, vi+1), najkrótsza ścieżka to ścieżka o
i=1
minimalnej wadze.
Cel: wyznaczyć najkrótsze ścieżki z s do każdego
wierzchołka w V \ {s}.
ASD240 - Algorytmy i struktury danych  p.3
Algorytm Dijkstry
Wejście: graf skierowany G = (V, E), wierzchołek
poczÄ…tkowy s, funkcja wagowa w : E R+
Dla ścieżki P = (v1, v2, . . . , vk) definiujemy jej długość (wagę)
k-1

w(P ) = w(vi, vi+1), najkrótsza ścieżka to ścieżka o
i=1
minimalnej wadze.
Cel: wyznaczyć najkrótsze ścieżki z s do każdego
wierzchołka w V \ {s}.
Struktura danych: KOLEJKA PRIORYTETOWA: priorytet zależy od
aktualnego przybliżenia odległości wierzchołków od
wierzchołka s
ASD240 - Algorytmy i struktury danych  p.3
Algorytm Dijkstry
Wejście: graf skierowany G = (V, E), wierzchołek
poczÄ…tkowy s, funkcja wagowa w : E R+
Dla ścieżki P = (v1, v2, . . . , vk) definiujemy jej długość (wagę)
k-1

w(P ) = w(vi, vi+1), najkrótsza ścieżka to ścieżka o
i=1
minimalnej wadze.
Cel: wyznaczyć najkrótsze ścieżki z s do każdego
wierzchołka w V \ {s}.
Struktura danych: KOLEJKA PRIORYTETOWA: priorytet zależy od
aktualnego przybliżenia odległości wierzchołków od
wierzchołka s
Algorytm odwiedza w pierwszej kolejności wierzchołek w
najbliższej odległości od s.
ASD240 - Algorytmy i struktury danych  p.3
Algorytm Dijkstry
Dijkstra(G = (V, E, w), s)
inicjalizuj pustÄ… kolejkÄ™ Q := "
for u " V - {s} do
d[u] := " odległość od s
d[s] := 0
Wstaw(s, Q)
while Q = " do

u :=Extract_MIN(Q) element minimalny z kolejki priorytetowej
oznacz(u)
for v " S[u] do
if v nieoznaczony i d[v] > d[u] + w(u, v) then
d[v] := d[u] + w(u, v)
Wstaw(v, Q)
ASD240 - Algorytmy i struktury danych  p.4
Algorytm Dijkstry - przykład
1 4
c
a
e
2
2
5
3
s
1
1 3
6
b
d f
2
2
ASD240 - Algorytmy i struktury danych  p.5
Algorytm Dijkstry - przykład
3
2
6
1 4
c
a
e
2
2
5
3
s
0
1
1 3
6
b
d f
2
2
4
6 5
ASD240 - Algorytmy i struktury danych  p.5
Algorytm Dijkstry - złożoność
Wykonuje następujące operacje:
Wstaw :|E| razy
Extract_MIN : |V | razy
ASD240 - Algorytmy i struktury danych  p.6
Algorytm Dijkstry - złożoność
Wykonuje następujące operacje:
Wstaw :|E| razy
Extract_MIN : |V | razy
Każda z nich zależy od implementacji kolejki priorytetowej Q
ASD240 - Algorytmy i struktury danych  p.6
Algorytm Dijkstry - złożoność
Wykonuje następujące operacje:
Wstaw :|E| razy
Extract_MIN : |V | razy
Każda z nich zależy od implementacji kolejki priorytetowej Q
Implementacja kolejki Q Extract_MIN Wstaw Razem
tablica O(n) O(1) O(n2)
kopiec O(log n) O(log n) O(m log n)
kopiec Fibonacciego* O(log n) O(1) O(n log n + m)
*nie omawiamy
ASD240 - Algorytmy i struktury danych  p.6
Algorytm Dijkstry - poprawność
Idea: Należy pokazać, że zawsze gdy wierzchołek u zostaje
oznaczony, d[u] jest najkrótszą odległością z s do u.
ASD240 - Algorytmy i struktury danych  p.7
Algorytm Dijkstry - poprawność
Idea: Należy pokazać, że zawsze gdy wierzchołek u zostaje
oznaczony, d[u] jest najkrótszą odległością z s do u. Niech
´(s, v) bÄ™dzie dÅ‚ugoÅ›ciÄ… najkrótszej Å›cieżki z s do v w G.
Fakt. "v " V (G) d[v] e" ´(s, v)
ASD240 - Algorytmy i struktury danych  p.7
Algorytm Dijkstry - poprawność
Idea: Należy pokazać, że zawsze gdy wierzchołek u zostaje
oznaczony, d[u] jest najkrótszą odległością z s do u. Niech
´(s, v) bÄ™dzie dÅ‚ugoÅ›ciÄ… najkrótszej Å›cieżki z s do v w G.
Fakt. "v " V (G) d[v] e" ´(s, v)
Dowód: na tablicy
ASD240 - Algorytmy i struktury danych  p.7
Ograniczenia algorytmu Dijkstry
Problematyczne dane wejściowe dla alg. Dijkstry - ujemne
wagi
ASD240 - Algorytmy i struktury danych  p.8
Ograniczenia algorytmu Dijkstry
Problematyczne dane wejściowe dla alg. Dijkstry - ujemne
wagi
a
2
3
-2
s
3
b
ASD240 - Algorytmy i struktury danych  p.8
Ograniczenia algorytmu Dijkstry
Problematyczne dane wejściowe dla alg. Dijkstry - ujemne
wagi
2
a
2
3
-2
s
0
3
b
3
ASD240 - Algorytmy i struktury danych  p.8
Ograniczenia algorytmu Dijkstry
Problematyczne dane wejściowe dla alg. Dijkstry - ujemne
wagi
2
a
2
3
-2
s
0
3
b
3
Wtedy alg. Dijkstry nie działa i trzeba zastosować inny algo-
rytm.
ASD240 - Algorytmy i struktury danych  p.8
Algorytm Dijkstry - podsumowanie
Jest to algorytm zachłanny.
ASD240 - Algorytmy i struktury danych  p.9
Algorytm Dijkstry - podsumowanie
Jest to algorytm zachłanny.
Cechy algorytmu zachłannego:
buduje rozwiązanie w małych krokach
w każdym kroku podejmuje decyzję optymalizując
pewne zadane kryterium
lokalnie optymalny krok prowadzi do wyznaczenia
globalnego optimum.
ASD240 - Algorytmy i struktury danych  p.9
Algorytm Dijkstry - podsumowanie
Jest to algorytm zachłanny.
Cechy algorytmu zachłannego:
buduje rozwiązanie w małych krokach
w każdym kroku podejmuje decyzję optymalizując
pewne zadane kryterium
lokalnie optymalny krok prowadzi do wyznaczenia
globalnego optimum.
tzw.  krok zachłanny to wybór nieodwiedzonego
wierzchołka, który znajduje się  najbliżej zbioru
wierzchołków już odwiedzonych z s
ASD240 - Algorytmy i struktury danych  p.9
Problem podróżującego komiwojażera
Komiwojażer chce odwiedzić dokładnie jeden raz każde spośród n miast i wrócić do punktu
wyjścia pokonując drogę o minimalnym koszcie.
ASD240 - Algorytmy i struktury danych  p.10
Problem podróżującego komiwojażera
Komiwojażer chce odwiedzić dokładnie jeden raz każde spośród n miast i wrócić do punktu
wyjścia pokonując drogę o minimalnym koszcie.
B
C
38
92
56
39
122
89
A
111
103
87
D
121
59
73
134
17
F E
67
ASD240 - Algorytmy i struktury danych  p.10
Problem podróżującego komiwojażera
Komiwojażer chce odwiedzić dokładnie jeden raz każde spośród n miast i wrócić do punktu
wyjścia pokonując drogę o minimalnym koszcie.
B
C
38
92
56
39
122
89
A
111
103
87
D
121
59
73
134
17
F E
67
Inaczej: pytamy o cykl zawierający wszystkie wierzchołki grafu (tzw. cykl Hamiltona) o
minimalnej wadze krawędzi.
ASD240 - Algorytmy i struktury danych  p.10
Problem podróżującego komiwojażera
Komiwojażer chce odwiedzić dokładnie jeden raz każde spośród n miast i wrócić do punktu
wyjścia pokonując drogę o minimalnym koszcie.
B
C
38
92
56
39
122
89
A
111
103
87
D
121
59
73
134
17
F E
67
Inaczej: pytamy o cykl zawierający wszystkie wierzchołki grafu (tzw. cykl Hamiltona) o
minimalnej wadze krawędzi.
Sprawdzając wszystkie cykle Hamiltona mamy 4!/2 możliwości.
ASD240 - Algorytmy i struktury danych  p.10
Problem podróżującego komiwojażera
Komiwojażer chce odwiedzić dokładnie jeden raz każde spośród n miast i wrócić do punktu
wyjścia pokonując drogę o minimalnym koszcie.
Inaczej: pytamy o cykl zawierający wszystkie wierzchołki grafu (tzw. cykl Hamiltona) o
minimalnej wadze krawędzi.
Sprawdzając wszystkie cykle Hamiltona mamy 4!/2 możliwości.
Ogólnie: (n - 1)!/2, a to jest bardzo duża liczba, dla n = 25 wynosi ok. 3, 1 × 1023, co
wymagałoby ok. 10 milionów lat obliczeń.
ASD240 - Algorytmy i struktury danych  p.10
Problem podróżującego komiwojażera
Komiwojażer chce odwiedzić dokładnie jeden raz każde spośród n miast i wrócić do punktu
wyjścia pokonując drogę o minimalnym koszcie.
Inaczej: pytamy o cykl zawierający wszystkie wierzchołki grafu (tzw. cykl Hamiltona) o
minimalnej wadze krawędzi.
Sprawdzając wszystkie cykle Hamiltona mamy 4!/2 możliwości.
Ogólnie: (n - 1)!/2, a to jest bardzo duża liczba, dla n = 25 wynosi ok. 3, 1 × 1023, co
wymagałoby ok. 10 milionów lat obliczeń.
Wielomianowy algorytm dla tego problemu nie jest znany, a problem jest NP-trudny, tzn.
znacznie trudniejszy niż wszystkie omawiane na tym wykładzie.
ASD240 - Algorytmy i struktury danych  p.10