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

Материал из Мегапедии
Перейти к: навигация, поиск
(начало)
 
м
Строка 29: Строка 29:
  
 
*Заметим, что оптимальный маршрут из пункта '''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:54, 5 января 2021

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

Обозначения

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

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

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

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

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

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

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

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

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

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

Алгоритм

Входные данные: k; n; V; G; {d12, d13, ..., dk k-1}.

АДЕ01.JPG

Выходные данные: {sn1, sn2, ..., snk}; {p1, p2, ..., pk}.

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

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

Ссылки