Оптимизационни задачи. Най-къс път. Част 1 - алгоритъм на Dijkstra.

Класове оптимизационни задачи за най-къс път.

Основните класове задачи за най-къс път са :

  1. най-къси пътища от даден връх до всички останали;
  2. най-къс път между два дадени върха от графа;
  3. най-къс път от всеки връх в графа, до всеки друг връх;

По-горните класове задачи ще бъдат разглеждани за графи със следните характеристики:

  1. графи, в които теглото на всяко ребро е неотрицателно число;
  2. произволни графи, с произволни тегла на ребрата;
  3. ациклични графи;
  4. графи, в които теглото на всяко ребро е 1;

Алгоритми за решаване на задачи за най-къс път в граф.

Естествено началото е за един от най-комерсиалните алгоритми - алгоритъмът на Дейкстра (Dijkstra). Причините, поради които този алгоритъм е толкова известен са няколко. Той е доста понятен и някак естествен (в сравнение с други алгоритми за решаване на същия тип задачи). Лесно се имплементира на PC и прилага на лист. Когато се наложи да се ползва, всичко, което е нужно, е малко практика. Дава добри резултати при имплементация на PC откъм време, с някои оптимизации естествено.

Алгоритъм на Дейкстра

Преди да изложа алгоритъма, първо някои пояснения:
Ще вземем граф G(V, A) с N върха и неотрицателни стойности на дъгите (ще видим по-късно защо това е от значение), номерирани от 1 до N. Избираме като начален връх върха с номер 1 и ще търсим най-късите пътища от него до всички останали.
нека с:

  • $d_i$ бележим най-късия път от връх $1$ до връх $i$.
  • $d^*_i$ бележим временно най-късия път от връх $1$ до връх $i$.
  • curNode запишем върхът, който сме избрали да прибавим на дадената стъпка от алгоритъма.
  • S осначим множеството на всички върхове от графа, за който още не знаем най-късия път до тях.
  • $l(i, j)$ означим теглото на реброто с начало връх $i$ и край връх $j$.
  • с $prev_i$ ще означаваме предшественика на върхът $i$ по пътя от връх $1$ до връх $i$, иначе казано това ще е нашият списък на бащите. Тук е важно да се направи една забележка: Запаметяването на пътя по този линеен по памет начин е единствено осъществимо от факта, че най-късият път, между всеки два върха в нашия граф, е прост. Последното следва от липсата на отрицателни цикли. От това, че алгоритъмът намира прости пътища, следва че графът $G`(V, A`)$, подграф на $G$ със същите върхове, но с дъги само дъгите участващи в най-късите пътища от $1$ до всички останали върхове, и без ориентация на дъгите, всъщност е дърво (последното е доста важно).

Ето и самият алгоритъм.
Първоначално настройваме:

  1. $S = {1, 2, 3 ... N}$;
  2. $d^*_i = \inf$, за всяко $i = 1$ да $N$;
  3. $d^*_1 = 0$;
  4. $prev_i = -1$, за всяко $i = 1$ до $N$;

Действията извършвани във всяка стъпка от алгоритъма:

  1. dcurNode = d*curNode;
  2. S = S / {curNode};
  3. Ако $S = \varnothing$, край;
  4. за всеки връх j от S , такъв че $(curNode, j) \in A$, преизчисляваме : ако d*j > dcurNode + l(curNode, j), то prevj = curNode и разбира се d*j = dcurNode + l(curNode, j);
  5. минаваме през всеки елемент от S и избираме елемента j с най-къс временно най-къс път d*j ,избираме curNode = j;
  6. отиваме на 1-а стъпка от алгоритъма;

Лема Да докажем, че избраният за curNode на всяка стъпка връх действително притежава качеството временно най-късият до него път d*curNode да е и глобално най-къс.

Доказателство

