Алгоритам на Дијкстра

Теоријата на графови е посебна гранка во математиката која се занимава со проучување на графовите и нивните својства. За нас информатичарите тоа е една посебно интересна област бидејќи има широка примена во информатиката. Позната е примената на графовите кај описот на моделот на податоците, структурите на податоците, во програмирањето и во компјутерските мрежи. Кај компјутерските мрежи графовите се користат за моделирање и анализирање на мрежниот сообраќај, како и Интернет сообраќајот. Се ова се само некои од примените на графовите.
Графовите се корисни за претставување на многу проблеми од компјутерските науки и во реалниот свет. Апликациите за претставување на графови се движат од прилично едноставни, да дознаеме дали еден јазол е достапен од друг јазол, до екстремно сложени, како наоѓање на патека која поминува низ јазлите и минимизирање на вкупното време. Заеднички, но решлив проблем е наоѓање на едноставна патека. Општо земено, задачата е утврдување на најкратката можна патека од еден почетен јазол, до било кој друг јазол во графот.
Еден од најчестите алгоритми за решавање на овој проблем е алгоритмот на Дијкстра. Осмислен е од страна на познатиот германски математичар и информатичар Edsger W. Dijkstra, кој инаку е познат по многуте алгоритми од областа на математиката и информатиката. Овој алгоритам го решава проблемот за наоѓање на најкратката патека од одреден почетен јазол до било кој друг јазол, каде што нема рабови со негативна тежина и работи на принципот дека најкраткиот можен пат од изворот мора да дојде од една од најкратките можни патеки кои веќе се откриени. Иако негативните тежини некогаш може да бидат и потребни, за многу апликации тие се невозможни, и можноста за негативни тежини може да се игнорира.

1. Опис на алгоритмот

Алгоритмот на Дијкстра работи под претпоставка дека за даден тежински ориентиран граф G = (V, E) за секое ребро (u, v) E важи дека нејзината тежина w(u, v) 0.
Овој алгоритам работи со множество на темиња S до кои е одреден најкраткиот пат од појдовното теме s. Поради тоа за секое теме v S, важи d[v] = (s, v) односно d[v] е бараната тежина на најкраткиот пат. Алгоритмот на Дијкстра ги селектира темињата u V - S така што тие имаат најмал естимиран пат до s, ги вметнува нив во S и ги релаксира сите ребра кои излегуваат од u.

Псевдо код за алгоритмот на Дијкстра:

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 sekoe teme v  Adj[u]
8. do RELAX (u,v,w)

Илустрацијата на овој алгоритам за даден граф е прикажана на Слика 1. Појдовното теме е најлевото теме од графот. Во темињата се означени тековните претпоставени најкратки должини на патеките, додека со темна боја се означени ребрата кои се кон моменталните предходници (кои го сочинуваат моменталното стебло на најкратки патеки). Темињата кои припаѓаат на S се означени со темна боја. Темето означено со сива боја е темето кое е одередено како избрано во линија 5 од псевдо кодот. На Слика 1.а е претставена ситуацијата после иницијализацијата, додека останатите слики соодветствуваат со ситуациите после секоја итерација на циклусот од линиите 4 до 8. Слика 1.ѓ го претставува излезот на алгоритмот.

Слика 1. Илустрација на алгоритмот на Дијкстра за граф со повеќе темиња

2. Примери за алгоритмот на Дијкстра

Пример 1.

Слика 1.

Ако е даден графот на Слика 1. ќе ги имаме овие вредности:

Итерација 1:

Итерација 2:

Итерација 3:

Итерација 4:

Дрвото кое се добива по завршувањето на алгоритамот е:

Пример 2.

Пример 3.

Пример 4.

Доколку во графот се јавуваат и рабови со негативни тежини, во тој случај најкратката патека којашто ќе ја пронајдеме со алгоритмот на Дијкстра ќе биде неточна. Во продолжение следува пример за овој случај.

Образложение

Нека е даден графот на сликата. Почетен јазол е јазолот s. Со алгоритмот на Дијкстра, најкратката патека од s до c ќе биде преку директната врска меѓу овие два јазли, и ќе има тежина 3. Точното би било дека најкратката патека од s до c е преку јазолот b, така што има тежина 1.

3. Заклучок

Во оваа семинарска работа е прикажано како се применува теоријата на графови во информатиката. Го разгледавме најпознатиот алгоритам за наоѓање најкратка патека-алгоритмот на Дијкстра. Исто така дадена е и илустрација на алгоритмот низ повеќе примери.

4. Користена литература

1. http://en.wikipedia.org/wiki/Dijkstra's_algorithm 2. http://mendo.mk/wiki/attach/%D0%9F%D0%98%D0%9D%202009/Dijkstra.pdf 3. http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/dijkstraAlgor.htm