AlgorithmO #5 — Алгоритъм на Дейкстра (най-кратък път от даден връх до всички останали за граф с ТЕГЛА)

(Първо публикувано на 07.01.2017)

Днес ще ви представя още един популярен алчен алгоритъм (макар и да се смята за добър пример за алгоритъм на динамичното програмиране).

Този алгоритъм беше един от първите, които научих, и, макар че може да е объркващ, намира широко приложение и си струва да бъде научен.

ОПИСАНИЕ:

Алгоритъмът на Дейкстра е най-ефективният начин за намиране на минималния път (т.е. пътят с минимално тегло) от даден връх до всички останали в ориентиран граф с тегла.

Важното за този алгоритъм е, че теглата трябва да са положителни числа, иначе няма да работи коректно.

АЛГОРИТЪМ:

На всеки възел на графа поставяме в съответствие запис с 3 полета:

• V — признак за обработен (маркиран) връх (0 — необработен, 1 — обработен)

• D — дължина на пътя до този връх

• P — връх предшественик на дадения връх в пътя.

1. Инициализация:

• на полетата V за всеки връх присвояваме стойности 0;

• на полетата D за всеки връх присвояваме стойности БЕЗКРАЙНОСТ (само началният е със стойност 0);

• на полетата P за всеки връх присвояваме стойности -1.

1. Повтаряме толкова пъти колкото са върховете:

• избираме връх с НАЙ-МАЛКА ДОСЕГАШНА ДЪЛЖИНА на пътя, измежду НЕОБРАБОТЕНИТЕ върхове (обозначаваме го като ‘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, ще се наложи да изберем друга стойност, за да е коректно изпълнен алгоритъмът.

И така, след всичко това, началната ни таблица ще изглежда така:

Това беше всичко по първата стъпка от алгоритъма (инициализацията е завършена).

Сега трябва да изберем връх с най-малка досегашна дължина (стойност на D). Това ще е началният връх 1, тъй като на него изкуствено сме му поставили дължина 0.

Приемаме, че с ‘x’ бележим текушия връх и ще го отблелязваме над таблицата за поредната итерация на алгоритъма. Следователно x = 1.

След това маркираме този връх като посетен (променяме V стойността му на 1). Следователно x.V = 1.

Най-накрая следва и най-интересната част. Трябва да разберем кои са всички непосетени съседи на този връх. Поглеждаме графа и виждаме, че това са върховете 2 и 4 (не забравяйте, че това е ориентиран граф и затова гледаме само стрелките, които излизат от върха 1).

Правим няколко изчисления за всеки от тези непосетени съседи на 1:

1) x = 1, y = 2 (x — текущ връх, y — непосетен съсед на текущия връх)

x.D = 0, y.D = ∞
x.D + 2 <= y.D (2 е дължината на дъгата (x,y))
— > 0 + 2 <= ∞
— > ВЯРНО
— > y.D = x.D + 2
— > y.D = 2
— > y.P = x
— > y.P = 1

2) x = 1, y = 4

x.D = 0, y.D = ∞
x.D + 1 <= y.D
— > 0 + 1 <= ∞
— > ВЯРНО
— > y.D = x.D + 1
— > y.D = 1
— > y.P = x
— > y.P = 1

Добавяме стойностите с удебелен шрифт в обновена таблица:

Продължаваме по същия принцип. Виждаме, че върхът с най-малка досегашна дължина (от непосетените) е връх 4 (с досегашна дължина 1). x = 4

Маркираме го като посетен, т.е. x.V = 1.

За наше нещастие виждаме, че върхът има доста непосетени съседи — 3, 6, 7 и 5. Това не е проблем, разбира се. Правим същите изчисления като за предишната итерация:

1) x = 4, y = 3

x.D = 1, y.D = ∞
x.D + 1 <= y.D
— > 1 + 2 <= ∞
— > ВЯРНО
— > y.D = 1 + 2
— > y.D = 3
— -> y.P = x
— > y.P = 4

