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

Алгоритм Дейкстры — это алгоритм нахождения минимальных расстояний и маршрутов от заданного пункта до остальных.

Обозначения

Введём обозначения.

k – число пунктов (вершин графа);

V – множество вершин графа (пунктов);

E – множество "не просмотренных" вершин;

J – множество конечных вершин дуг исходящих из "просматриваемой" вершины;

G – множество дуг графа (дорог между пунктами);

d_ij – расстояние от пункта i до пункта j, зависящее от направления;

s_nj – наименьшее расстояние от пункта n до пункта j;

p_j – пункт в оптимальном маршруте, предшествующий пункту j;

n – начальный пункт.

Алгоритм

Входные данные: k; n; V; G; {d₁₂, d₁₃, ..., d_{k k-1}}.

Выходные данные: {s_n1, s_n2, ..., s_nk}; {p₁, p₂, ..., p_k}.

• Заметим, что оптимальный маршрут из пункта n в пункт k имеет длину s_nk и вид {n, ... , p_pk, p_k, k}.

Другие алгоритмы:

• алгоритм Дейкстры;
• алгоритм Флойда;
• алгоритм Ху;
• алгоритм Джонсона;
• алгоритм построения сетевого графика;
• алгоритм построения графика Гантта.

Ссылки

• Участник:Logic-samara