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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене
Начин на обхождане на алгоритъма на Дейкстра

Алгоритъм на Дейкстра, наречен на името на откривателя си Едсхер Дейкстра (Edsger Dijkstra), служи за пресмятане на най-къс път от даден връх до всички останали в ориентиран граф с не отрицателни тегла на ребрата. Алгоритъма съществува в много варианти, по-често използвания вариант определя един връх като "начален" и намира най-късото разстояние от началния до всички останали върхове в граф. Алгоритъма може да бъде използван и за намиране на най-краткото разстояние от един връх до върха на дадена дестинация, чрез спиране на алгоритъма, след като най-краткия път до върха на дестинацията е била определена. Например, ако върховете на даден граф представляват градове и крайните точки представляват разстоянието между два града свързани с директен път, алгоритъма на Дейкстра може да бъде използван за намиране на най-краткия път между даден град и всички останали градове. Може да се модифицира и да се използва за намиране на някои други видове оптимални пътища. Като резултат, алгоритъма за намиране на най-краткият път е широко използван в мрежовите протоколи за маршрутизация, най-вече в IS-IS и OSPF.

Алгоритъмът намира приложение най вече в информатиката и логистиката, където често се търси най-късото разстояние между две точки (в програма за GPS устройства, където трябва да се планира най-краткото трасе между стартовата и крайната позиция; оптимизация на транспорта; задача за търговския пътник ... )

История[редактиране | редактиране на кода]

Дейкстра мисли за най-краткия път към проблема, когато работи в Математическия център в Амстердам през 1956 г. като програмист да демонстрира възможностите на нов компютър, наречен ARMAC. Неговата цел е да се избират и двете: проблем, както и отговор (които могат да бъдат получени от компютър), които хората без компютри биха могли да разберат. Той проектира най-краткия път до алгоритъм за около 20 минути, без помощ от хартия и писалка, и по-късно го реализира за ARMAC за малко по-опростена преносима/транспортна карта от 64 градове в Холандия (ARMAC е бил 6-битов компютър и по този начин е могъл да поддържа/държи 64 места/градове). Една година по-късно, той се натъкнал на друг проблем от хардуерни инженери, които работели по следващия компютър на института: минимизиране на количеството на тел, необходима за свързване на изводите на задния панел на устройството. Като решение, той преоткрива алгоритъм, известен като алгоритъма "Оптимално покриващо дърво на Прим" (познато по-рано от Ярник, а също и преоткрито от Прим). Дейкстра публикувал алгоритъма през 1959 г., две години след Прим и 29 години след Ярник.

Описание на алгоритъма[редактиране | редактиране на кода]

Алгоритъмът на Дейкстра, както този на Белман-Форд, използва техниката на релаксация. Първоначално всеки връх има безкрайна дължина, която се намалява при изпълнение на алгоритъма. Нека r е избраният начален връх, а c*(i, j) е теглото на реброто от i до j или безкрайност, ако такова не съществува. Алгоритъмът работи, като поддържа дължината d(i) на намерения до момента най-кратък път от r до всеки връх i и постепенно разширява множество S от върховете, за които тази дължина със сигурност е оптимална. Първоначално d(i)=c*(r, i), а S={r}. На всяка итерация алгоритъмът избира такъв връх v, който не е в S и d(v) е минимално. Върхът v се добавя в S и се извършва релаксация: за всеки връх j, който не е в S, d(j)=min(d(j), d(v)+c*(v, j)). Алгоритъмът приключва, когато всички върхове на графа са в множеството S.

Доказателство за коректност[редактиране | редактиране на кода]

Доказателство чрез индукция от броя на посетените възли.

Непроменлива хипотеза: За всеки посетен възел ф, дист [ф] е най-късото разстояние от източника до ф; и за всеки непосещаван V, дист [V] е най-късото разстояние чрез посетените възли само от източника до V (ако съществува такава пътека, в противен случай е безкрайност; имайте предвид, че не приемаме, че дист [V] е действително най-късото разстояние на непосетените възли).

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

Приемаме хипотезата за N-1 посетени възли. Сега ние избираме един ръб UV където V е най-ниската DIST [V] на всеки непосещаван възел и ръба UV е такъв, че {{{1}}}. дист [V] трябва да е най-късото разстояние от източника до V, защото ако имаше по-кратък път, и ако W е първият непосетен възел по този път, после хипотеза дист [W]> дист [V] създава противоречие. По същия начин, ако имаше по-кратък път до V, без да използваме непосетени възли, тогава дист [V] щеше да е по-малко от дист [ф] + дължина [U, V].

След обработка v все още ще бъде вярно, че за всеки непосетен възел w, дист [W] е най-късото разстояние от източника до w, използвайки само посетените възли, тъй като, ако имаше по-кратък път, който не посетите V щяхме да го намери преди това, и ако имаше по-кратък път, които не ползват(посещават) V, щяха да бъдат открити преди това. А ако има по-кратък път, ползващ V, обновяваме го при обработката на V.

Сложност[редактиране | редактиране на кода]

Нека алгоритъмът се прилага върху граф G(V, E). Най-простата реализация използва матрица на съседство за представяне на графа и едномерен вектор за съхранение на стойностите на d(). Сложността по време и по памет е O(|V|2). Ако графът бъде представен чрез списъци на съседите и за намиране на всеки следващ връх се използва приоритетна опашка(напр. Фибоначиеви пирамиди), сложността по време е O(E + |V|.log|V|), а по памет е O(|E|+|V|).

Външни препратки[редактиране | редактиране на кода]

Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Dijkstra's algorithm“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.