Алгоритм Дейкстры

Эта статья находится в разработке!

Алгоритм

В ориентированном взвешанном графе [math]G = (V, E)[/math], вес рёбер которого неотрицателен, Алгоритм Дейкстры находит длинну кратчайшего пути из одной вершины [math]s[/math] до всех остальных.

Псевдокод

Dijkstra([math]G[/math], [math]w[/math], [math]s[/math])
    [math]d \gets \infty[/math]
    [math]d[s] \gets 0[/math]
    [math]S \gets \emptyset[/math]
    [math]Q \gets V[G][/math]
    while [math]Q \neq \emptyset[/math]
        do [math]u \gets[/math] Extract_Min([math]Q[/math])
           [math]s \gets S \cup \{u\}[/math]
           for [math](uv) \in E[/math]
               do Relax([math]u[/math], [math]v[/math], [math]w[/math])

литература

• Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)