Алгоритм Дейкстры - История изменений

Logic-samara в 11:38, 16 января 2024

2024-01-16T11:38:55Z

Logic-samara в 11:23, 16 января 2024

2024-01-16T11:23:36Z

Logic-samara в 02:54, 31 марта 2019

2019-03-31T02:54:47Z

Logic-samara в 11:23, 29 декабря 2017

2017-12-29T11:23:26Z

Logic-samara в 17:29, 1 февраля 2016

2016-02-01T17:29:05Z

Logic-samara: Новая страница: «'''Алгоритм Дейкстры''' — это алгоритм нахождения минимальных расстояний и маршрутов от з…»

2016-01-15T16:59:13Z

Новая страница: «'''Алгоритм Дейкстры''' — это алгоритм нахождения минимальных расстояний и маршрутов от з…»

Новая страница

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

'''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}'''.
== Другие алгоритмы: ==
*[[Алгоритм Джонсона]];
*[[Алгоритм Флойда]];
*[[Алгоритм Ху]].
== Ссылки ==
* [[Участник:Logic-samara]]
[[Категория:Логистика]][[Категория:Алгоритмы]]

@@ Строка 29: / Строка 29: @@
 {{Список ЛАлг}}
 == Ссылки ==
-* [[Участник:Logic-samara]]
+*[[Участник:Logic-samara]]
-[[Категория:Логистика]][[Категория:Алгоритмы]]
+[[Категория:Математика]][[Категория:Алгоритмы]][[Категория:Логистика]]

@@ Строка 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]]
 [[Категория:Логистика]][[Категория:Алгоритмы]]

@@ Строка 30: / Строка 30: @@
 * Заметим, что оптимальный маршрут из пункта '''n''' в пункт '''k''' имеет длину '''s<sub>nk</sub>''' и вид '''{n, ... , p<sub>p<sub>k</sub></sub>, p<sub>k</sub>, k}'''.
 == Другие алгоритмы: ==
-*[[алгоритм Дейкстры]];
+{{Список АлгЛ}}
-*[[алгоритм Джонсона]];
-*[[алгоритм Флойда]];
-*[[алгоритм Ху]].
 == Ссылки ==
 * [[Участник:Logic-samara]]
 [[Категория:Логистика]][[Категория:Алгоритмы]]