Алгоритм Флойда - История изменений

Ctrlalt: /* TLDR */

2024-04-21T13:19:51Z

TLDR

← Предыдущая версия		Версия от 13:19, 21 апреля 2024
Строка 4:		Строка 4:

	<youtube width="300" height="180">LVnPNWwd-yo</youtube>		<youtube width="300" height="180">LVnPNWwd-yo</youtube>
	<youtube width="300" height="180">~~LnOOuNcRLIo~~</youtube>		<youtube width="300" height="180">4njNaLG5p1A</youtube>

	== Код ==		== Код ==

Ctrlalt: /* TLDR */

2024-04-21T12:52:41Z

TLDR

← Предыдущая версия		Версия от 12:52, 21 апреля 2024
Строка 1:		Строка 1:
	== TLDR ==		== TLDR ==
	<youtube width="300" height="180">~~kaA3_qNfpCA~~</youtube>		<youtube width="300" height="180">c7ahlIwBL7o</youtube>
	<youtube width="300" height="180">8JQ565Rz7d8</youtube>		<youtube width="300" height="180">8JQ565Rz7d8</youtube>

Ctrlalt в 15:29, 24 мая 2023

2023-05-24T15:29:58Z

← Предыдущая версия		Версия от 15:29, 24 мая 2023
Строка 1:		Строка 1:
			== TLDR ==
			<youtube width="300" height="180">kaA3_qNfpCA</youtube>
			<youtube width="300" height="180">8JQ565Rz7d8</youtube>

			<youtube width="300" height="180">LVnPNWwd-yo</youtube>
			<youtube width="300" height="180">LnOOuNcRLIo</youtube>

			== Код ==

	Ищем расстояния во взвешенном графе от каждой вершины до всех остальных. Веса могут быть любыми.		Ищем расстояния во взвешенном графе от каждой вершины до всех остальных. Веса могут быть любыми.

Ctrlalt в 11:40, 28 июня 2022

2022-06-28T11:40:47Z

← Предыдущая версия		Версия от 11:40, 28 июня 2022
Строка 27:		Строка 27:
	if (dist[a][v] == INF \|\| dist[v][b] == INF)		if (dist[a][v] == INF \|\| dist[v][b] == INF)
	continue;		continue;
	dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b]);		dist[a][b] = min(dist[a][b], dist[a][v] + dist[v][b]);
	dist[a][b] = max(dist[a][b], -INF);		dist[a][b] = max(dist[a][b], -INF);
	}		}

Ctrlalt: /* Отрицательные циклы */

2022-04-07T02:01:16Z

Отрицательные циклы

← Предыдущая версия		Версия от 02:01, 7 апреля 2022
Строка 40:		Строка 40:
	== Отрицательные циклы ==		== Отрицательные циклы ==

	Вершина v лежит на отрицательном цикле, если после запуска Флойда dist[v][v] < 0.		Вершина v лежит на отрицательном цикле, если после запуска алгоритма Флойда dist[v][v] < 0. Наличие такой вершины — критерий отрицательного цикла в алгоритме Флойда.

	При наличии отрицательных циклов между некоторыми парами вершин может не существовать кратчайшего пути. Между вершинами a и b нет кратчайшего пути, если существует вершина v, лежащая на отрицательном цикле, ~~достижимая~~ из a и из которой достижима b.		При наличии отрицательных циклов между некоторыми парами вершин может не существовать кратчайшего пути. Между вершинами a и b нет кратчайшего пути, если существует вершина v, лежащая на отрицательном цикле, которая достижима из a и из которой достижима b.

	const int NO_SHORTEST_PATH = -2e9;		const int NO_SHORTEST_PATH = -2e9;

	for (int v = 0; v < vertexCount; v++)		for (int v = 0; v < vertexCount; v++)
	for (int a = 0; a < vertexCount; a++)		for (int a = 0; a < vertexCount; a++)

Ctrlalt в 01:59, 7 апреля 2022

2022-04-07T01:59:17Z

@@ Строка 38: / Строка 38: @@
 * При наличии отрицательных циклов расстояния могут очень быстро уменьшаться и приводить к отрицательным переполнениям. Поэтому нужно ограничивать отрицательные числа снизу.
