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

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

Обозначения

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}.

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

1. алгоритм Дейкстры;
2. алгоритм Флойда;
3. алгоритм Ху;
4. алгоритм Джонсона;
5. алгоритм построения сетевого графика;
6. алгоритм построения графика Гантта.

Ссылки

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