Алгоритм Дейкстры — различия между версиями

Версия 11:23, 16 января 2024

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

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_{p_k}, p_k, k}.

@@ Строка 1: / Строка 1: @@
 '''Алгоритм Дейкстры''' — это алгоритм нахождения минимальных расстояний и маршрутов от заданного пункта до остальных.
 == Обозначения ==
-Введём обозначения.
 '''k''' – число пунктов (вершин графа);
@@ Строка 27: / Строка 25: @@
 Выходные данные: '''{s<sub>n1</sub>, s<sub>n2</sub>, ..., s<sub>nk</sub>};'''
 '''{p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>k</sub>}'''.
+*Заметим, что оптимальный маршрут из пункта '''n''' в пункт '''k''' имеет длину '''s<sub>nk</sub>''' и вид '''{n, ... , p<sub>p<sub>k</sub></sub>, p<sub>k</sub>, k}'''.
-* Заметим, что оптимальный маршрут из пункта '''n''' в пункт '''k''' имеет длину '''s<sub>nk</sub>''' и вид '''{n, ... , p<sub>p<sub>k</sub></sub>, p<sub>k</sub>, k}'''.
 == [[Логистические алгоритмы|Другие алгоритмы:]] ==
-{{Список АлгЛ}}
+{{Список ЛАлг}}
 == Ссылки ==
 * [[Участник:Logic-samara]]
 [[Категория:Логистика]][[Категория:Алгоритмы]]