-== Ссылки на задачи ==
+== Отрицательные циклы ==
 * [http://acmp.ru/?main=task&id_task=135 ACMP #135 &mdash; Алгоритм Флойда]
 * [http://acmp.ru/?main=task&id_task=136 ACMP #136 &mdash; Алгоритм Флойда - 2]
 * [http://acmp.ru/?main=task&id_task=137 ACMP #137 &mdash; Существование пути]
 * [http://acmp.ru/?main=task&id_task=562 ACMP #562 &mdash; Слабая K-связность]
 [[Category:Кратчайшие пути между всеми парами вершин]]

Ctrlalt в 03:07, 26 декабря 2021

2021-12-26T03:07:01Z

← Предыдущая версия		Версия от 03:07, 26 декабря 2021
Строка 8:		Строка 8:
	* Шаг 0. Теперь разрешаем путям проходить через вершину 0. Обновляем dist: dist[a][b] = min(dist[a][b], dist[a][0] + dist[0][b]);		* Шаг 0. Теперь разрешаем путям проходить через вершину 0. Обновляем dist: dist[a][b] = min(dist[a][b], dist[a][0] + dist[0][b]);
	* Шаг 1. Теперь разрешаем путям проходить через вершину 1. Обновляем dist: dist[a][b] = min(dist[a][b], dist[a][1] + dist[1][b]);		* Шаг 1. Теперь разрешаем путям проходить через вершину 1. Обновляем dist: dist[a][b] = min(dist[a][b], dist[a][1] + dist[1][b]);
	* Повторяем до шага n - 1.		* Повторяем до шага vertexCount - 1.

	~~vector<vector<int>> g(n, vector<int>(n));~~
	~~vector<vector<int>> dist(n, vector<int>(n));~~
	const int INF = 1e9;		const int INF = 1e9;
			vector<vector<int>> dist(vertexCount, vector<int>(vertexCount, INF));

	~~// считаем, что петель и кратных рёбер нет, граф задан матрицей смежности g, g[a][b] == 0 --- признак отсутствия ребра~~		for (int v = 0; v < vertexCount; v++)
	for (int a = 0; a < n; a++) {		dist[v][v] = 0;
	for (int b = 0; b < n; b++) {
	~~if (~~a == b)		for (int i = 0; i < edgeCount; i++) {
	~~dist[~~a][b~~] = 0~~;		int a, b, w;
	~~else~~		cin >> a >> b >> w;
	dist[a][b] = (g[a][b] ~~? g[a][b] : INF~~);		dist[a][b] = min(dist[a][b], w);
	}
	}		}

	for (int v = 0; v < n; v++) {		for (int v = 0; v < vertexCount; v++) {
	for (int a = 0; a < n; a++) {		for (int a = 0; a < vertexCount; a++) {
	for (int b = 0; b < n; b++) {		for (int b = 0; b < vertexCount; b++) {
	if (dist[a][v] == INF \|\| dist[v][b] == INF)		if (dist[a][v] == INF \|\| dist[v][b] == INF)
	continue;		continue;
	dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b]);		dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b]);
	dist[a][b] = ~~min~~(dist[a][b], -INF);		dist[a][b] = max(dist[a][b], -INF);
	}		}
	}		}

Ctrlalt в 16:44, 15 февраля 2020

2020-02-15T16:44:52Z

← Предыдущая версия		Версия от 16:44, 15 февраля 2020
Строка 1:		Строка 1:
	~~int g~~[~~V_CNT~~][~~V_CNT~~], dist[~~V_CNT~~][~~V_CNT~~], INF = 1 << 30;		Ищем расстояния во взвешенном графе от каждой вершины до всех остальных. Веса могут быть любыми.

			Идея алгоритма:
			* Инициализация. Пусть dist[a][b] — кратчайшее расстояние от a до b, но длиной не более чем одно ребро. Нетрудно понять, что dist — это просто матрица смежности графа (возможно, с небольшими модификациями):
			:* Случай простого графа: dist[a][a] = 0, dist[a][b] = весу ребра (a, b); если ребра (a, b) нет, то dist[a][b] = INF;
			:* Если есть кратные рёбра, то dist[a][b] = весу минимального ребра между a и b;
			:* Если есть петли, то dist[a][a] = min(0, вес минимальной петли из a);
			* Шаг 0. Теперь разрешаем путям проходить через вершину 0. Обновляем dist: dist[a][b] = min(dist[a][b], dist[a][0] + dist[0][b]);
			* Шаг 1. Теперь разрешаем путям проходить через вершину 1. Обновляем dist: dist[a][b] = min(dist[a][b], dist[a][1] + dist[1][b]);
			* Повторяем до шага n - 1.

			vector<vector<int>> g(n, vector<int>(n));
			vector<vector<int>> dist(n, vector<int>(n));
			const int INF = 1e9;

	for (int i = 0; i < ~~V_CNT~~; i++)		// считаем, что петель и кратных рёбер нет, граф задан матрицей смежности g, g[a][b] == 0 --- признак отсутствия ребра
	for (int j = 0; j < ~~V_CNT~~; j++)		for (int a = 0; a < n; a++) {
	dist[i][j] = (g[i][j] ? g[i][j] : INF);		for (int b = 0; b < n; b++) {
			if (a == b)
			dist[a][b] = 0;
			else
			dist[a][b] = (g[a][b] ? g[a][b] : INF);
			}
			}

	for (int k = 0; k < ~~V_CNT~~; k++)		for (int v = 0; v < n; v++) {
	for (int i = 0; i < ~~V_CNT~~; i++)		for (int a = 0; a < n; a++) {
	for (int j = 0; j < ~~V_CNT~~; j++)		for (int b = 0; b < n; b++) {
	if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]);		if (dist[a][v] == INF \|\| dist[v][b] == INF)
	dist[i][j] = ~~max~~(dist[~~i][k] + dist[k~~][j], -INF);		continue;
			dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b]);
			dist[a][b] = min(dist[a][b], -INF);
			}
			}
			}

			На что нужно обратить внимание:
			* При инициализации матрицы на главной диагонали должны быть нули (если нет петель отрицательного веса), а там, где рёбер нет — бесконечности;
			* При наличии отрицательных рёбер следует избегать присваиваний вида (INF - 1). Для этого, если хотя бы один из фрагментов пути равен INF, нужно делать continue;
			* При наличии отрицательных циклов расстояния могут очень быстро уменьшаться и приводить к отрицательным переполнениям. Поэтому нужно ограничивать отрицательные числа снизу.

	== Ссылки на задачи ==		== Ссылки на задачи ==