2) x = 4, y = 6

x.D = 1, y.D = ∞
x.D + 8 <= y.D
— > 1 + 8 <= ∞
— > ВЯРНО
— > y.D = 1 + 8
— > y.D = 9
— > y.P = x
— > y.P = 4

3) x = 4, y = 7

x.D = 1, y.D = ∞
x.D + 4 <= y.D
— > 1 + 4 <= ∞
— > ВЯРНО
— > y.D = 1 + 4
— > y.D = 5
— > y.P = x
— > y.P = 4

4) x = 4, y = 5

x.D = 1, y.D = ∞
x.D + 2 <= y.D
— > 1 + 2 <= ∞
— > ВЯРНО
— > y.D = 1 + 2
— > y.D = 3
— > y.P = x
— > y.P = 4

Това беше за тази итерация! Добавяме подчертаните стойности в обновена таблица:

Бързо виждаме, че от непосетените върхове, сега връх 2 има минималната досегашна дължина (2.D = 2). Намерихме следващия връх, т.е. x = 2 **и следователно x.V = 1 **(маркираме го като посетен).

Съседи на 2 са 4 и 5, но за радост 4 вече е посетен, така че няма да се занимаваме с него. Правим изчисления за непосетения връх 5:

1) x = 2, y = 5

x.D = 2, y.D = 3 (внимавайте — стойността вече не е безкрайност, тъй като беше променена на предишната итерация)
x.D + 10 <= y.D
— > 2 + 10 <= 3
— > НЕВЯРНО
— > не променяме никакви други стойности

Този път само маркираме текущия връх като посетен в обновена таблица:

Сега се намираме в доста интересна ситуация. Виждаме, че има два върха от непосетените, които имат минимална досегашна дължина — върховете 3 и 5 (с дължина 3). Няма значение кой от двата ще изберем първо.

Все пак нека изберем 3 за тази итерация, **т.е. **x = 3 и x.V = 1.

Съседи на 3 са 1 и 6, но само 6 е непосетен. Правим обичайните изчисления:

1) x = 3, y = 6

x.D = 3, y.D = 9
x.D + 5 <= y.D
— > 3 + 5 <= 9
— > ВЯРНО
— > y.D = 3 + 5
— > y.D = 8
— > y.P = x
— > y.P = 3

Добавяме подчертаните стойности към обновена таблица:

Следващият връх, който ще посетим, ще е 5, тъй като дължината му е минимална. x = 5 и x.V = 1.

5 има само един непосетен съсед — 7. Правим изчисленията:

1) x = 5, y = 7

x.D = 3, y.D = 5
x.D + 1 <= y.D
— > 3 + 1 <= 5
— > ВЯРНО
— > y.D = 3 + 1
— > y.D = 4
— > y.P = x
— > y.P = 5

Добавяме отново подчертаните стойности към обновена таблица:

Останаха ни само два върха. 7 има по-малка стойност за D, затова избираме него. x = 7 и x.V = 1.

7 има един непосетен връх и това е 6. Правим изчисленията:

1) x = 7, y = 6

x.D = 4, y.D = 8
x.D + 1 <= y.D
— > 4 + 1 <= 8
— > ВЯРНО
— > y.D = 4 + 1
— > y.D = 5
— > y.P = x
— > y.P = 7

Добавяме подчертаните стойности:

Остана ни само един връх — 6. Той очевидно няма непосетени съседи, така че просто го маркираме като посетен и обновяваме таблицата:

*Това е финалната версия на нашата таблица *и алгоритъмът завършва.

Добре, моментът на истината настъпи. Как да използваме тази скапана таблица, за да определим най-краткия път от 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 и ако искаме да използваме друг за начален, трябва да повторим алгоритъма отново).

—

Това е за днес! Ако видите някоя неточност, моля кажете ми! 😉