Алгоритмы на графах

жүктеу/скачать 0,92 Mb.

бет	1/4
Дата	16.11.2022
өлшемі	0,92 Mb.
	#50601

1 2 3 4

Байланысты:
Алгоритмы на графах тех прог

Основные алгоритмы
Алгоритм Дейкстры
Алгоритм работает только для графов без рёбер отрицательного веса.
Формулировка задачи
Алгоритм

Алгоритмы на графах

Алгоритм	Объект работы	Действие	Сложность		Доп. память	Полезн.
			Матрица	Список
Поиск в ширину	Невзвеш-й граф	Поиск кратчайшего расстояния от одной вершины до всех остальных, определение количества компонент связности, определение двудольности графа	O(N2)	O(M)	O(N)	10
Поиск в глубину	Невзвеш-й граф	Определение количества компонент связности, построение дерева поиска в глубину, поиск точек сочленения и мостов, определение двудольности графа	O(N2)	O(M)	O(N)	8
Алгоритм Дейкстры	Взвеш-й граф без рёбер отрицат-го веса	Поиск кратчайшего расстояния от одной вершины до всех остальных	O(N2)	O(N2),	O(N)	10
Алгоритм Форда-Беллмана	Взвешенный граф	Поиск кратчайшего расстояния от одной вершины до всех остальных	O(N3)	O(MN)	O(N)	5
Алгоритм Флойда	Взвешенный граф	Поиск кратчайшего расстояния между каждой парой вершин	O(N3)		O(N2)	8

Основные алгоритмы

Нахождение кратчайших путей из одного источника: алгоритм Дейкстры.
Построение минимального остова графа: алгоритм Крускала.
Задача о лабиринте и поиск в глубину на неориентированном графе.

Алгоритм Дейкстры

Э́дсгер Ви́бе Де́йкстра (Edsger Wybe Dijkstra [ˈɛtsxər ˈʋibə ˈdɛikstra]) (11 мая 1930, Роттердам, Нидерланды — 6 августа 2002) — нидерландский учёный, идеи которого оказали влияние на развитие компьютерной индустрии.

Алгоритм Дейкстры

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

Алгоритм работает только для графов без рёбер отрицательного веса.

Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

Формулировка задачи

Дан взвешенный ориентированный граф без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины а до всех остальных вершин этого графа

Граф называется взвешенным или нагруженным, если каждому ребру поставлено в соответствии некоторое число w (вес).

Алгоритм

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до а. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Метка самой вершины а полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

жүктеу/скачать 0,92 Mb.

Достарыңызбен бөлісу:

1 2 3 4