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

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

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

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

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

Алгоритъмът на Дейкстра, както този на Белман-Форд, използва техниката на релаксация. Първоначално всеки връх има безкрайна дължина, която се намалява при изпълнение на алгоритъма. Нека 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.

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

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

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