Сложност на алгоритъма на Дейкстра Сложност поначало не сме дефинирали като отделно понятие, но не мисля да се впускам в обяснения. Който иска може да потърси из нета материали по темата, останалите - ще се учи някъде около четвърти семестър. Като цяло, алгоритъмът на Дейкстра "върви" (или влиза в нова стъпка) докато $S \ne \varnothing$ и на всяка стъпка добавя по един връх, следователно имаме N на брой стъпки, където N е броят на върховете. Във всяка стъпка, действие 4 изисква да се обходят всички съседи на curNode, а на действие 5 преминаваме през всички "неизбрани" до момента върхове, за да фиксираме най-оптималния. Другите действия - 1, 2, 3, 6 - са с константна сложност (О(1)). Като имаме предвид, че не разглеждаме мултиграф, може да приемем че стъпка 4 е с не по-голяма сложност от стъпка 5 (в общия случай), а стъпка 5 е с линейна сложност (O(N)), следователно сложността на всяка стъпка е линейна (сложността на една стъпка е сложността на най-скъпото действие в нея). N на брой стъпки с O(N) сложност ни дават O(N2) сложност. Тук идва един тънък момент, който не бива да се пропуска - сумирането на действие 4 от всяка от N-е стъпки ни дава общия брой на ребрата - M, заради което сложността на алгоритъма без оптимизации достига O(M + N2) = O(N2)( N2 ≥ M ⇒ 2N2 ≥ M + N2 ). Kогато започнем да оптимизираме, това M не е за изпускане, понеже не може да не прегледаме всички ребра, тоест си остава в сложността на алгоритъма, колкото и да оптимизираме останалата част. С оптимизации е възможно да ускорим изпълняването на стъпка 5 до логаритмична сложност (O(log2N)) с помощта на абстрактна структура от данни, наречена пирамида heap, което ни дава O(M + Nlog2N) оптимална сложност на алгоритъма.

Сега да видим как работи алгоритъмът с един прост пример. По принцип няма да има примери след всеки алгоритъм, защото това би било излишно, но поради популярността му смятам че е добре да бъде максимално понятно обяснен.
Нека нашият неориентиран (за алгоритъма ориентацията на графа е без значение) граф G(V, A) има следните характеристики

Дъга Тегло
(1, 3) 5
(1, 4) 8
(3, 4) 2
(3, 5) 3
(4, 2) 3
(4, 6) 7
(5, 2) 6
(2, 6) 2
Матрица на съседство:
1 2 3 4 5 6
1 0 0 5 8 0 0
2 0 0 0 3 6 2
3 5 0 0 2 3 0
4 8 3 2 0 0 7
5 0 6 3 0 0 0
6 0 2 0 7 0 0

Цел: да се намерят най-късите пътища от връх 1 до всички останали.
Инициализацията е ясна, ето какво се случва при прилагането на алгоритъма по стъпки. В таблицата, за всеки връх динамично се подновява стойността на временно най-късия път, докато съответният връх все още се намира в S. i-ият ред съответства на i-та стъпка от алгоритъма, или по-точно информацията, с която разполагаме в началото ѝ. Щом даден връх бива избран за curNode на дадена стъпка, то в реда съответстващ на стъпката той ще е с удебелен шрифт.

стъпка N# d*1 d*2 d*3 d*4 d*5 d*6
1 0 inf inf inf inf inf
2 0 inf 5 8 inf inf
3 0 inf 5 7 8 inf
4 0 10 5 7 8 14
5 0 10 5 7 8 14
6 0 10 5 7 8 12

Ето и нещо за хората които си купуват списания и книги заради картинките(като мен), - визуална реализация на написаното в таблицата:
Забележка: Картинките са взети директно от сайта на Американската олимпиада по информатика. Надяваме се да не ни съдят :)

sp.exec1.gif sp.exec2.gifsp.exec3.gifsp.exec4.gifsp.exec5.gifsp.exec6.gifsp.exec7.gif

Примерна задача : http://acm.timus.ru/problem.aspx?space=1&num=1031.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License