четвъртък, 27 октомври 2011 г.

Алгоритъм на Дейкстра / Dijkstra's algorithm

Наложи ми се да намеря най-краткият път между две точки в мрежа от такива. Един от колегите ме посъветва да разгледам алгоритъмът на Дейкстра.

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

Ето линкче към файла:
http://www.saylor.org/site/wp-content/uploads/2011/09/CS408-2.3.2-Dijkstras-algorithm.pdf

Още по темата:

Няма коментари:

Публикуване на коментар