Алгоритм Дейкстры — различия между версиями
Материал из ALL
м |
|||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 1: | Строка 1: | ||
'''Алгоритм Дейкстры''' — это алгоритм нахождения минимальных расстояний и маршрутов от заданного пункта до остальных. | '''Алгоритм Дейкстры''' — это алгоритм нахождения минимальных расстояний и маршрутов от заданного пункта до остальных. | ||
== Обозначения == | == Обозначения == | ||
− | |||
− | |||
'''k''' – число пунктов (вершин графа); | '''k''' – число пунктов (вершин графа); | ||
Строка 27: | Строка 25: | ||
Выходные данные: '''{s<sub>n1</sub>, s<sub>n2</sub>, ..., s<sub>nk</sub>};''' | Выходные данные: '''{s<sub>n1</sub>, s<sub>n2</sub>, ..., s<sub>nk</sub>};''' | ||
'''{p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>k</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]] | + | *[[Участник:Logic-samara]] |
− | [[Категория: | + | [[Категория:Математика]][[Категория:Алгоритмы]][[Категория:Логистика]] |
Текущая версия на 11:38, 16 января 2024
Алгоритм Дейкстры — это алгоритм нахождения минимальных расстояний и маршрутов от заданного пункта до остальных.
Содержание
Обозначения
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}.