Informatyka. Konkursy i algorytmy
Dijkstra
Do czego służy?
Algorytm Dijkstra służy do znajdowania najkrótszej ścieżki z jednego wierzchołka do wszystkich w grafie ważonym. Pierwszym pomysłem na algorytm może być przejście po wszystkich ścieżkach, ale to jest oczywiście za wolne. Rozwiązaniem tego problemu jest algorytm Dijkstry.
Algorytm
Trzymamy listę wierzchołków do odwiedzenia, listę odwiedzonych wierzchołków i listę odległości od wierzchołka startowego
do innych wierzchołków. W liście odwiedzonych wierzchołków na początku każdy wierzchołek ma wartość false (jeszcze nie
został odwiedzony). W liście odległości od wierzchołka startowego na początku trzymamy nieskończoność (czyli jakąś bardzo
dużą liczbę, która jest większa od możliwego do uzyskania wyniku). W liście wierzchołków do rozpatrzenia będziemy trzymać
jako jeden obiekt wierzchołek i odległość do niego jaką wyliczyliśmy. Z listy będziemy brać od najmniejszej odległości
do największej. Na początku wrzucamy tam wierzchołek startowy z odległością 0. Ustawiamy odległość dla niegna 0. Dla
każdego rozpatrywanego wierzchołka z listy będziemy wykonywać takie czynności:
1. usuwamy rozpatrywany wierzchołek z listy
2. jeśli był już odwiedzony (wartość w liście wierzchołków odwiedzonych ma true) to przechodzimy do rozpatrzywania
następnego wierzchołka
3. ustawiamy wartość dla wierzchołka na liście wierzchołków odwiedzonych na true
4. przechodzimy po sąsiadach rozpatrywanego wierzchołka:
5. jeśli dla danego sąsiada rozpatrywanego wierzchołka odległość od niego jest większa niż odległość rozpatrywanego
wierzchołka dodać wartość w krawędzi to aktualizujemy mu wartość odległości i wrzucamy go z tą odległością na listę
6. algorytm kończymy jeśli lista jest pusta. Odległości od wierzchołka dla każdego wierzchołka w danych grafie są już
obliczone i trzymane w tablicy odległości.
Przykład
Zasymulujmy algorytm Dijkstry na takim przykładowym grafie:
Wierzchołkiem startowym jest 1.
lista wierzchołków do rozpatrzenia:
1 odległość 0
lista odległości od 1 dla wierzchołków grafu:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
lista wierzchołków odwiedzonych:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| false | false | false | false | false | false | false | false |
Ustawiamy odległość w 1 na 0. Rozpatrujemy 1:
Usuwamy 1 z listy wierzchołków do rozpatrzenia.
W liście wierzchołków odwiedzonych 1 ma wartość false, więc ustawiamy ją na true.
Przechodzimy po sąsiadach 1:
2:
Odległość od 2 jest większa niż odległość 1 dodać krawędź z 1 do 2 (∞ > 0 + 2). Ustawiamy więc odległość 2 na odległość 1 dodać krawędź z 1 do 2 (czyli 0 + 2 = 2) i dodajemy 2 razem z odległością do listy wierzchołków do rozpatrzenia.
3:
Odległość od 3 jest większa niż odległość 1 dodać krawędź z 1 do 3(∞ > 0 + 1). Ustawiamy więc odległość 3 na odległość 1 dodać krawędź z 1 do 3 (czyli 0 + 1 = 1) i dodajemy 3 razem z odległością do listy wierzchołków do rozpatrzenia.
5:
Odległość od 5 jest większa niż odległość 1 dodać krawędź z 1 do 5(∞ > 0 + 3). Ustawiamy więc odległość 5 na odległość 1 dodać krawędź z 1 do 5 (czyli 0 + 3 = 3) i dodajemy 5 razem z odległością do listy wierzchołków do rozpatrzenia.
lista wierzchołków do rozpatrzenia: 3 odległość 1, 2 odległość 2, 5 odległość 3
lista odległości od 1 dla wierzchołków grafu:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 2 | 1 | ∞ | 3 | ∞ | ∞ | ∞ |
lista wierzchołków odwiedzonych:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| true | false | false | false | false | false | false | false |
Rozpatrujemy 3:
Usuwamy 3 z listy wierzchołków do rozpatrzenia.
W liście wierzchołków odwiedzonych 3 ma wartość false, więc ustawiamy ją na true.
Przechodzimy po sąsiadach 3:
2:
Odległość od 2 jest mniejsza niż odległość 3 dodać krawędź z 3 do 2 (2 < 1 + 8). Zostawiamy więc 2 i idziemy do następnego wierzchołka.
1:
Odległość od 1 jest mniejsza niż odległość 3 dodać krawędź z 3 do 1(0 < 1 + 1). Zostawiamy więc 2 i idziemy do następnego wierzchołka (czyli kończymy rozpatrywanie 3, ponieważ nie ma już więcej sąsiadów)
lista wierzchołków do rozpatrzenia: 2 odległość 2, 5 odległość 3
lista odległości od 1 dla wierzchołków grafu:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 2 | 1 | ∞ | 3 | ∞ | ∞ | ∞ |
lista wierzchołków odwiedzonych:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| true | false | true | false | false | false | false | false |
Rozpatrujemy 2:
Usuwamy 2 z listy wierzchołków do rozpatrzenia.
W liście wierzchołków odwiedzonych 2 ma wartość false, więc ustawiamy ją na true.
Przechodzimy po sąsiadach 2:
3:
Odległość od 3 jest mniejsza niż odległość 2 dodać krawędź z 2 do 3 (1 < 2 + 8). Zostawiamy więc 3 i idziemy do następnego wierzchołka.
1:
Odległość od 1 jest mniejsza niż odległość 2 dodać krawędź z 2 do 1(0 < 2 + 2). Zostawiamy więc 1 i idziemy do następnego wierzchołka
5:
Odległość od 5 nie jest większa niż odległość 2 dodać krawędź z 2 do 5 (3 = 2 + 1). Zostawiamy więc 5 i idziemy do następnego wierzchołka.
6:
Odległość od 6 jest większa niż odległość 2 dodać krawędź z 2 do 6(∞ > 2 + 5). Ustawiamy więc odległość 6 na odległość 2 dodać krawędź z 2 do 6 (czyli 2 + 5 = 7) i dodajemy 6 razem z odległością do listy wierzchołków do rozpatrzenia.
lista wierzchołków do rozpatrzenia: 5 odległość 3, 6 odległość 7
lista odległości od 1 dla wierzchołków grafu:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 2 | 1 | ∞ | 3 | 7 | ∞ | ∞ |
lista wierzchołków odwiedzonych:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| true | true | true | false | false | false | false | false |
Rozpatrujemy 5:
Usuwamy 5 z listy wierzchołków do rozpatrzenia.
W liście wierzchołków odwiedzonych 5 ma wartość false, więc ustawiamy ją na true.
Przechodzimy po sąsiadach 5:
2:
Odległość od 2 jest mniejsza niż odległość 5 dodać krawędź z 5 do 2 (2 < 3 + 1). Zostawiamy więc 2 i idziemy do następnego wierzchołka.
1:
Odległość od 1 jest mniejsza niż odległość 5 dodać krawędź z 5 do 1(0 < 3 + 3). Zostawiamy więc 1 i idziemy do następnego wierzchołka
4:
Odległość od 4 jest większa niż odległość 5 dodać krawędź z 5 do 4(∞ > 2 + 3). Ustawiamy więc odległość 4 na odległość 5 dodać krawędź z 5 do 4 (czyli 2 + 3 = 5) i dodajemy 4 razem z odległością do listy wierzchołków do rozpatrzenia.
8:
Odległość od 8 jest większa niż odległość 5 dodać krawędź z 5 do 8(∞ > 3 + 6). Ustawiamy więc odległość 8 na odległość 5 dodać krawędź z 5 do 8 (czyli 3 + 6 = 9) i dodajemy 8 razem z odległością do listy wierzchołków do rozpatrzenia.
lista wierzchołków do rozpatrzenia: 4 odległość 5, 6 odległość 7, 8 odległość 9
lista odległości od 1 dla wierzchołków grafu:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 2 | 1 | 5 | 3 | 7 | ∞ | 9 |
lista wierzchołków odwiedzonych:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| true | true | true | false | true | false | false | false |
Rozpatrujemy 4:
Usuwamy 4 z listy wierzchołków do rozpatrzenia.
W liście wierzchołków odwiedzonych 4 ma wartość false, więc ustawiamy ją na true.
Przechodzimy po sąsiadach 4:
5:
Odległość od 5 jest mniejsza niż odległość 6 dodać krawędź z 6 do 5 (3 < 5 + 2). Zostawiamy więc 5 i idziemy do następnego wierzchołka.(czyli kończymy rozpatrywanie 4, ponieważ nie ma już więcej sąsiadów)
lista wierzchołków do rozpatrzenia: 6 odległość 7, 8 odległość 9
lista odległości od 1 dla wierzchołków grafu:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 2 | 1 | 5 | 3 | 7 | ∞ | 9 |
lista wierzchołków odwiedzonych:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| true | true | true | true | true | false | false | false |
Rozpatrujemy 6:
Usuwamy 6 z listy wierzchołków do rozpatrzenia.
W liście wierzchołków odwiedzonych 6 ma wartość false, więc ustawiamy ją na true.
Przechodzimy po sąsiadach 6:
2:
Odległość od 2 jest mniejsza niż odległość 6 dodać krawędź z 6 do 2 (2 < 7 + 5). Zostawiamy więc 2 i idziemy do następnego wierzchołka.
7:
Odległość od 7 jest większa niż odległość 6 dodać krawędź z 6 do 7(∞ > 7 + 9). Ustawiamy więc odległość 7 na odległość 6 dodać krawędź z 6 do 7 (czyli 7 + 9 = 16) i dodajemy 7 razem z odległością do listy wierzchołków do rozpatrzenia.
4:
lista wierzchołków do rozpatrzenia: 8 odległość 9, 7 odległość 16
lista odległości od 1 dla wierzchołków grafu:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 2 | 1 | 5 | 3 | 7 | 16 | 9 |
lista wierzchołków odwiedzonych:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| true | true | true | true | true | true | false | false |
Rozpatrujemy 8:
Usuwamy 8 z listy wierzchołków do rozpatrzenia.
W liście wierzchołków odwiedzonych 8 ma wartość false, więc ustawiamy ją na true.
Przechodzimy po sąsiadach 8:
5:
Odległość od 5 jest mniejsza niż odległość 8 dodać krawędź z 8 do 5 (3 < 9 + 6). Zostawiamy więc 5 i idziemy do następnego wierzchołka.
7:
Odległość od 7 jest większa niż odległość 8 dodać krawędź z 8 do 7(16 > 9 + 3). Ustawiamy więc odległość 7 na odległość 8 dodać krawędź z 8 do 7 (czyli 9 + 3 = 12) i dodajemy 7 razem z odległością do listy wierzchołków do rozpatrzenia.
lista wierzchołków do rozpatrzenia: 7 odległość 12, 7 odległość 16
lista odległości od 1 dla wierzchołków grafu:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 2 | 1 | 5 | 3 | 7 | 12 | 9 |
lista wierzchołków odwiedzonych:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| true | true | true | true | true | true | false | true |
Rozpatrujemy 7:
Usuwamy 7 z listy wierzchołków do rozpatrzenia.
W liście wierzchołków odwiedzonych 7 ma wartość false, więc ustawiamy ją na true.
Przechodzimy po sąsiadach 7:
8:
Odległość od 8 jest mniejsza niż odległość 7 dodać krawędź z 7 do 8 (9 < 12 + 3). Zostawiamy więc 8 i idziemy do następnego wierzchołka.
6:
Odległość od 6 jest mniejsza niż odległość 7 dodać krawędź z 7 do 6 (7 < 12 + 9). Zostawiamy więc 6 i idziemy do następnego wierzchołka.(czyli kończymy rozpatrywanie 7, ponieważ nie ma już więcej sąsiadów)
lista wierzchołków do rozpatrzenia: 7 odległość 16
lista odległości od 1 dla wierzchołków grafu:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 2 | 1 | 5 | 3 | 7 | 12 | 9 |
lista wierzchołków odwiedzonych:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| true | true | true | true | true | true | true | true |
Rozpatrujemy 7:
Usuwamy 7 z listy wierzchołków do rozpatrzenia.
W liście wierzchołków odwiedzonych 7 ma wartość true, więc nie rozpatrujemy dalej 7.
lista wierzchołków do rozpatrzenia:
lista odległości od 1 dla wierzchołków grafu:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 2 | 1 | 5 | 3 | 7 | 12 | 9 |
lista wierzchołków odwiedzonych:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| true | true | true | true | true | true | true | true |
Ponieważ lista wierzchołków do rozpatrzenia jest pusta, kończymy algorytm.
implementacja i złożoność
implementacja w c++:vector <pair <int, long long> >graf[1000007];
long long odl[1000007];
void dijkstra(){
odl[1] = 0;
priority_queue <pair <long long, int> > q;
q.push(make_pair(0, 1));
while(q.size()){
int w = q.top().second;
q.pop();
if(odw[w]){
continue;
}
odw[w] = true;
for(int i : graf[w]){
if(odl[i.first] > odl[w] + i.second){
odl[i.first] = odl[w] + i.second;
q.push(make_pair(-odl[i.first], i.first));
}
}
}
}
implementacja w python:
odl = [1000000007 for i in range(1000007)]
graf = [[] for i in range(1000007)]
def dijkstra():
odl[1] = 0
q = set()
q.add((0, 1))
while(len(q) > 0):
w = q.pop()
if(odw[w[1]] == False):
odw[w[1]] = True
for i in graf[w[1]]:
if(odl[i[0]] > odl[w[1]] + i[1]):
odl[i[0]] = odl[w[1]] + i[1]
q.add((odl[i[0]], i[0]))
złożoność: