Този алгоритъм беше един от първите, които научих, и, макар че може да е объркващ, намира широко приложение и си струва да бъде научен.
---
 |
| Source: https://www.cs.umd.edu |
ОПИСАНИЕ:
Алгоритъмът на Дейкстра е най-ефективният начин за намиране на минималния път (т.е. пътят с минимално тегло) от даден връх до всички останали в ориентиран граф с тегла.
Важното за този алгоритъм е, че теглата трябва да се положителни числа, иначе няма да работи коректно.
АЛГОРИТЪМ:
На всеки възел на графа поставяме в съответствие запис с 3 полета:
- V - признак за обработен (маркиран) връх (0 - необработен, 1 - обработен)
- D - дължина на пътя до този връх
- P - връх предшественик на дадения връх в пътя.
1. Инициализация:
- на полетата V за всеки връх присвояваме стойности 0;
- на полетата D за всеки връх присвояваме стойности БЕЗКРАЙНОСТ (само началният е със стойност 0);
- на полетата P за всеки връх присвояваме стойности -1.
2. Повтаряме толкова пъти колкото са върховете:
- избираме връх с НАЙ-МАЛКА ДОСЕГАШНА ДЪЛЖИНА на пътя,
измежду НЕОБРАБОТЕНИТЕ върхове (обозначаваме го като 'x')
(в началото това е началният връх, тъй като изкуствено сме направили дължината на пътя до него 0)
- маркираме обработения връх като посетен (променяме V стойността му на 1)
- за всеки НЕОБРАБОТЕН (V = 0) съсед 'y' на 'x'
ако x.D + дължината на дъгата (x,y) <= y.D тогава
y.D = x.D + дължината на дъгата (x,y)
y.P = x.
ПРИМЕР:
Нека имаме следния граф:
Първата ни стъпка е да видим колко върха има в този граф. В случая са 7, следователно ще ни трябва таблица със 7 реда и 3 колони (по 1 за съответно V, D и P стойностите на всеки връх).
Избираме 1 за начален връх (но може да е който и да е от другите).
Сега нека определим какви ще са стойностите за V, D и P в началото.
Алгоритъмът ни казва, че за V, всички върхове в началото имат стойност 0 (не са "обработени" все още), включително и началният.
За D поставяме стойността 0 за началния връх (тъй като пътят от началния връх до него самия винаги е 0), но за другите поставяме стойността "∞" (безкрайност), защото тази стойност ще участва в сравненията в стъпка 2 (разбира се, ако имплементираме алгоритъма на език за програмиране, бихме използвали конкретна стойност).
За стойностите на P, решението е просто - поставяме стойността -1 (тъй като все още нямат предшественик и няма връх -1). Ако съществува връх -1, ще се наложи да изберем друга стойност, за да е коректно изпълнен алгоритъмът.
И така, след всичко това, началната ни таблица ще изглежда така:
V
|
D
|
P
|
|
1
|
0
|
0
|
-1
|
2
|
0
|
∞
|
-1
|
3
|
0
|
∞
|
-1
|
4
|
0
|
∞
|
-1
|
5
|
0
|
∞
|
-1
|
6
|
0
|
∞
|
-1
|
7
|
0
|
∞
|
-1
|
x.D + 2 <= y.D (2 е дължината на дъгата (x,y))
---> 0 + 2 <= ∞
---> ВЯРНО
---> y.D = x.D + 2
---> y.D = 2
x.D + 1 <= y.D
---> 0 + 1 <= ∞
---> ВЯРНО
---> y.D = x.D + 1
---> y.D = 1
Добавяме подчертаните стойности в обновена таблица:
1
|
|||
V
|
D
|
P
|
|
1
|
1
|
0
|
-1
|
2
|
0
|
2 |
1
|
3
|
0
|
∞
|
-1
|
4
|
0
|
1 |
1
|
5
|
0
|
∞
|
-1
|
6
|
0
|
∞
|
-1
|
7
|
0
|
∞
|
-1
|
Продължаваме по същия принцип. Виждаме, че върхът с най-малка досегашна дължина (от непосетените) е връх 4 (с досегашна дължина 1). x = 4
Маркираме го като посетен, т.е. x.V = 1.
За наше нещастие виждаме, че върхът има доста непосетени съседи - 3, 6, 7 и 5.
Това не е проблем, разбира се. Правим същите изчисления като за предишната итерация:
x.D + 1 <= y.D
---> 1 + 2 <= ∞
---> ВЯРНО
---> y.D = 1 + 2
---> y.D = 3
x.D + 8 <= y.D
---> 1 + 8 <= ∞
---> ВЯРНО
---> y.D = 1 + 8
---> y.D = 9
x.D + 4 <= y.D
---> 1 + 4 <= ∞
---> ВЯРНО
---> y.D = 1 + 4
---> y.D = 5
x.D + 2 <= y.D
---> 1 + 2 <= ∞
---> ВЯРНО
---> y.D = 1 + 2
---> y.D = 3
---> y.P = 4
4
| |||
V
|
D
|
P
| |
1
|
1
|
0
|
-1
|
2
|
0
| 2 |
1
|
3
|
0
| 3 |
4
|
4
|
1
| 1 |
1
|
5
|
0
| 3 |
4
|
6
|
0
| 9 |
4
|
7
|
0
| 5 |
4
|
Бързо виждаме, че от непосетените върхове, сега връх 2 има минималната досегашна дължина (2.D = 2). Намерихме следващия връх, т.е. x = 2 и следователно x.V = 1 (маркираме го като посетен).
Съседи на 2 са 4 и 5, но за радост 4 вече е посетен, така че няма да се занимаваме с него. Правим изчисления за непосетения връх 5:
x.D + 10 <= y.D
---> 2 + 10 <= 3
---> НЕВЯРНО
---> не променяме никакви други стойности
Този път само маркираме текущия връх като посетен в обновена таблица:
2
|
|||
V
|
D
|
P
|
|
1
|
1
|
0
|
-1
|
2
|
1
|
2
|
1
|
3
|
0
|
3
|
4
|
4
|
1
|
1
|
1
|
5
|
0
|
3
|
4
|
6
|
0
|
9
|
4
|
7
|
0
|
5
|
4
|
Сега се намираме в доста интересна ситуация. Виждаме, че има два върха от непосетените, които имат минимална досегашна дължина - върховете 3 и 5 (с дължина 3). Няма значение кой от двата ще изберем първо.
Все пак, нека изберем 3 за тази итерация, т.е. x = 3 и x.V = 1.
Съседи на 3 са 1 и 6, но само 6 е непосетен. Правим обичайните изчисления:
x.D + 5 <= y.D
---> 3 + 5 <= 9
---> ВЯРНО
---> y.D = 3 + 5
---> y.D = 8
---> y.P = 3
Добавяме подчертаните стойности към обновена таблица:
3
|
|||
V
|
D
|
P
|
|
1
|
1
|
0
|
-1
|
2
|
1
|
2
|
1
|
3
|
1
|
3
|
4
|
4
|
1
|
1
|
1
|
5
|
0
|
3
|
4
|
6
|
0
|
8
|
3
|
7
|
0
|
5
|
4
|
Следващият връх, който ще посетим, ще е 5, тъй като дължината му е минимална. x = 5 и x.V = 1.
5 има само един непосетен съсед - 7. Правим изчисленията:
x.D + 1 <= y.D
---> 3 + 1 <= 5
---> ВЯРНО
---> y.D = 3 + 1
---> y.D = 4
---> y.P = 5
Добавяме отново подчертаните стойности към обновена таблица:
5
|
|||
V
|
D
|
P
|
|
1
|
1
|
0
|
-1
|
2
|
1
|
2
|
1
|
3
|
1
|
3
|
4
|
4
|
1
|
1
|
1
|
5
|
1
|
3
|
4
|
6
|
0
|
8
|
3
|
7
|
0
|
4
|
5
|
Останаха ни само два върха. 7 има по-малка стойност за D, затова избираме него. x = 7 и x.V = 1.
7 има един непосетен връх и това е 6. Правим изчисленията:
x.D + 1 <= y.D
---> 4 + 1 <= 8
---> ВЯРНО
---> y.D = 4 + 1
---> y.D = 5
---> y.P = 7
Добавяме подчертаните стойности:
7
|
|||
V
|
D
|
P
|
|
1
|
1
|
0
|
-1
|
2
|
1
|
2
|
1
|
3
|
1
|
3
|
4
|
4
|
1
|
1
|
1
|
5
|
1
|
3
|
4
|
6
|
0
|
5
|
7
|
7
|
1
|
4
|
5
|
Остана ни само един връх - 6. Той очевидно няма непосетени съседи, така че просто го маркираме като посетен и обновяваме таблицата:
6
|
|||
V
|
D
|
P
|
|
1
|
1
|
0
|
-1
|
2
|
1
|
2
|
1
|
3
|
1
|
3
|
4
|
4
|
1
|
1
|
1
|
5
|
1
|
3
|
4
|
6
|
1
|
5
|
7
|
7
|
1
|
4
|
5
|
Това е финалната версия на нашата таблица и алгоритъмът завършва.
Добре, моментът на истината настъпи. Как да използваме тази скапана таблица, за да определим най-краткия път от 1 до другите върхове?
Много просто. Гледаме крайния връх, който ни интересува. Да кажем 6. Виждаме, че в P колоната му е 7. Това означава, че 7 е негов предшественик. В колоната P на 7 пък виждаме стойността 5. Значи 5 е предшественик на 7. 4 пък е предшественик на 5. Най-накрая виждаме, че 1 е предшественик на 4.
От това следва, че най-краткият път до 6 е 1 -> 4 -> 5 -> 7 -> 6. Ако сметнем общата дължина, тя е 1+2+1+1 = 5 (каквато е и D стойността на крайния връх 6).
По този начин можем да намерим най-краткия път до който и да е друг връх (не забравяйте обаче, че начален винаги трябва да e 1 и ако искаме да използваме друг за начален, трябва да повторим алгоритъма отново).
---
Това е за днес! Ако видите някоя неточност, моля кажете ми! 😉
Няма коментари:
Публикуване на коментар