Алгоритм Дейкстры — различия между версиями
м |
|||
Строка 33: | Строка 33: | ||
== Ссылки == | == Ссылки == | ||
*[[Участник:Logic-samara]] | *[[Участник:Logic-samara]] | ||
− | [[Категория:Логистика]][[Категория:Алгоритмы]] | + | [[Категория:Математика]][[Категория:Логистика]][[Категория:Алгоритмы]] |
Текущая версия на 05:04, 10 апреля 2023
Алгоритм Дейкстры — это алгоритм нахождения минимальных расстояний и маршрутов от заданного пункта до остальных.
Содержание
Обозначения
Введём обозначения.
k – число пунктов (вершин графа);
V – множество вершин графа (пунктов);
E – множество "не просмотренных" вершин;
J – множество конечных вершин дуг исходящих из "просматриваемой" вершины;
G – множество дуг графа (дорог между пунктами);
dij – расстояние от пункта i до пункта j, зависящее от направления;
snj – наименьшее расстояние от пункта n до пункта j;
pj – пункт в оптимальном маршруте, предшествующий пункту j;
n – начальный пункт.
Алгоритм
Входные данные: k; n; V; G; {d12, d13, ..., dk k-1}.
Ошибка создания миниатюры: Не удаётся сохранить эскиз по месту назначения
Выходные данные: {sn1, sn2, ..., snk}; {p1, p2, ..., pk}.
- Заметим, что оптимальный маршрут из пункта n в пункт k имеет длину snk и вид {n, ... , ppk, pk, k}.