Строка 20:		Строка 49:
	* [http://e-maxx.ru/algo/floyd_warshall_algorithm e-maxx.ru — Алгоритм Флойда-Уоршелла]		* [http://e-maxx.ru/algo/floyd_warshall_algorithm e-maxx.ru — Алгоритм Флойда-Уоршелла]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BB%D0%BE%D0%B9%D0%B4%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Флойда]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BB%D0%BE%D0%B9%D0%B4%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Флойда]
	* [http://brestprog.~~neocities.org~~/~~lections~~/floyd~~.html~~ brestprog~~.neocities.org —~~ Алгоритм Флойда-Уоршелла]		* [http://brestprog.by/topics/floyd/ brestprog — Алгоритм Флойда-Уоршелла]
	* [http://algorithmica.org/tg/shortest-paths algorithmica.org — Кратчайшие пути в графе]		* [http://algorithmica.org/tg/shortest-paths algorithmica.org — Кратчайшие пути в графе]
	* [http://brilliant.org/wiki/floyd-warshall-algorithm Brilliant.org — Floyd-Warshall Algorithm]		* [http://brilliant.org/wiki/floyd-warshall-algorithm Brilliant.org — Floyd-Warshall Algorithm]

Ctrlalt: /* Ссылки */

2020-01-02T18:41:54Z

Ссылки

← Предыдущая версия		Версия от 18:41, 2 января 2020
Строка 22:		Строка 22:
	* [http://brestprog.neocities.org/lections/floyd.html brestprog.neocities.org — Алгоритм Флойда-Уоршелла]		* [http://brestprog.neocities.org/lections/floyd.html brestprog.neocities.org — Алгоритм Флойда-Уоршелла]
	* [http://algorithmica.org/tg/shortest-paths algorithmica.org — Кратчайшие пути в графе]		* [http://algorithmica.org/tg/shortest-paths algorithmica.org — Кратчайшие пути в графе]
			* [http://brilliant.org/wiki/floyd-warshall-algorithm Brilliant.org — Floyd-Warshall Algorithm]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 5]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 5]
	* [http://github.com/indy256/codelibrary/blob/master/java/src/FloydWarshall.java CodeLibrary — Floyd–Warshall algorithm]		* [http://github.com/indy256/codelibrary/blob/master/java/src/FloydWarshall.java CodeLibrary — Floyd–Warshall algorithm]

Ctrlalt: /* Ссылки */

2019-08-30T13:50:27Z

Ссылки

← Предыдущая версия		Версия от 13:50, 30 августа 2019
Строка 21:		Строка 21:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BB%D0%BE%D0%B9%D0%B4%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Флойда]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%BB%D0%BE%D0%B9%D0%B4%D0%B0 neerc.ifmo.ru/wiki — Алгоритм Флойда]
	* [http://brestprog.neocities.org/lections/floyd.html brestprog.neocities.org — Алгоритм Флойда-Уоршелла]		* [http://brestprog.neocities.org/lections/floyd.html brestprog.neocities.org — Алгоритм Флойда-Уоршелла]
			* [http://algorithmica.org/tg/shortest-paths algorithmica.org — Кратчайшие пути в графе]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 5]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 5]
	* [http://github.com/indy256/codelibrary/blob/master/java/src/FloydWarshall.java CodeLibrary — Floyd–Warshall algorithm]		* [http://github.com/indy256/codelibrary/blob/master/java/src/FloydWarshall.java CodeLibrary — Floyd–Warshall algorithm]