Algorytmy grafowe
•Minimalne drzewa rozpinające
•Algorytm Kruskala
•Algorytm Prima
•Wyszukiwanie najkrótszych ścieżek z
jednym źródłem
•Algorytm Dijkstry
•Algorytm Bellmana-Forda
Algorytmy grafowe
•Minimalne drzewa rozpinające
•Algorytm Kruskala
•Algorytm Prima
•Wyszukiwanie najkrótszych ścieżek z
jednym źródłem
•Algorytm Dijkstry
•Algorytm Bellmana-Forda
Minimalne drzewa
rozpinające
Podgraf T spójnego grafu G nazywa się jego
drzewem rozpinającym, jeśli T jest acykliczny i
łączy wszystkie wierzchołki G. Jeśli krawędziom
przypisane są wagi, i suma wag krawędzi T jest
minimalna, T nazywamy minimalnym drzewem
rozpinającym.
4
8
7
9
14
10
2
1
11
2
7
8
4
6
Przykład minimalnego drzewa
rozpinającego
Algorytm Kruskala
MST-Kruskal(G, w)
1 A :=
2 for każdy wierzchołek vV[G]
3
do Make-Set(v)
4 posortuj krawędzie z E niemalejąco względem wag w
5 for każda krawędź (u,v) E, w kolejności niemalejących
wag
6
do if Find-Set(u) Find-Set(v)
7
then A := A {(u,v)}
8
Union(u,v)
9 return A
Algorytm Kruskala
(przykład)
4
8
7
9
14
10
2
1
1
1
2
7
8
4
6
4
8
7
9
14
10
2
1
1
1
2
7
8
4
6
4
8
7
9
14
10
2
1
1
1
2
7
8
4
6
4
8
7
9
14
10
2
1
1
1
2
7
8
4
6
2
1
4
8
7
9
10
1
1
2
7
8
4
6
4
8
7
9
14
10
2
1
1
1
2
7
8
4
6
Algorytm Prima
MST-Prim(G, w, r)
1 Q := V[G]
2 for każdy uQ
3
do key[u] :=
4 key[r] := 0
5
[r] := NIL
6 while Q
7
do u := Extract-Min(Q)
8
for każdy v Adj[u]
9
do if vQ i w(u,v) < key[v]
10
then
[v] := u
11
key[v] := w(u,v)
Algorytm Prima (przykład)
8
7
4
9
14
10
2
1
1
1
2
7
8
4
6
4
8
7
9
14
10
2
1
1
1
2
7
8
4
6
4
8
7
9
14
10
2
1
1
1
2
7
8
4
6
4
8
7
9
14
10
2
1
1
1
2
7
8
4
6
2
1
4
8
7
9
10
1
1
2
7
8
4
6
8
7
2
1
4
9
14
10
1
1
2
7
8
4
6
Najkrótsze ścieżki z
jednym źródłem
Dany jest ważony graf skierowany G=(V,E) i
wyróżniony wierzchołek sV, nazywany źródłem;
dla każdego wierzchołka vV należy znaleźć
najkrótszą ścieżkę z s do v. Wagą ścieżki jest
suma wag tworzących ją krawędzi. Najkrótszą
ścieżką jest ścieżka o najmniejszej wadze.
s
6
3
5
7
11
9
3
5
0
2
1
6
2
4
3
Ważony graf skierowany Drzewo najkrótszych ścieżek
s
6
3
5
7
9
3
5
0
2
1
6
2
4
3
1
1
Najkrótsze ścieżki z
jednym źródłem
d[v] - oszacowanie wagi najkrótszej ścieżki, [v] -
poprzednik v
Initialize-Single-Source(G, s)
1 for każdy wierzchołek vV[G]
2
do d[v] :=
3
[v] := NIL
4 d[s] := 0
Relaksacja krawędzi - ewentualne zmniejszenie
oszacowania wagi najkrótszej ścieżki d[v]
Relax(u, v, w)
1 if d[v] > d[u] + w(u, v)
2
then d[v] := d[u] + w(u, v)
3
[v] := u
Algorytm Dijkstry
Dijkstra(G, w, s)
1 Initialize-Single-Source(G, s)
2 S :=
3 Q := V[G]
4 while Q
5
do u := Extract-Min(Q)
6
S := S {u}
7
for każdy wierzchołek v Adj[u]
8
do Relax(u, v, w)
Algorytm Dijkstry
(przykład)
s
1
1
0
5
6
0
2
3
2
4
9
7
s
1
1
0
5
6
10
5
0
2
3
2
4
9
7
s
1
1
0
5
6
7
14
8
5
0
2
3
2
4
9
7
s
1
1
0
5
6
7
13
8
5
0
2
3
2
4
9
7
s
1
1
0
5
6
7
9
8
5
0
2
3
2
4
9
7
1
s
1
0
5
6
7
9
8
5
0
2
3
2
4
9
7
Algorytm Bellmana-Forda
Bellman-Ford(G, w, s)
1 Initialize-Single-Source(G, s)
2 for i = 1 to |V[G]| - 1
3
do for każda krawędź (u, v) E[G]
4
do Relax(u, v, w)
5 for każda krawędź (u, v) E[G]
6
do if d[v] > d[u] + w(u, v)
7
then return FALSE
8 return TRUE
Algorytm Bellmana-Forda
(przykład)
s
5
6
7
7
0
8
3
9
-4
-2
2
-3
s
5
6
7
7
6
7
0
8
3
9
-4
-2
2
-3
s
5
6
7
7
2
4
6
7
0
8
3
9
-4
-2
2
-3
9
s
5
6
7
7
2
4
2
7
0
8
3
-4
-2
2
-3
s
5
6
7
7
-2
4
2
7
0
8
3
-4
-2
2
-3