Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Grafy c.d. cykl Eulera, algorytm Dijkstry i
Cykl Eulera
Bellmana-Forda
Wstęp
Istnienie
Wyznaczanie zajęcia 6.
Najkrótsze
ścieżki
Wstęp
Dijkstra
Bellman-Ford
Marcin Andrychowicz, Tomasz Kulczyński, Błażej
Osiński
Problem mostów królewieckich
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Mosty Graf
Bellmana-
Forda
3
Cykl Eulera
Wstęp
2 4
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
1
Wstęp
Dijkstra
Bellman-Ford
Cykl Eulera
Cykl Eulera to cykl, który przechodzi przez wszystkie
krawędzie grafu dokładnie raz.
Problem mostów królewieckich
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Mosty Graf
Bellmana-
Forda
3
Cykl Eulera
Wstęp
2 4
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
1
Wstęp
Dijkstra
Bellman-Ford
Cykl Eulera
Cykl Eulera to cykl, który przechodzi przez wszystkie
krawędzie grafu dokładnie raz.
Problem mostów królewieckich
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Mosty Graf
Bellmana-
Forda
3
Cykl Eulera
Wstęp
2 4
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
1
Wstęp
Dijkstra
Bellman-Ford
Cykl Eulera
Cykl Eulera to cykl, który przechodzi przez wszystkie
krawędzie grafu dokładnie raz.
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Przykład cyklu Eulera:
Forda
7
Cykl Eulera
6
Wstęp
Istnienie
1 2
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
Bellman-Ford
3 4
5
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Przykład cyklu Eulera:
Forda
7
Cykl Eulera
6
Wstęp
Istnienie
1 2
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
Bellman-Ford
3 4
5
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Przykład cyklu Eulera:
Forda
7
Cykl Eulera
6
Wstęp
Istnienie
1 2
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
Bellman-Ford
3 4
5
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Przykład cyklu Eulera:
Forda
7
Cykl Eulera
6
Wstęp
Istnienie
1 2
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
Bellman-Ford
3 4
5
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Przykład cyklu Eulera:
Forda
7
Cykl Eulera
6
Wstęp
Istnienie
1 2
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
Bellman-Ford
3 4
5
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Przykład cyklu Eulera:
Forda
7
Cykl Eulera
6
Wstęp
Istnienie
1 2
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
Bellman-Ford
3 4
5
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Przykład cyklu Eulera:
Forda
7
Cykl Eulera
6
Wstęp
Istnienie
1 2
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
Bellman-Ford
3 4
5
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Przykład cyklu Eulera:
Forda
7
Cykl Eulera
6
Wstęp
Istnienie
1 2
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
Bellman-Ford
3 4
5
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Przykład cyklu Eulera:
Forda
7
Cykl Eulera
6
Wstęp
Istnienie
1 2
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
Bellman-Ford
3 4
5
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Przykład cyklu Eulera:
Forda
7
Cykl Eulera
6
Wstęp
Istnienie
1 2
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
Bellman-Ford
3 4
5
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera
Pytania
Wstęp
Istnienie
Wyznaczanie
czy graf posiada cykl Eulera? (czy jest tzw.
Najkrótsze
eulerowski)
ścieżki
Wstęp
jak znalezć dowolny cykl Eulera?
Dijkstra
Bellman-Ford
Cykl Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera
Pytania
Wstęp
Istnienie
Wyznaczanie
czy graf posiada cykl Eulera? (czy jest tzw.
Najkrótsze
eulerowski)
ścieżki
Wstęp
jak znalezć dowolny cykl Eulera?
Dijkstra
Bellman-Ford
Czy graf posiada cykl Euler?
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Graf
Bellmana-
Forda
Dlaczego poniższy graf nie posiada cyklu Eulera?
3
Cykl Eulera
Wstęp
Istnienie
Wyznaczanie
2 4
Najkrótsze
ścieżki
Wstęp
1
Dijkstra
Bellman-Ford
Warunki konieczne:
parzystość stopni wierzchołków
spójność
Czy graf posiada cykl Euler?
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Graf
Bellmana-
Forda
Dlaczego poniższy graf nie posiada cyklu Eulera?
3
Cykl Eulera
Wstęp
Istnienie
Wyznaczanie
2 4
Najkrótsze
ścieżki
Wstęp
1
Dijkstra
Bellman-Ford
Warunki konieczne:
parzystość stopni wierzchołków
spójność
Czy graf posiada cykl Euler?
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Graf
Bellmana-
Forda
Dlaczego poniższy graf nie posiada cyklu Eulera?
3
Cykl Eulera
Wstęp
Istnienie
Wyznaczanie
2 4
Najkrótsze
ścieżki
Wstęp
1
Dijkstra
Bellman-Ford
Warunki konieczne:
parzystość stopni wierzchołków
spójność
Czy graf posiada cykl Euler?
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Graf
Bellmana-
Forda
Dlaczego poniższy graf nie posiada cyklu Eulera?
3
Cykl Eulera
Wstęp
Istnienie
Wyznaczanie
2 4
Najkrótsze
ścieżki
Wstęp
1
Dijkstra
Bellman-Ford
Warunki konieczne:
parzystość stopni wierzchołków
spójność
Czy graf posiada cykl Eulera?
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Podane warunki są dostateczne!
Cykl Eulera
Wstęp
Istnienie
dowód przez indukcję względem ilości krawędzi
Wyznaczanie
Najkrótsze baza: dla grafu bez krawędzi zachodzi
ścieżki
Wstęp
krok indukcyjny: zaczynamy z dowolnego wierzchołka v
Dijkstra
Bellman-Ford
i poruszamy się aż trafimy znów do v . . .
Czy graf posiada cykl Eulera?
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Podane warunki są dostateczne!
Cykl Eulera
Wstęp
Istnienie
dowód przez indukcję względem ilości krawędzi
Wyznaczanie
Najkrótsze baza: dla grafu bez krawędzi zachodzi
ścieżki
Wstęp
krok indukcyjny: zaczynamy z dowolnego wierzchołka v
Dijkstra
Bellman-Ford
i poruszamy się aż trafimy znów do v . . .
Czy graf posiada cykl Eulera?
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Podane warunki są dostateczne!
Cykl Eulera
Wstęp
Istnienie
dowód przez indukcję względem ilości krawędzi
Wyznaczanie
Najkrótsze baza: dla grafu bez krawędzi zachodzi
ścieżki
Wstęp
krok indukcyjny: zaczynamy z dowolnego wierzchołka v
Dijkstra
Bellman-Ford
i poruszamy się aż trafimy znów do v . . .
Dowód c.d.
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i
Bellmana- 7
Forda
6
1 2
Cykl Eulera
Wstęp
Istnienie
Wyznaczanie
3 4
Najkrótsze
ścieżki
Wstęp 5
Dijkstra
Bellman-Ford
Co dalej?
dlaczego trafiliśmy do v?
w pozostałej części grafu cykl Eulera istnieje
(7, 1, 2, 3, 4, 2, 7)
łączymy oba cykle (7, 5, 4, 6, 7, 1, 2, 3, 4, 2, 7)
Dowód c.d.
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i
Bellmana- 7
Forda
6
1 2
Cykl Eulera
Wstęp
Istnienie
Wyznaczanie
3 4
Najkrótsze
ścieżki
Wstęp 5
Dijkstra
Bellman-Ford
Co dalej?
dlaczego trafiliśmy do v?
w pozostałej części grafu cykl Eulera istnieje
(7, 1, 2, 3, 4, 2, 7)
łączymy oba cykle (7, 5, 4, 6, 7, 1, 2, 3, 4, 2, 7)
Dowód c.d.
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i
Bellmana- 7
Forda
6
1 2
Cykl Eulera
Wstęp
Istnienie
Wyznaczanie
3 4
Najkrótsze
ścieżki
Wstęp 5
Dijkstra
Bellman-Ford
Co dalej?
dlaczego trafiliśmy do v?
w pozostałej części grafu cykl Eulera istnieje
(7, 1, 2, 3, 4, 2, 7)
łączymy oba cykle (7, 5, 4, 6, 7, 1, 2, 3, 4, 2, 7)
Dowód c.d.
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i
Bellmana- 7
Forda
6
1 2
Cykl Eulera
Wstęp
Istnienie
Wyznaczanie
3 4
Najkrótsze
ścieżki
Wstęp 5
Dijkstra
Bellman-Ford
Co dalej?
dlaczego trafiliśmy do v?
w pozostałej części grafu cykl Eulera istnieje
(7, 1, 2, 3, 4, 2, 7)
łączymy oba cykle (7, 5, 4, 6, 7, 1, 2, 3, 4, 2, 7)
Dowód c.d.
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i
Bellmana- 7
Forda
6
1 2
Cykl Eulera
Wstęp
Istnienie
Wyznaczanie
3 4
Najkrótsze
ścieżki
Wstęp 5
Dijkstra
Bellman-Ford
Co dalej?
dlaczego trafiliśmy do v?
w pozostałej części grafu cykl Eulera istnieje
(7, 1, 2, 3, 4, 2, 7)
łączymy oba cykle (7, 5, 4, 6, 7, 1, 2, 3, 4, 2, 7)
Dowód c.d.
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i
Bellmana- 7
Forda
6
1 2
Cykl Eulera
Wstęp
Istnienie
Wyznaczanie
3 4
Najkrótsze
ścieżki
Wstęp 5
Dijkstra
Bellman-Ford
Co dalej?
dlaczego trafiliśmy do v?
w pozostałej części grafu cykl Eulera istnieje
(7, 1, 2, 3, 4, 2, 7)
łączymy oba cykle (7, 5, 4, 6, 7, 1, 2, 3, 4, 2, 7)
Dowód c.d.
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i
Bellmana- 7
Forda
6
1 2
Cykl Eulera
Wstęp
Istnienie
Wyznaczanie
3 4
Najkrótsze
ścieżki
Wstęp 5
Dijkstra
Bellman-Ford
Co dalej?
dlaczego trafiliśmy do v?
w pozostałej części grafu cykl Eulera istnieje
(7, 1, 2, 3, 4, 2, 7)
łączymy oba cykle (7, 5, 4, 6, 7, 1, 2, 3, 4, 2, 7)
Ścieżka Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Ścieżka Eulera
ŚcieżkaEulera ścieżka przechodząca przez każdą
Cykl Eulera
Wstęp krawędz dokładnie raz nie będąca cyklem
Istnienie
Wyznaczanie
graf musi być spójny
Najkrótsze
ścieżki
niech p i k będą początkiem i końcem ścieżki Eulera
Wstęp
Dijkstra
po dodaniu krawędzi łączącej p i k otrzymujemy graf
Bellman-Ford
eulerowski
zatem w grafie muszą istnieć dokładnie dwa wierzchołki
nieparzystego stopnia
Ścieżka Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Ścieżka Eulera
ŚcieżkaEulera ścieżka przechodząca przez każdą
Cykl Eulera
Wstęp krawędz dokładnie raz nie będąca cyklem
Istnienie
Wyznaczanie
graf musi być spójny
Najkrótsze
ścieżki
niech p i k będą początkiem i końcem ścieżki Eulera
Wstęp
Dijkstra
po dodaniu krawędzi łączącej p i k otrzymujemy graf
Bellman-Ford
eulerowski
zatem w grafie muszą istnieć dokładnie dwa wierzchołki
nieparzystego stopnia
Ścieżka Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Ścieżka Eulera
ŚcieżkaEulera ścieżka przechodząca przez każdą
Cykl Eulera
Wstęp krawędz dokładnie raz nie będąca cyklem
Istnienie
Wyznaczanie
graf musi być spójny
Najkrótsze
ścieżki
niech p i k będą początkiem i końcem ścieżki Eulera
Wstęp
Dijkstra
po dodaniu krawędzi łączącej p i k otrzymujemy graf
Bellman-Ford
eulerowski
zatem w grafie muszą istnieć dokładnie dwa wierzchołki
nieparzystego stopnia
Ścieżka Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Ścieżka Eulera
ŚcieżkaEulera ścieżka przechodząca przez każdą
Cykl Eulera
Wstęp krawędz dokładnie raz nie będąca cyklem
Istnienie
Wyznaczanie
graf musi być spójny
Najkrótsze
ścieżki
niech p i k będą początkiem i końcem ścieżki Eulera
Wstęp
Dijkstra
po dodaniu krawędzi łączącej p i k otrzymujemy graf
Bellman-Ford
eulerowski
zatem w grafie muszą istnieć dokładnie dwa wierzchołki
nieparzystego stopnia
Ścieżka Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Ścieżka Eulera
ŚcieżkaEulera ścieżka przechodząca przez każdą
Cykl Eulera
Wstęp krawędz dokładnie raz nie będąca cyklem
Istnienie
Wyznaczanie
graf musi być spójny
Najkrótsze
ścieżki
niech p i k będą początkiem i końcem ścieżki Eulera
Wstęp
Dijkstra
po dodaniu krawędzi łączącej p i k otrzymujemy graf
Bellman-Ford
eulerowski
zatem w grafie muszą istnieć dokładnie dwa wierzchołki
nieparzystego stopnia
Cykl Eulera w grafach skierowanych
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera Warunki konieczne:
Wstęp
Istnienie
z wierzchołka nr. 1 da się dojść do każdego innego
Wyznaczanie
Najkrótsze do każdego wierzchołka wchodzi tyle samo krawędzi ile
ścieżki
z niego wychodzi
Wstęp
Dijkstra
Bellman-Ford
powyższe warunki są dostateczne
Cykl Eulera w grafach skierowanych
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera Warunki konieczne:
Wstęp
Istnienie
z wierzchołka nr. 1 da się dojść do każdego innego
Wyznaczanie
Najkrótsze do każdego wierzchołka wchodzi tyle samo krawędzi ile
ścieżki
z niego wychodzi
Wstęp
Dijkstra
Bellman-Ford
powyższe warunki są dostateczne
Cykl Eulera w grafach skierowanych
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera Warunki konieczne:
Wstęp
Istnienie
z wierzchołka nr. 1 da się dojść do każdego innego
Wyznaczanie
Najkrótsze do każdego wierzchołka wchodzi tyle samo krawędzi ile
ścieżki
z niego wychodzi
Wstęp
Dijkstra
Bellman-Ford
powyższe warunki są dostateczne
Wyznaczanie cyklu Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda Wyznaczanie cyklu Eulera
umiemy już sprawdzić czy cykl Eulera istnieje, ale jak
Cykl Eulera
go znalezć?
Wstęp
Istnienie
Wyznaczanie
służy do tego algorytmFleury ego, który działa
Najkrótsze
trochę na zasadzie opisanego dowodu
ścieżki
Wstęp
działa zarówno dla grafów skierowanych jak i
Dijkstra
Bellman-Ford
nieskierowanych
jest rekurencyjny
zaczynamy od dowolnego wierzchołka
Wyznaczanie cyklu Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda Wyznaczanie cyklu Eulera
umiemy już sprawdzić czy cykl Eulera istnieje, ale jak
Cykl Eulera
go znalezć?
Wstęp
Istnienie
Wyznaczanie
służy do tego algorytmFleury ego, który działa
Najkrótsze
trochę na zasadzie opisanego dowodu
ścieżki
Wstęp
działa zarówno dla grafów skierowanych jak i
Dijkstra
Bellman-Ford
nieskierowanych
jest rekurencyjny
zaczynamy od dowolnego wierzchołka
Wyznaczanie cyklu Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda Wyznaczanie cyklu Eulera
umiemy już sprawdzić czy cykl Eulera istnieje, ale jak
Cykl Eulera
go znalezć?
Wstęp
Istnienie
Wyznaczanie
służy do tego algorytmFleury ego, który działa
Najkrótsze
trochę na zasadzie opisanego dowodu
ścieżki
Wstęp
działa zarówno dla grafów skierowanych jak i
Dijkstra
Bellman-Ford
nieskierowanych
jest rekurencyjny
zaczynamy od dowolnego wierzchołka
Wyznaczanie cyklu Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda Wyznaczanie cyklu Eulera
umiemy już sprawdzić czy cykl Eulera istnieje, ale jak
Cykl Eulera
go znalezć?
Wstęp
Istnienie
Wyznaczanie
służy do tego algorytmFleury ego, który działa
Najkrótsze
trochę na zasadzie opisanego dowodu
ścieżki
Wstęp
działa zarówno dla grafów skierowanych jak i
Dijkstra
Bellman-Ford
nieskierowanych
jest rekurencyjny
zaczynamy od dowolnego wierzchołka
Wyznaczanie cyklu Eulera
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda Wyznaczanie cyklu Eulera
umiemy już sprawdzić czy cykl Eulera istnieje, ale jak
Cykl Eulera
go znalezć?
Wstęp
Istnienie
Wyznaczanie
służy do tego algorytmFleury ego, który działa
Najkrótsze
trochę na zasadzie opisanego dowodu
ścieżki
Wstęp
działa zarówno dla grafów skierowanych jak i
Dijkstra
Bellman-Ford
nieskierowanych
jest rekurencyjny
zaczynamy od dowolnego wierzchołka
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Aby przetworzyć wierzchołek v:
dopóki istnieje krawędz z v:
Cykl Eulera
Wstęp
usuń tą krawędz i przetwórz wierzchołek do którego
Istnienie
Wyznaczanie
prowadziła
Najkrótsze
wypisz v
ścieżki
Wstęp
wypisane wierzchołki czytane w odwrotnej kolejności
Dijkstra
Bellman-Ford
tworzą cykl Eulera (pierwszy wierzchołek nie jest
powtórzony na końcu)
dlaczego to działa? popatrzmy na przykład
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Aby przetworzyć wierzchołek v:
dopóki istnieje krawędz z v:
Cykl Eulera
Wstęp
usuń tą krawędz i przetwórz wierzchołek do którego
Istnienie
Wyznaczanie
prowadziła
Najkrótsze
wypisz v
ścieżki
Wstęp
wypisane wierzchołki czytane w odwrotnej kolejności
Dijkstra
Bellman-Ford
tworzą cykl Eulera (pierwszy wierzchołek nie jest
powtórzony na końcu)
dlaczego to działa? popatrzmy na przykład
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Aby przetworzyć wierzchołek v:
dopóki istnieje krawędz z v:
Cykl Eulera
Wstęp
usuń tą krawędz i przetwórz wierzchołek do którego
Istnienie
Wyznaczanie
prowadziła
Najkrótsze
wypisz v
ścieżki
Wstęp
wypisane wierzchołki czytane w odwrotnej kolejności
Dijkstra
Bellman-Ford
tworzą cykl Eulera (pierwszy wierzchołek nie jest
powtórzony na końcu)
dlaczego to działa? popatrzmy na przykład
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Aby przetworzyć wierzchołek v:
dopóki istnieje krawędz z v:
Cykl Eulera
Wstęp
usuń tą krawędz i przetwórz wierzchołek do którego
Istnienie
Wyznaczanie
prowadziła
Najkrótsze
wypisz v
ścieżki
Wstęp
wypisane wierzchołki czytane w odwrotnej kolejności
Dijkstra
Bellman-Ford
tworzą cykl Eulera (pierwszy wierzchołek nie jest
powtórzony na końcu)
dlaczego to działa? popatrzmy na przykład
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Aby przetworzyć wierzchołek v:
dopóki istnieje krawędz z v:
Cykl Eulera
Wstęp
usuń tą krawędz i przetwórz wierzchołek do którego
Istnienie
Wyznaczanie
prowadziła
Najkrótsze
wypisz v
ścieżki
Wstęp
wypisane wierzchołki czytane w odwrotnej kolejności
Dijkstra
Bellman-Ford
tworzą cykl Eulera (pierwszy wierzchołek nie jest
powtórzony na końcu)
dlaczego to działa? popatrzmy na przykład
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Aby przetworzyć wierzchołek v:
dopóki istnieje krawędz z v:
Cykl Eulera
Wstęp
usuń tą krawędz i przetwórz wierzchołek do którego
Istnienie
Wyznaczanie
prowadziła
Najkrótsze
wypisz v
ścieżki
Wstęp
wypisane wierzchołki czytane w odwrotnej kolejności
Dijkstra
Bellman-Ford
tworzą cykl Eulera (pierwszy wierzchołek nie jest
powtórzony na końcu)
dlaczego to działa? popatrzmy na przykład
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Grafy c.d.
cykl Eulera,
Algorytm Fleury ego
algorytm
Dijkstry i
Bellmana-
7
Forda
6
Cykl Eulera
1 2
Wstęp
Istnienie
Wyznaczanie
Najkrótsze
ścieżki
Wstęp
Dijkstra
3 4
Bellman-Ford
5
Wyjście
7 2 4 3 2 1 7 6 4 5
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Usuwanie krawędzi
Cykl Eulera
dla macierzy sąsiedztwa łatwe
Wstęp
Istnienie
dla list sąsiedztwa:
Wyznaczanie
Najkrótsze
dla grafów skierowanych metodapop_back()
ścieżki
dla grafów nieskierowanych a co z krawędzią "w
Wstęp
Dijkstra
drugą stronę"?
Bellman-Ford
problem ten pominiemy do czasu aż poznamy klasę
set
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Usuwanie krawędzi
Cykl Eulera
dla macierzy sąsiedztwa łatwe
Wstęp
Istnienie
dla list sąsiedztwa:
Wyznaczanie
Najkrótsze
dla grafów skierowanych metodapop_back()
ścieżki
dla grafów nieskierowanych a co z krawędzią "w
Wstęp
Dijkstra
drugą stronę"?
Bellman-Ford
problem ten pominiemy do czasu aż poznamy klasę
set
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Usuwanie krawędzi
Cykl Eulera
dla macierzy sąsiedztwa łatwe
Wstęp
Istnienie
dla list sąsiedztwa:
Wyznaczanie
Najkrótsze
dla grafów skierowanych metodapop_back()
ścieżki
dla grafów nieskierowanych a co z krawędzią "w
Wstęp
Dijkstra
drugą stronę"?
Bellman-Ford
problem ten pominiemy do czasu aż poznamy klasę
set
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Usuwanie krawędzi
Cykl Eulera
dla macierzy sąsiedztwa łatwe
Wstęp
Istnienie
dla list sąsiedztwa:
Wyznaczanie
Najkrótsze
dla grafów skierowanych metodapop_back()
ścieżki
dla grafów nieskierowanych a co z krawędzią "w
Wstęp
Dijkstra
drugą stronę"?
Bellman-Ford
problem ten pominiemy do czasu aż poznamy klasę
set
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Usuwanie krawędzi
Cykl Eulera
dla macierzy sąsiedztwa łatwe
Wstęp
Istnienie
dla list sąsiedztwa:
Wyznaczanie
Najkrótsze
dla grafów skierowanych metodapop_back()
ścieżki
dla grafów nieskierowanych a co z krawędzią "w
Wstęp
Dijkstra
drugą stronę"?
Bellman-Ford
problem ten pominiemy do czasu aż poznamy klasę
set
Implementacja
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera
Wstęp
Istnienie Implementacja
Wyznaczanie
Implementacja algorytmu Fleury ego znajduje się w
Najkrótsze
ścieżki
notatkach.
Wstęp
Dijkstra
Bellman-Ford
Algorytm Fleury ego
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera
Wstęp
Analiza złożoności lista sąsiedztwa:
Istnienie
Wyznaczanie
Po każdej krawędzi przechodzimy dokładnie raz
Najkrótsze
ścieżki
złożoność O(|E|).
Wstęp
Dijkstra
Bellman-Ford
Grafy ważone
Grafy c.d.
cykl Eulera,
algorytm
Grafy ważone
Dijkstry i
Bellmana-
Forda grafemważonymlub inaczejsieciąnazywamy graf,
którego krawędzie posiadają w pewnym sensie
Cykl Eulera
"długości"
Wstęp
Istnienie
przykład grafu ważonego:
Wyznaczanie
6
Najkrótsze
41
ścieżki
1
Wstęp 29
Dijkstra
Bellman-Ford
5 32
45 21
51
29
4
38
36 32
3 50 2
Grafy ważone
Grafy c.d.
cykl Eulera,
algorytm
Grafy ważone
Dijkstry i
Bellmana-
Forda grafemważonymlub inaczejsieciąnazywamy graf,
którego krawędzie posiadają w pewnym sensie
Cykl Eulera
"długości"
Wstęp
Istnienie
przykład grafu ważonego:
Wyznaczanie
6
Najkrótsze
41
ścieżki
1
Wstęp 29
Dijkstra
Bellman-Ford
5 32
45 21
51
29
4
38
36 32
3 50 2
Grafy ważone
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera
Grafy ważone
Wstęp
Istnienie
Wyznaczanie
owe liczby będziemy nazywać wagą, długością albo
Najkrótsze
kosztem krawędzi
ścieżki
Wstęp
długość ścieżki to suma długości jej krawędzi
Dijkstra
Bellman-Ford
Grafy ważone
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera
Grafy ważone
Wstęp
Istnienie
Wyznaczanie
owe liczby będziemy nazywać wagą, długością albo
Najkrótsze
kosztem krawędzi
ścieżki
Wstęp
długość ścieżki to suma długości jej krawędzi
Dijkstra
Bellman-Ford
Najkrótsze ścieżki
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Pytania
Cykl Eulera
Wstęp
jaka jest najkrótsza ścieżka z wierzchołka v do w?
Istnienie
Wyznaczanie
jakie są najkrótsze ścieżki z wierzchołka v do
Najkrótsze
ścieżki
wszystkich pozostałych wierzchołków?
Wstęp
Dijkstra
jakie są najkrótsze ścieżki pomiędzy wszystkimi parami
Bellman-Ford
wierzchołków?
Najkrótsze ścieżki
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Pytania
Cykl Eulera
Wstęp
jaka jest najkrótsza ścieżka z wierzchołka v do w?
Istnienie
Wyznaczanie
jakie są najkrótsze ścieżki z wierzchołka v do
Najkrótsze
ścieżki
wszystkich pozostałych wierzchołków?
Wstęp
Dijkstra
jakie są najkrótsze ścieżki pomiędzy wszystkimi parami
Bellman-Ford
wierzchołków?
Najkrótsze ścieżki
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Pytania
Cykl Eulera
Wstęp
jaka jest najkrótsza ścieżka z wierzchołka v do w?
Istnienie
Wyznaczanie
jakie są najkrótsze ścieżki z wierzchołka v do
Najkrótsze
ścieżki
wszystkich pozostałych wierzchołków?
Wstęp
Dijkstra
jakie są najkrótsze ścieżki pomiędzy wszystkimi parami
Bellman-Ford
wierzchołków?
Najkrótsze ścieżki
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Najkrótsze ścieżki
Cykl Eulera
Wstęp zazwyczaj nie da się policzyć najkrótszej ścieżki z v do
Istnienie
Wyznaczanie w bez liczenia najkrótszych ścieżek z v do wszystkich
Najkrótsze
pozostałych wierzchołków
ścieżki
Wstęp
dlatego też skupimy się na liczeniu wszystkich
Dijkstra
Bellman-Ford
najkrótszych ścieżek z pojedynczego zródła (oznaczmy
je s)
Najkrótsze ścieżki
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Najkrótsze ścieżki
Cykl Eulera
Wstęp zazwyczaj nie da się policzyć najkrótszej ścieżki z v do
Istnienie
Wyznaczanie w bez liczenia najkrótszych ścieżek z v do wszystkich
Najkrótsze
pozostałych wierzchołków
ścieżki
Wstęp
dlatego też skupimy się na liczeniu wszystkich
Dijkstra
Bellman-Ford
najkrótszych ścieżek z pojedynczego zródła (oznaczmy
je s)
Najkrótsze ścieżki
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Zarys metody postępowania
Cykl Eulera
w każdej chwili obliczeń będziemy trzymali pewne
Wstęp
Istnienie
ścieżki z s do pozostałych wierzchołków
Wyznaczanie
Najkrótsze konkretniej będziemy trzymali 2 tablice:
ścieżki
Wstęp dis[v] długość najkrótszej znalezionej ścieżki z s do
Dijkstra
v
Bellman-Ford
ojc[v] ostatni nie licząc v wierzchołek na najkrótszej
ścieżce z s do v
Najkrótsze ścieżki
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Zarys metody postępowania
Cykl Eulera
w każdej chwili obliczeń będziemy trzymali pewne
Wstęp
Istnienie
ścieżki z s do pozostałych wierzchołków
Wyznaczanie
Najkrótsze konkretniej będziemy trzymali 2 tablice:
ścieżki
Wstęp dis[v] długość najkrótszej znalezionej ścieżki z s do
Dijkstra
v
Bellman-Ford
ojc[v] ostatni nie licząc v wierzchołek na najkrótszej
ścieżce z s do v
Najkrótsze ścieżki
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Zarys metody postępowania
Cykl Eulera
w każdej chwili obliczeń będziemy trzymali pewne
Wstęp
Istnienie
ścieżki z s do pozostałych wierzchołków
Wyznaczanie
Najkrótsze konkretniej będziemy trzymali 2 tablice:
ścieżki
Wstęp dis[v] długość najkrótszej znalezionej ścieżki z s do
Dijkstra
v
Bellman-Ford
ojc[v] ostatni nie licząc v wierzchołek na najkrótszej
ścieżce z s do v
Najkrótsze ścieżki
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Zarys metody postępowania
Cykl Eulera
w każdej chwili obliczeń będziemy trzymali pewne
Wstęp
Istnienie
ścieżki z s do pozostałych wierzchołków
Wyznaczanie
Najkrótsze konkretniej będziemy trzymali 2 tablice:
ścieżki
Wstęp dis[v] długość najkrótszej znalezionej ścieżki z s do
Dijkstra
v
Bellman-Ford
ojc[v] ostatni nie licząc v wierzchołek na najkrótszej
ścieżce z s do v
Sytuacja w trakcie obliczeń
Grafy c.d.
cykl Eulera,
Graf
algorytm
Dijkstry i
6
Bellmana-
41
Forda
1
29
Cykl Eulera
5 32
Wstęp
45 21
Istnienie
51
29
Wyznaczanie
4
38
Najkrótsze
ścieżki
36 32
Wstęp
Dijkstra
Bellman-Ford
3 50 2
Tablice
v 1 2 3 4 5 6
dis[v] 41 " " 73 29 0
ojc[v] 6 x x 1 6 x
Relaksacja krawędzi
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Relaksacja krawędzi
Forda
podstawową operacją w rozważanych algorytmach
Cykl Eulera
będzie relaksacja krawędzi
Wstęp
Istnienie
Wyznaczanie relaksacja krawędzi v w polega na sprawdzeniu, czy
Najkrótsze
przejście najkrótszą znaną ścieżką z s do v a
ścieżki
Wstęp następnie krawędzią z v do w nie daje krótszej ścieżki
Dijkstra
Bellman-Ford z s do w niż obecnie znana
if dis[v]+waga(v,w) < dis[w]
dis[w]=dis[v]+waga(v,w)
ojc[w]=v
Relaksacja krawędzi
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Relaksacja krawędzi
Forda
podstawową operacją w rozważanych algorytmach
Cykl Eulera
będzie relaksacja krawędzi
Wstęp
Istnienie
Wyznaczanie relaksacja krawędzi v w polega na sprawdzeniu, czy
Najkrótsze
przejście najkrótszą znaną ścieżką z s do v a
ścieżki
Wstęp następnie krawędzią z v do w nie daje krótszej ścieżki
Dijkstra
Bellman-Ford z s do w niż obecnie znana
if dis[v]+waga(v,w) < dis[w]
dis[w]=dis[v]+waga(v,w)
ojc[w]=v
Relaksacja krawędzi
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Relaksacja krawędzi
Forda
podstawową operacją w rozważanych algorytmach
Cykl Eulera
będzie relaksacja krawędzi
Wstęp
Istnienie
Wyznaczanie relaksacja krawędzi v w polega na sprawdzeniu, czy
Najkrótsze
przejście najkrótszą znaną ścieżką z s do v a
ścieżki
Wstęp następnie krawędzią z v do w nie daje krótszej ścieżki
Dijkstra
Bellman-Ford z s do w niż obecnie znana
if dis[v]+waga(v,w) < dis[w]
dis[w]=dis[v]+waga(v,w)
ojc[w]=v
Relaksacja krawędzi
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Relaksacja krawędzi
Forda
podstawową operacją w rozważanych algorytmach
Cykl Eulera
będzie relaksacja krawędzi
Wstęp
Istnienie
Wyznaczanie relaksacja krawędzi v w polega na sprawdzeniu, czy
Najkrótsze
przejście najkrótszą znaną ścieżką z s do v a
ścieżki
Wstęp następnie krawędzią z v do w nie daje krótszej ścieżki
Dijkstra
Bellman-Ford z s do w niż obecnie znana
if dis[v]+waga(v,w) < dis[w]
dis[w]=dis[v]+waga(v,w)
ojc[w]=v
Relaksacja krawędzi
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Relaksacja krawędzi
Forda
podstawową operacją w rozważanych algorytmach
Cykl Eulera
będzie relaksacja krawędzi
Wstęp
Istnienie
Wyznaczanie relaksacja krawędzi v w polega na sprawdzeniu, czy
Najkrótsze
przejście najkrótszą znaną ścieżką z s do v a
ścieżki
Wstęp następnie krawędzią z v do w nie daje krótszej ścieżki
Dijkstra
Bellman-Ford z s do w niż obecnie znana
if dis[v]+waga(v,w) < dis[w]
dis[w]=dis[v]+waga(v,w)
ojc[w]=v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Algorytm Dijkstry
Cykl Eulera pokażemy teraz najbardziej znany algorytm liczenia
Wstęp
najkrótszych ścieżek z pojedynczego zródła
Istnienie
Wyznaczanie
algorytmDijkstry
Najkrótsze
ścieżki
algorytm ten Działa tylko dla grafów o nieujemnych
Wstęp
Dijkstra
wagach krawędzi
Bellman-Ford
jest to założenie często spełnione, np. kiedy wagi
odpowiadają odległościom
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Algorytm Dijkstry
Cykl Eulera pokażemy teraz najbardziej znany algorytm liczenia
Wstęp
najkrótszych ścieżek z pojedynczego zródła
Istnienie
Wyznaczanie
algorytmDijkstry
Najkrótsze
ścieżki
algorytm ten Działa tylko dla grafów o nieujemnych
Wstęp
Dijkstra
wagach krawędzi
Bellman-Ford
jest to założenie często spełnione, np. kiedy wagi
odpowiadają odległościom
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Algorytm Dijkstry
Cykl Eulera pokażemy teraz najbardziej znany algorytm liczenia
Wstęp
najkrótszych ścieżek z pojedynczego zródła
Istnienie
Wyznaczanie
algorytmDijkstry
Najkrótsze
ścieżki
algorytm ten Działa tylko dla grafów o nieujemnych
Wstęp
Dijkstra
wagach krawędzi
Bellman-Ford
jest to założenie często spełnione, np. kiedy wagi
odpowiadają odległościom
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Algorytm Dijkstry
Forda
oznacz wszystkie wierzchołki jako nieodwiedzone
(vis[v] = false)
Cykl Eulera
Wstęp
Istnienie
dla każdego v " V ustaw dis[v] = "
Wyznaczanie
ustaw dis[s] = 0
Najkrótsze
ścieżki
Wstęp dopóki istnieje nieodwiedzony wierzchołek o
Dijkstra
skończonej odległości:
Bellman-Ford
niech v będzie wierzchołkiem nieodwiedzonym o
najmniejszej odległości
oznacz v jako odwiedzony
zrelaksuj wszystkie krawędzie wychodzące z v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Algorytm Dijkstry
Forda
oznacz wszystkie wierzchołki jako nieodwiedzone
(vis[v] = false)
Cykl Eulera
Wstęp
Istnienie
dla każdego v " V ustaw dis[v] = "
Wyznaczanie
ustaw dis[s] = 0
Najkrótsze
ścieżki
Wstęp dopóki istnieje nieodwiedzony wierzchołek o
Dijkstra
skończonej odległości:
Bellman-Ford
niech v będzie wierzchołkiem nieodwiedzonym o
najmniejszej odległości
oznacz v jako odwiedzony
zrelaksuj wszystkie krawędzie wychodzące z v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Algorytm Dijkstry
Forda
oznacz wszystkie wierzchołki jako nieodwiedzone
(vis[v] = false)
Cykl Eulera
Wstęp
Istnienie
dla każdego v " V ustaw dis[v] = "
Wyznaczanie
ustaw dis[s] = 0
Najkrótsze
ścieżki
Wstęp dopóki istnieje nieodwiedzony wierzchołek o
Dijkstra
skończonej odległości:
Bellman-Ford
niech v będzie wierzchołkiem nieodwiedzonym o
najmniejszej odległości
oznacz v jako odwiedzony
zrelaksuj wszystkie krawędzie wychodzące z v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Algorytm Dijkstry
Forda
oznacz wszystkie wierzchołki jako nieodwiedzone
(vis[v] = false)
Cykl Eulera
Wstęp
Istnienie
dla każdego v " V ustaw dis[v] = "
Wyznaczanie
ustaw dis[s] = 0
Najkrótsze
ścieżki
Wstęp dopóki istnieje nieodwiedzony wierzchołek o
Dijkstra
skończonej odległości:
Bellman-Ford
niech v będzie wierzchołkiem nieodwiedzonym o
najmniejszej odległości
oznacz v jako odwiedzony
zrelaksuj wszystkie krawędzie wychodzące z v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Algorytm Dijkstry
Forda
oznacz wszystkie wierzchołki jako nieodwiedzone
(vis[v] = false)
Cykl Eulera
Wstęp
Istnienie
dla każdego v " V ustaw dis[v] = "
Wyznaczanie
ustaw dis[s] = 0
Najkrótsze
ścieżki
Wstęp dopóki istnieje nieodwiedzony wierzchołek o
Dijkstra
skończonej odległości:
Bellman-Ford
niech v będzie wierzchołkiem nieodwiedzonym o
najmniejszej odległości
oznacz v jako odwiedzony
zrelaksuj wszystkie krawędzie wychodzące z v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Algorytm Dijkstry
Forda
oznacz wszystkie wierzchołki jako nieodwiedzone
(vis[v] = false)
Cykl Eulera
Wstęp
Istnienie
dla każdego v " V ustaw dis[v] = "
Wyznaczanie
ustaw dis[s] = 0
Najkrótsze
ścieżki
Wstęp dopóki istnieje nieodwiedzony wierzchołek o
Dijkstra
skończonej odległości:
Bellman-Ford
niech v będzie wierzchołkiem nieodwiedzonym o
najmniejszej odległości
oznacz v jako odwiedzony
zrelaksuj wszystkie krawędzie wychodzące z v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana- Algorytm Dijkstry
Forda
oznacz wszystkie wierzchołki jako nieodwiedzone
(vis[v] = false)
Cykl Eulera
Wstęp
Istnienie
dla każdego v " V ustaw dis[v] = "
Wyznaczanie
ustaw dis[s] = 0
Najkrótsze
ścieżki
Wstęp dopóki istnieje nieodwiedzony wierzchołek o
Dijkstra
skończonej odległości:
Bellman-Ford
niech v będzie wierzchołkiem nieodwiedzonym o
najmniejszej odległości
oznacz v jako odwiedzony
zrelaksuj wszystkie krawędzie wychodzące z v
Algorytm Dijkstry
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i 6
Bellmana- 41
1
Forda
29
29
5 32
Cykl Eulera
Wstęp
45 21
Istnienie
51
Wyznaczanie
4
38
Najkrótsze
ścieżki 36 32
Wstęp
Dijkstra
3 50 2
Bellman-Ford
Tablice
v 1 2 3 4 5 6
dis[v] " " " " " 0
ojc[v] x x x x x x
vis[v] 0 0 0 0 0 0
Algorytm Dijkstry
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i 6
Bellmana- 41
1
Forda
29
29
5 32
Cykl Eulera
Wstęp
45 21
Istnienie
51
Wyznaczanie
4
38
Najkrótsze
ścieżki 36 32
Wstęp
Dijkstra
3 50 2
Bellman-Ford
Tablice
v 1 2 3 4 5 6
dis[v] 41 " " " 29 0
ojc[v] 6 x x x 6 x
vis[v] 0 0 0 0 1 0
Algorytm Dijkstry
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i 6
Bellmana- 41
1
Forda
29
29
5 32
Cykl Eulera
Wstęp
45 21
Istnienie
51
Wyznaczanie
4
38
Najkrótsze
ścieżki 36 32
Wstęp
Dijkstra
3 50 2
Bellman-Ford
Tablice
v 1 2 3 4 5 6
dis[v] 41 " " 50 29 0
ojc[v] 6 x x 5 6 x
vis[v] 0 0 0 0 1 1
Algorytm Dijkstry
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i 6
Bellmana- 41
1
Forda
29
29
5 32
Cykl Eulera
Wstęp
45 21
Istnienie
51
Wyznaczanie
4
38
Najkrótsze
ścieżki 36 32
Wstęp
Dijkstra
3 50 2
Bellman-Ford
Tablice
v 1 2 3 4 5 6
dis[v] 41 92 " 50 29 0
ojc[v] 6 1 x 5 6 x
vis[v] 1 0 0 0 1 1
Algorytm Dijkstry
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i 6
Bellmana- 41
1
Forda
29
29
5 32
Cykl Eulera
Wstęp
45 21
Istnienie
51
Wyznaczanie
4
38
Najkrótsze
ścieżki 36 32
Wstęp
Dijkstra
3 50 2
Bellman-Ford
Tablice
v 1 2 3 4 5 6
dis[v] 41 82 86 50 29 0
ojc[v] 6 4 4 5 6 x
vis[v] 1 0 0 1 1 1
Algorytm Dijkstry
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i 6
Bellmana- 41
1
Forda
29
29
5 32
Cykl Eulera
Wstęp
45 21
Istnienie
51
Wyznaczanie
4
38
Najkrótsze
ścieżki 36 32
Wstęp
Dijkstra
3 50 2
Bellman-Ford
Tablice
v 1 2 3 4 5 6
dis[v] 41 82 86 50 29 0
ojc[v] 6 4 4 5 6 x
vis[v] 1 1 0 1 1 1
Algorytm Dijkstry
Grafy c.d.
Graf
cykl Eulera,
algorytm
Dijkstry i 6
Bellmana- 41
1
Forda
29
29
5 32
Cykl Eulera
Wstęp
45 21
Istnienie
51
Wyznaczanie
4
38
Najkrótsze
ścieżki 36 32
Wstęp
Dijkstra
3 50 2
Bellman-Ford
Tablice
v 1 2 3 4 5 6
dis[v] 41 82 86 50 29 0
ojc[v] 6 4 4 5 6 x
vis[v] 1 1 1 1 1 1
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Analiza złożoności listy sąsiedztwa:
Forda
złożoność pamięciowa O(|V | + |E|)
Cykl Eulera
każdą krawędz relaksujemy co najwyżej raz czas
Wstęp
Istnienie
O(|E|)
Wyznaczanie
Najkrótsze
O(|V |) razy wybieramy wierzchołek o najmniejszej
ścieżki
Wstęp odległości, co zajmuje jednorazowo czas O(|V |), czyli
Dijkstra
Bellman-Ford łącznie O(|V |2)
złożoność czasowa O(|V |2 + |E|) = O(|V |2)
da się tą złożoność poprawić, ale o tym będzie kiedy
indziej . . .
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Analiza złożoności listy sąsiedztwa:
Forda
złożoność pamięciowa O(|V | + |E|)
Cykl Eulera
każdą krawędz relaksujemy co najwyżej raz czas
Wstęp
Istnienie
O(|E|)
Wyznaczanie
Najkrótsze
O(|V |) razy wybieramy wierzchołek o najmniejszej
ścieżki
Wstęp odległości, co zajmuje jednorazowo czas O(|V |), czyli
Dijkstra
Bellman-Ford łącznie O(|V |2)
złożoność czasowa O(|V |2 + |E|) = O(|V |2)
da się tą złożoność poprawić, ale o tym będzie kiedy
indziej . . .
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Analiza złożoności listy sąsiedztwa:
Forda
złożoność pamięciowa O(|V | + |E|)
Cykl Eulera
każdą krawędz relaksujemy co najwyżej raz czas
Wstęp
Istnienie
O(|E|)
Wyznaczanie
Najkrótsze
O(|V |) razy wybieramy wierzchołek o najmniejszej
ścieżki
Wstęp odległości, co zajmuje jednorazowo czas O(|V |), czyli
Dijkstra
Bellman-Ford łącznie O(|V |2)
złożoność czasowa O(|V |2 + |E|) = O(|V |2)
da się tą złożoność poprawić, ale o tym będzie kiedy
indziej . . .
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Analiza złożoności listy sąsiedztwa:
Forda
złożoność pamięciowa O(|V | + |E|)
Cykl Eulera
każdą krawędz relaksujemy co najwyżej raz czas
Wstęp
Istnienie
O(|E|)
Wyznaczanie
Najkrótsze
O(|V |) razy wybieramy wierzchołek o najmniejszej
ścieżki
Wstęp odległości, co zajmuje jednorazowo czas O(|V |), czyli
Dijkstra
Bellman-Ford łącznie O(|V |2)
złożoność czasowa O(|V |2 + |E|) = O(|V |2)
da się tą złożoność poprawić, ale o tym będzie kiedy
indziej . . .
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Analiza złożoności listy sąsiedztwa:
Forda
złożoność pamięciowa O(|V | + |E|)
Cykl Eulera
każdą krawędz relaksujemy co najwyżej raz czas
Wstęp
Istnienie
O(|E|)
Wyznaczanie
Najkrótsze
O(|V |) razy wybieramy wierzchołek o najmniejszej
ścieżki
Wstęp odległości, co zajmuje jednorazowo czas O(|V |), czyli
Dijkstra
Bellman-Ford łącznie O(|V |2)
złożoność czasowa O(|V |2 + |E|) = O(|V |2)
da się tą złożoność poprawić, ale o tym będzie kiedy
indziej . . .
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dlaczego to działa?
Dijkstry i
Bellmana-
Forda po rozpatrzeniu v wartość dis[v] już się nie zmieni, bo
rozpatrujemy wierzchołki coraz bardziej odległe od s
Cykl Eulera
udowodnimy, że w momencie odwiedzania v najkrótsza
Wstęp
Istnienie
ścieżka z s do v ma długość dis[v]:
Wyznaczanie
dowód przez indukcję "w czasie"
Najkrótsze
ścieżki
baza w momencie wejścia do s zachodzi dis[s] = 0
Wstęp
Dijkstra krok indukcyjny załóżmy, że odwiedzamy v:
Bellman-Ford
najkrótsza ścieżka do v musi biec tylko przez już
odwiedzone wierzchołki, bo v ma najniższą wartość w
tablicy dis spośród nieodwiedzonych wierzchołków
jest więc ona postaci (s, x1, . . . , xn, v) dla odwiedzonych
xi
rozważyliśmy ją relaksując krawędz xn v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dlaczego to działa?
Dijkstry i
Bellmana-
Forda po rozpatrzeniu v wartość dis[v] już się nie zmieni, bo
rozpatrujemy wierzchołki coraz bardziej odległe od s
Cykl Eulera
udowodnimy, że w momencie odwiedzania v najkrótsza
Wstęp
Istnienie
ścieżka z s do v ma długość dis[v]:
Wyznaczanie
dowód przez indukcję "w czasie"
Najkrótsze
ścieżki
baza w momencie wejścia do s zachodzi dis[s] = 0
Wstęp
Dijkstra krok indukcyjny załóżmy, że odwiedzamy v:
Bellman-Ford
najkrótsza ścieżka do v musi biec tylko przez już
odwiedzone wierzchołki, bo v ma najniższą wartość w
tablicy dis spośród nieodwiedzonych wierzchołków
jest więc ona postaci (s, x1, . . . , xn, v) dla odwiedzonych
xi
rozważyliśmy ją relaksując krawędz xn v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dlaczego to działa?
Dijkstry i
Bellmana-
Forda po rozpatrzeniu v wartość dis[v] już się nie zmieni, bo
rozpatrujemy wierzchołki coraz bardziej odległe od s
Cykl Eulera
udowodnimy, że w momencie odwiedzania v najkrótsza
Wstęp
Istnienie
ścieżka z s do v ma długość dis[v]:
Wyznaczanie
dowód przez indukcję "w czasie"
Najkrótsze
ścieżki
baza w momencie wejścia do s zachodzi dis[s] = 0
Wstęp
Dijkstra krok indukcyjny załóżmy, że odwiedzamy v:
Bellman-Ford
najkrótsza ścieżka do v musi biec tylko przez już
odwiedzone wierzchołki, bo v ma najniższą wartość w
tablicy dis spośród nieodwiedzonych wierzchołków
jest więc ona postaci (s, x1, . . . , xn, v) dla odwiedzonych
xi
rozważyliśmy ją relaksując krawędz xn v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dlaczego to działa?
Dijkstry i
Bellmana-
Forda po rozpatrzeniu v wartość dis[v] już się nie zmieni, bo
rozpatrujemy wierzchołki coraz bardziej odległe od s
Cykl Eulera
udowodnimy, że w momencie odwiedzania v najkrótsza
Wstęp
Istnienie
ścieżka z s do v ma długość dis[v]:
Wyznaczanie
dowód przez indukcję "w czasie"
Najkrótsze
ścieżki
baza w momencie wejścia do s zachodzi dis[s] = 0
Wstęp
Dijkstra krok indukcyjny załóżmy, że odwiedzamy v:
Bellman-Ford
najkrótsza ścieżka do v musi biec tylko przez już
odwiedzone wierzchołki, bo v ma najniższą wartość w
tablicy dis spośród nieodwiedzonych wierzchołków
jest więc ona postaci (s, x1, . . . , xn, v) dla odwiedzonych
xi
rozważyliśmy ją relaksując krawędz xn v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dlaczego to działa?
Dijkstry i
Bellmana-
Forda po rozpatrzeniu v wartość dis[v] już się nie zmieni, bo
rozpatrujemy wierzchołki coraz bardziej odległe od s
Cykl Eulera
udowodnimy, że w momencie odwiedzania v najkrótsza
Wstęp
Istnienie
ścieżka z s do v ma długość dis[v]:
Wyznaczanie
dowód przez indukcję "w czasie"
Najkrótsze
ścieżki
baza w momencie wejścia do s zachodzi dis[s] = 0
Wstęp
Dijkstra krok indukcyjny załóżmy, że odwiedzamy v:
Bellman-Ford
najkrótsza ścieżka do v musi biec tylko przez już
odwiedzone wierzchołki, bo v ma najniższą wartość w
tablicy dis spośród nieodwiedzonych wierzchołków
jest więc ona postaci (s, x1, . . . , xn, v) dla odwiedzonych
xi
rozważyliśmy ją relaksując krawędz xn v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dlaczego to działa?
Dijkstry i
Bellmana-
Forda po rozpatrzeniu v wartość dis[v] już się nie zmieni, bo
rozpatrujemy wierzchołki coraz bardziej odległe od s
Cykl Eulera
udowodnimy, że w momencie odwiedzania v najkrótsza
Wstęp
Istnienie
ścieżka z s do v ma długość dis[v]:
Wyznaczanie
dowód przez indukcję "w czasie"
Najkrótsze
ścieżki
baza w momencie wejścia do s zachodzi dis[s] = 0
Wstęp
Dijkstra krok indukcyjny załóżmy, że odwiedzamy v:
Bellman-Ford
najkrótsza ścieżka do v musi biec tylko przez już
odwiedzone wierzchołki, bo v ma najniższą wartość w
tablicy dis spośród nieodwiedzonych wierzchołków
jest więc ona postaci (s, x1, . . . , xn, v) dla odwiedzonych
xi
rozważyliśmy ją relaksując krawędz xn v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dlaczego to działa?
Dijkstry i
Bellmana-
Forda po rozpatrzeniu v wartość dis[v] już się nie zmieni, bo
rozpatrujemy wierzchołki coraz bardziej odległe od s
Cykl Eulera
udowodnimy, że w momencie odwiedzania v najkrótsza
Wstęp
Istnienie
ścieżka z s do v ma długość dis[v]:
Wyznaczanie
dowód przez indukcję "w czasie"
Najkrótsze
ścieżki
baza w momencie wejścia do s zachodzi dis[s] = 0
Wstęp
Dijkstra krok indukcyjny załóżmy, że odwiedzamy v:
Bellman-Ford
najkrótsza ścieżka do v musi biec tylko przez już
odwiedzone wierzchołki, bo v ma najniższą wartość w
tablicy dis spośród nieodwiedzonych wierzchołków
jest więc ona postaci (s, x1, . . . , xn, v) dla odwiedzonych
xi
rozważyliśmy ją relaksując krawędz xn v
Algorytm Dijkstry
Grafy c.d.
cykl Eulera,
algorytm
Dlaczego to działa?
Dijkstry i
Bellmana-
Forda po rozpatrzeniu v wartość dis[v] już się nie zmieni, bo
rozpatrujemy wierzchołki coraz bardziej odległe od s
Cykl Eulera
udowodnimy, że w momencie odwiedzania v najkrótsza
Wstęp
Istnienie
ścieżka z s do v ma długość dis[v]:
Wyznaczanie
dowód przez indukcję "w czasie"
Najkrótsze
ścieżki
baza w momencie wejścia do s zachodzi dis[s] = 0
Wstęp
Dijkstra krok indukcyjny załóżmy, że odwiedzamy v:
Bellman-Ford
najkrótsza ścieżka do v musi biec tylko przez już
odwiedzone wierzchołki, bo v ma najniższą wartość w
tablicy dis spośród nieodwiedzonych wierzchołków
jest więc ona postaci (s, x1, . . . , xn, v) dla odwiedzonych
xi
rozważyliśmy ją relaksując krawędz xn v
Implementacja
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera
Wstęp
Istnienie
Implementacja
Wyznaczanie
Najkrótsze
Implementacja algorytmu Dijkstry znajduje się w notatkach.
ścieżki
Wstęp
Dijkstra
Bellman-Ford
Sieci z ujemnymi wagami
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Sieci z ujemnymi wagami
Forda
przypomnijmy, że algorytm Dijkstry nie dział dla sieci z
Cykl Eulera
ujemnymi wagami
Wstęp
Istnienie
takie sieci czasem pojawiają się w zadaniach, np:
Wyznaczanie
Najkrótsze
Mamy n różnych przedmiotów oraz informacje
ścieżki
Wstęp o możliwych transakcjach postaci: "przedmiot
Dijkstra
Bellman-Ford A można wymienić na B zyskując/dopłacając
C zł". Masz przedmiot nr. 1 a chcesz mieć
przedmiot nr. n. Ile musisz minimalnie wydać
lub ile możesz maksymalnie zarobić?
Sieci z ujemnymi wagami
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Sieci z ujemnymi wagami
Forda
przypomnijmy, że algorytm Dijkstry nie dział dla sieci z
Cykl Eulera
ujemnymi wagami
Wstęp
Istnienie
takie sieci czasem pojawiają się w zadaniach, np:
Wyznaczanie
Najkrótsze
Mamy n różnych przedmiotów oraz informacje
ścieżki
Wstęp o możliwych transakcjach postaci: "przedmiot
Dijkstra
Bellman-Ford A można wymienić na B zyskując/dopłacając
C zł". Masz przedmiot nr. 1 a chcesz mieć
przedmiot nr. n. Ile musisz minimalnie wydać
lub ile możesz maksymalnie zarobić?
Sieci z ujemnymi wagami
Grafy c.d.
cykl Eulera,
Ujemne cykle
algorytm
Dijkstry i
Bellmana- zastanówmy się co by się stało, gdybyśmy szukali
Forda
najkrótszych ścieżek w grafie z ujemnym cyklem o
sumie wag -c (c > 0)
Cykl Eulera
Wstęp
niech v należy do takiego cyklu
Istnienie
Wyznaczanie
jaka jest długość najkrótszej ścieżki z v do v
Najkrótsze
ścieżki
jeśli przejdziemy po cyklu to otrzymujemy ścieżkę o
Wstęp
Dijkstra
koszcie -c
Bellman-Ford
jeśli przejdziemy po cyklu dwukrotnie to otrzymujemy
ścieżkę o koszcie -2c
jeśli przejdziemy po cyklu trzykrotnie to otrzymujemy
ścieżkę o koszcie -3c . . .
widzimy, że najkrótsza ścieżka z v do v nie istnieje!
Sieci z ujemnymi wagami
Grafy c.d.
cykl Eulera,
Ujemne cykle
algorytm
Dijkstry i
Bellmana- zastanówmy się co by się stało, gdybyśmy szukali
Forda
najkrótszych ścieżek w grafie z ujemnym cyklem o
sumie wag -c (c > 0)
Cykl Eulera
Wstęp
niech v należy do takiego cyklu
Istnienie
Wyznaczanie
jaka jest długość najkrótszej ścieżki z v do v
Najkrótsze
ścieżki
jeśli przejdziemy po cyklu to otrzymujemy ścieżkę o
Wstęp
Dijkstra
koszcie -c
Bellman-Ford
jeśli przejdziemy po cyklu dwukrotnie to otrzymujemy
ścieżkę o koszcie -2c
jeśli przejdziemy po cyklu trzykrotnie to otrzymujemy
ścieżkę o koszcie -3c . . .
widzimy, że najkrótsza ścieżka z v do v nie istnieje!
Sieci z ujemnymi wagami
Grafy c.d.
cykl Eulera,
Ujemne cykle
algorytm
Dijkstry i
Bellmana- zastanówmy się co by się stało, gdybyśmy szukali
Forda
najkrótszych ścieżek w grafie z ujemnym cyklem o
sumie wag -c (c > 0)
Cykl Eulera
Wstęp
niech v należy do takiego cyklu
Istnienie
Wyznaczanie
jaka jest długość najkrótszej ścieżki z v do v
Najkrótsze
ścieżki
jeśli przejdziemy po cyklu to otrzymujemy ścieżkę o
Wstęp
Dijkstra
koszcie -c
Bellman-Ford
jeśli przejdziemy po cyklu dwukrotnie to otrzymujemy
ścieżkę o koszcie -2c
jeśli przejdziemy po cyklu trzykrotnie to otrzymujemy
ścieżkę o koszcie -3c . . .
widzimy, że najkrótsza ścieżka z v do v nie istnieje!
Sieci z ujemnymi wagami
Grafy c.d.
cykl Eulera,
Ujemne cykle
algorytm
Dijkstry i
Bellmana- zastanówmy się co by się stało, gdybyśmy szukali
Forda
najkrótszych ścieżek w grafie z ujemnym cyklem o
sumie wag -c (c > 0)
Cykl Eulera
Wstęp
niech v należy do takiego cyklu
Istnienie
Wyznaczanie
jaka jest długość najkrótszej ścieżki z v do v
Najkrótsze
ścieżki
jeśli przejdziemy po cyklu to otrzymujemy ścieżkę o
Wstęp
Dijkstra
koszcie -c
Bellman-Ford
jeśli przejdziemy po cyklu dwukrotnie to otrzymujemy
ścieżkę o koszcie -2c
jeśli przejdziemy po cyklu trzykrotnie to otrzymujemy
ścieżkę o koszcie -3c . . .
widzimy, że najkrótsza ścieżka z v do v nie istnieje!
Sieci z ujemnymi wagami
Grafy c.d.
cykl Eulera,
Ujemne cykle
algorytm
Dijkstry i
Bellmana- zastanówmy się co by się stało, gdybyśmy szukali
Forda
najkrótszych ścieżek w grafie z ujemnym cyklem o
sumie wag -c (c > 0)
Cykl Eulera
Wstęp
niech v należy do takiego cyklu
Istnienie
Wyznaczanie
jaka jest długość najkrótszej ścieżki z v do v
Najkrótsze
ścieżki
jeśli przejdziemy po cyklu to otrzymujemy ścieżkę o
Wstęp
Dijkstra
koszcie -c
Bellman-Ford
jeśli przejdziemy po cyklu dwukrotnie to otrzymujemy
ścieżkę o koszcie -2c
jeśli przejdziemy po cyklu trzykrotnie to otrzymujemy
ścieżkę o koszcie -3c . . .
widzimy, że najkrótsza ścieżka z v do v nie istnieje!
Sieci z ujemnymi wagami
Grafy c.d.
cykl Eulera,
Ujemne cykle
algorytm
Dijkstry i
Bellmana- zastanówmy się co by się stało, gdybyśmy szukali
Forda
najkrótszych ścieżek w grafie z ujemnym cyklem o
sumie wag -c (c > 0)
Cykl Eulera
Wstęp
niech v należy do takiego cyklu
Istnienie
Wyznaczanie
jaka jest długość najkrótszej ścieżki z v do v
Najkrótsze
ścieżki
jeśli przejdziemy po cyklu to otrzymujemy ścieżkę o
Wstęp
Dijkstra
koszcie -c
Bellman-Ford
jeśli przejdziemy po cyklu dwukrotnie to otrzymujemy
ścieżkę o koszcie -2c
jeśli przejdziemy po cyklu trzykrotnie to otrzymujemy
ścieżkę o koszcie -3c . . .
widzimy, że najkrótsza ścieżka z v do v nie istnieje!
Sieci z ujemnymi wagami
Grafy c.d.
cykl Eulera,
Ujemne cykle
algorytm
Dijkstry i
Bellmana- zastanówmy się co by się stało, gdybyśmy szukali
Forda
najkrótszych ścieżek w grafie z ujemnym cyklem o
sumie wag -c (c > 0)
Cykl Eulera
Wstęp
niech v należy do takiego cyklu
Istnienie
Wyznaczanie
jaka jest długość najkrótszej ścieżki z v do v
Najkrótsze
ścieżki
jeśli przejdziemy po cyklu to otrzymujemy ścieżkę o
Wstęp
Dijkstra
koszcie -c
Bellman-Ford
jeśli przejdziemy po cyklu dwukrotnie to otrzymujemy
ścieżkę o koszcie -2c
jeśli przejdziemy po cyklu trzykrotnie to otrzymujemy
ścieżkę o koszcie -3c . . .
widzimy, że najkrótsza ścieżka z v do v nie istnieje!
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera
Algorytm Bellmana-Forda
Wstęp
Istnienie
dlatego też załóżmy, że rozważamy graf z ujemnymi
Wyznaczanie
wagami, ale bez ujemnych cykli
Najkrótsze
ścieżki
Wstęp
do liczenia najkrótszych ścieżek w takim grafie możemy
Dijkstra
Bellman-Ford użyć algorytmuBellmana-Forda
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera
Algorytm Bellmana-Forda
Wstęp
Istnienie
dlatego też załóżmy, że rozważamy graf z ujemnymi
Wyznaczanie
wagami, ale bez ujemnych cykli
Najkrótsze
ścieżki
Wstęp
do liczenia najkrótszych ścieżek w takim grafie możemy
Dijkstra
Bellman-Ford użyć algorytmuBellmana-Forda
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera Algorytm Bellmana-Forda:
Wstęp
Istnienie
dla każdego v " V ustaw dis[v] = "
Wyznaczanie
Najkrótsze
ustaw dis[s] = 0
ścieżki
Wstęp
powtórz |V | - 1 razy poniższy krok:
Dijkstra
Bellman-Ford
zrelaksuj wszystkie krawędzie w dowolnej kolejności
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera Algorytm Bellmana-Forda:
Wstęp
Istnienie
dla każdego v " V ustaw dis[v] = "
Wyznaczanie
Najkrótsze
ustaw dis[s] = 0
ścieżki
Wstęp
powtórz |V | - 1 razy poniższy krok:
Dijkstra
Bellman-Ford
zrelaksuj wszystkie krawędzie w dowolnej kolejności
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera Algorytm Bellmana-Forda:
Wstęp
Istnienie
dla każdego v " V ustaw dis[v] = "
Wyznaczanie
Najkrótsze
ustaw dis[s] = 0
ścieżki
Wstęp
powtórz |V | - 1 razy poniższy krok:
Dijkstra
Bellman-Ford
zrelaksuj wszystkie krawędzie w dowolnej kolejności
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera Algorytm Bellmana-Forda:
Wstęp
Istnienie
dla każdego v " V ustaw dis[v] = "
Wyznaczanie
Najkrótsze
ustaw dis[s] = 0
ścieżki
Wstęp
powtórz |V | - 1 razy poniższy krok:
Dijkstra
Bellman-Ford
zrelaksuj wszystkie krawędzie w dowolnej kolejności
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i Dlaczego to działa?
Bellmana-
Forda
po 1-szym wykonaniu pętli mamy policzone najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
Cykl Eulera
składa się z 1 krawędzi
Wstęp
Istnienie
Wyznaczanie po 2-gim wykonaniu pętli mamy policzone najkrótsze
Najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
ścieżki
Wstęp
składa się z co najwyżej 2 krawędzi
Dijkstra
Bellman-Ford
po k-tym wykonaniu pętli mamy policzone najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
składa się z co najwyżej k krawędzi
najkrótsze ścieżki składają się z co najwyżej |V | - 1,
gdyż dłuższe ścieżki zawierają cykl o nieujemnej wadze
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i Dlaczego to działa?
Bellmana-
Forda
po 1-szym wykonaniu pętli mamy policzone najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
Cykl Eulera
składa się z 1 krawędzi
Wstęp
Istnienie
Wyznaczanie po 2-gim wykonaniu pętli mamy policzone najkrótsze
Najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
ścieżki
Wstęp
składa się z co najwyżej 2 krawędzi
Dijkstra
Bellman-Ford
po k-tym wykonaniu pętli mamy policzone najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
składa się z co najwyżej k krawędzi
najkrótsze ścieżki składają się z co najwyżej |V | - 1,
gdyż dłuższe ścieżki zawierają cykl o nieujemnej wadze
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i Dlaczego to działa?
Bellmana-
Forda
po 1-szym wykonaniu pętli mamy policzone najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
Cykl Eulera
składa się z 1 krawędzi
Wstęp
Istnienie
Wyznaczanie po 2-gim wykonaniu pętli mamy policzone najkrótsze
Najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
ścieżki
Wstęp
składa się z co najwyżej 2 krawędzi
Dijkstra
Bellman-Ford
po k-tym wykonaniu pętli mamy policzone najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
składa się z co najwyżej k krawędzi
najkrótsze ścieżki składają się z co najwyżej |V | - 1,
gdyż dłuższe ścieżki zawierają cykl o nieujemnej wadze
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i Dlaczego to działa?
Bellmana-
Forda
po 1-szym wykonaniu pętli mamy policzone najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
Cykl Eulera
składa się z 1 krawędzi
Wstęp
Istnienie
Wyznaczanie po 2-gim wykonaniu pętli mamy policzone najkrótsze
Najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
ścieżki
Wstęp
składa się z co najwyżej 2 krawędzi
Dijkstra
Bellman-Ford
po k-tym wykonaniu pętli mamy policzone najkrótsze
ścieżki do wierzchołków dla których najkrótsza ścieżka
składa się z co najwyżej k krawędzi
najkrótsze ścieżki składają się z co najwyżej |V | - 1,
gdyż dłuższe ścieżki zawierają cykl o nieujemnej wadze
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Wykrywanie ujemnych cykli
Dijkstry i
Bellmana-
zastanówmy się co by się stało, gdybyśmy wykonali
Forda
|V |-tą iterację pętli
Cykl Eulera
jeśli uda nam się cokolwiek zrelaksować, to wiemy, że
Wstęp
Istnienie
w grafie istnieje ujemny cykl
Wyznaczanie
jeśli w grafie istnieje ujemny cykl, to uda nam się coś
Najkrótsze
ścieżki
zrelaksować gdybyśmy nic nie zrelaksowali to
Wstęp
Dijkstra
kolejne powtórzenia pętli też nic by nie relaksowały a
Bellman-Ford
zatem pomimo dopuszczenia ścieżek składających się
z dowolnie wielu krawędzi nie otrzymali byśmy ścieżek
o dowolnie małym koszcie sprzeczność
otrzymujemy zatem prosty test na sprawdzanie czy graf
zawiera ujemny cykl
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Wykrywanie ujemnych cykli
Dijkstry i
Bellmana-
zastanówmy się co by się stało, gdybyśmy wykonali
Forda
|V |-tą iterację pętli
Cykl Eulera
jeśli uda nam się cokolwiek zrelaksować, to wiemy, że
Wstęp
Istnienie
w grafie istnieje ujemny cykl
Wyznaczanie
jeśli w grafie istnieje ujemny cykl, to uda nam się coś
Najkrótsze
ścieżki
zrelaksować gdybyśmy nic nie zrelaksowali to
Wstęp
Dijkstra
kolejne powtórzenia pętli też nic by nie relaksowały a
Bellman-Ford
zatem pomimo dopuszczenia ścieżek składających się
z dowolnie wielu krawędzi nie otrzymali byśmy ścieżek
o dowolnie małym koszcie sprzeczność
otrzymujemy zatem prosty test na sprawdzanie czy graf
zawiera ujemny cykl
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Wykrywanie ujemnych cykli
Dijkstry i
Bellmana-
zastanówmy się co by się stało, gdybyśmy wykonali
Forda
|V |-tą iterację pętli
Cykl Eulera
jeśli uda nam się cokolwiek zrelaksować, to wiemy, że
Wstęp
Istnienie
w grafie istnieje ujemny cykl
Wyznaczanie
jeśli w grafie istnieje ujemny cykl, to uda nam się coś
Najkrótsze
ścieżki
zrelaksować gdybyśmy nic nie zrelaksowali to
Wstęp
Dijkstra
kolejne powtórzenia pętli też nic by nie relaksowały a
Bellman-Ford
zatem pomimo dopuszczenia ścieżek składających się
z dowolnie wielu krawędzi nie otrzymali byśmy ścieżek
o dowolnie małym koszcie sprzeczność
otrzymujemy zatem prosty test na sprawdzanie czy graf
zawiera ujemny cykl
Algorytm Bellmana-Forda
Grafy c.d.
cykl Eulera,
algorytm
Wykrywanie ujemnych cykli
Dijkstry i
Bellmana-
zastanówmy się co by się stało, gdybyśmy wykonali
Forda
|V |-tą iterację pętli
Cykl Eulera
jeśli uda nam się cokolwiek zrelaksować, to wiemy, że
Wstęp
Istnienie
w grafie istnieje ujemny cykl
Wyznaczanie
jeśli w grafie istnieje ujemny cykl, to uda nam się coś
Najkrótsze
ścieżki
zrelaksować gdybyśmy nic nie zrelaksowali to
Wstęp
Dijkstra
kolejne powtórzenia pętli też nic by nie relaksowały a
Bellman-Ford
zatem pomimo dopuszczenia ścieżek składających się
z dowolnie wielu krawędzi nie otrzymali byśmy ścieżek
o dowolnie małym koszcie sprzeczność
otrzymujemy zatem prosty test na sprawdzanie czy graf
zawiera ujemny cykl
Implementacja
Grafy c.d.
cykl Eulera,
algorytm
Dijkstry i
Bellmana-
Forda
Cykl Eulera
Wstęp
Istnienie Implementacja
Wyznaczanie
Implementacja algorytmu Bellmana-Forda znajduje się w
Najkrótsze
ścieżki
notatkach.
Wstęp
Dijkstra
Bellman-Ford
Wyszukiwarka
Podobne podstrony:
Cykl Hamiltona algorytm rekurencyjnyPoszukiwanie cyklu Eulera algorytm Fleury`egoAlgorytm DijkstryMargit Sandemo Cykl Saga o czarnoksiężniku (02) Blask twoich oczuanaliza algorytmow2009 12 Metaprogramowanie algorytmy wykonywane w czasie kompilacji [Programowanie C C ]6 6 Zagadnienie transportowe algorytm transportowy przykład 2! Średniowiecze algoryzm sredniowieczny02 Jądro komórkowe w interfazie Cykl komórkowy4 Wyklad GrafyMargit Sandemo Cykl Saga o Królestwie Światła (01) Wielkie WrotaAlgorytmy genetyczne a logika rozmytaMargit Sandemo Cykl Saga o Królestwie Światła (16) Głód życiaLekcja algorytmy w geometriiAlgorytm Wstrzas anafilaktycznywięcej podobnych podstron