Легостаев Максим в 05:33, 22 декабря 2025

2025-12-22T05:33:55Z

Легостаев Максим в 05:32, 22 декабря 2025

2025-12-22T05:32:16Z

Легостаев Максим: Новая страница: «'''Алгоритм Дейкстры''' — алгоритм на графах, изобретённый нидерландским учёным [[Дейкстр…»

2025-12-16T03:30:29Z

Новая страница: «'''Алгоритм Дейкстры''' — алгоритм на графах, изобретённый нидерландским учёным [[Дейкстр…»

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

'''Алгоритм Дейкстры''' — алгоритм на графах, изобретённый нидерландским учёным [[Дейкстра, Эдсгер Вибе|Эдсгером Дейкстрой]] в 1959 году. Находит [[Кратчайший путь|кратчайшие пути]] от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

__TOC__

== Математическое описание ==
Алгоритм Дейкстры использует [[Жадный алгоритм|жадную стратегию]]. Для каждой вершины ''v'' хранится текущая длина <math>d[v]</math> кратчайшего пути из начальной вершины ''s'' в ''v'', а также булевый флаг <math>used[v]</math> — посещена ли вершина.

Изначально <math>d[s] = 0</math>, для всех остальных вершин расстояние считается бесконечным (<math>d[v] = \infty</math>), <math>used[v] = false</math>.

На каждом шаге алгоритма выбирается вершина <math>u</math> с минимальным <math>d[u]</math> среди ещё не посещённых. Для каждого соседа <math>v</math> вершины <math>u</math> пересчитывается расстояние:

<math>d[v] = \min(d[v], d[u] + w(u, v))</math>

где <math>w(u, v)</math> — вес ребра из <math>u</math> в <math>v</math>.

Алгоритм завершается, когда все вершины посещены или минимальное расстояние среди непосещённых равно бесконечности.

== Пример реализации на Python ==
<syntaxhighlight lang="python">
import heapq

def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]

while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)

if current_distance > distances[current_vertex]:
continue

for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))

return distances

# Пример графа в виде словаря смежности
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}

print(dijkstra(graph, 'A'))
</syntaxhighlight>

== Химическая аналогия ==
Процесс поиска кратчайшего пути можно сравнить с [[Диффузия|диффузией]] вещества в среде с переменной проводимостью. Рассмотрим реакцию диффузии ионов через мембрану:

<chem>Na^+_{(aq)} + Cl^{-}_{(aq)} ->[\text{diffusion}] Na^+_{(membrane)} + Cl^{-}_{(membrane)}</chem>

Скорость перемещения ионов аналогична «весу» ребра в графе — чем выше проводимость (меньше сопротивление), тем быстрее ион достигает цели, что соответствует меньшему весу ребра в алгоритме Дейкстры.

== Примечания ==
{{примечания}}
<ref name="Dijkstra1959">{{статья|автор=Dijkstra, E.W.|заглавие=A note on two problems in connexion with graphs|издание=Numerische Mathematik|год=1959|том=1|страницы=269—271}}</ref>
<ref name="Cormen">{{книга|автор=Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К.|заглавие=Алгоритмы: построение и анализ|издание=2-е|место=М.|издательство=Вильямс|год=2005|страницы=595—601}}</ref>

== См. также ==
* [[Алгоритм Беллмана — Форда]]
* [[Алгоритм Флойда — Уоршелла]]
* [[Алгоритм A*]]
* [[Теория графов]]

== Литература ==
* {{книга|автор=Дейкстра Э. В.|заглавие=Заметки по структурному программированию|место=М.|издательство=Мир|год=1975|страницы=34—45}}

[[Категория:Алгоритмы на графах]]
[[Категория:Теория графов]]
{{DEFAULTSORT:Дейкстры, Алгоритм}}

← Предыдущая		Версия 05:33, 22 декабря 2025
Строка 1:		Строка 1:
−	[[Файл:~~вик1~~.jpg]][[Файл:вик2.jpg]][[Файл:вик3.jpg]]	+	[[Файл:В1.jpg]][[Файл:вик2.jpg]][[Файл:вик3.jpg]]

← Предыдущая		Версия 05:32, 22 декабря 2025
Строка 1:		Строка 1:
−	'''Алгоритм Дейкстры''' — алгоритм на графах, изобретённый нидерландским учёным [[Дейкстра, Эдсгер Вибе\|Эдсгером Дейкстрой]] в 1959 году. Находит [[Кратчайший путь\|кратчайшие пути]] от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.	+	[[Файл:вик1.jpg]][[Файл:вик2.jpg]][[Файл:вик3.jpg]]
		+
		+
		+
		+	'''Полужирное начертание''''''Алгоритм Дейкстры''' — алгоритм на графах, изобретённый нидерландским учёным [[Дейкстра, Эдсгер Вибе\|Эдсгером Дейкстрой]] в 1959 году. Находит [[Кратчайший путь\|кратчайшие пути]] от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

	__TOC__		__TOC__

Wiki Легостаев - История изменений

Легостаев Максим в 05:33, 22 декабря 2025

Легостаев Максим в 05:32, 22 декабря 2025

Легостаев Максим: Новая страница: «'''Алгоритм Дейкстры''' — алгоритм на графах, изобретённый нидерландским учёным [[Дейкстр…»