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

Ctrlalt в 15:26, 24 мая 2023

2023-05-24T15:26:03Z

← Предыдущая версия		Версия от 15:26, 24 мая 2023
Строка 1:		Строка 1:
			== TLDR ==
			<youtube width="300" height="180">fA_xvuqzuGs</youtube>
			<youtube width="300" height="180">J-7MzbEtTR0</youtube>

	== Общие сведения ==		== Общие сведения ==
	Дан ориентированный или неориентированный взвешенный граф; веса всех рёбер неотрицательны. Требуется определить кратчайшие расстояния из данной вершины до всех остальных.		Дан ориентированный или неориентированный взвешенный граф; веса всех рёбер неотрицательны. Требуется определить кратчайшие расстояния из данной вершины до всех остальных.

Ctrlalt в 23:22, 1 августа 2022

2022-08-01T23:22:49Z

← Предыдущая версия		Версия от 23:22, 1 августа 2022
Строка 20:		Строка 20:

	struct Edge {		struct Edge {
	int ~~from~~, ~~to;~~		int to, weight;
	~~int~~ weight;
	};		};

Строка 47:		Строка 46:
	visited[nearestV] = true;		visited[nearestV] = true;

	for (auto &[~~from,~~ to, weight] : graph[nearestV])		for (auto &[to, weight] : graph[nearestV])
	if (dist[to] > dist[nearestV] + weight)		if (dist[to] > dist[nearestV] + weight)
	dist[to] = dist[nearestV] + weight;		dist[to] = dist[nearestV] + weight;
Строка 77:		Строка 76:
	unvisited.erase(unvisited.begin());		unvisited.erase(unvisited.begin());

	for (auto &[~~from,~~ to, weight] : graph[nearestV]) {		for (auto &[to, weight] : graph[nearestV]) {
	if (dist[to] > dist[nearestV] + weight) {		if (dist[to] > dist[nearestV] + weight) {
	unvisited.erase({ dist[to], to });		unvisited.erase({ dist[to], to });

Ctrlalt в 18:39, 23 мая 2022

2022-05-23T18:39:32Z

← Предыдущая версия		Версия от 18:39, 23 мая 2022
Строка 114:		Строка 114:

	Если в графе присутствуют кратные рёбра между одной и той же парой вершин, то логику определения кратчайшего пути придётся усложнить. В данных условиях можно явно сохранить все рёбра графа в отдельном массиве, а в массив <tt>parent</tt> записывать индекс того ребра, по которому осуществлялась релаксация. При этом можно изменить представление графа: вместо хранения списка смежных рёбер для каждой вершины (<tt>vector<vector<Edge>> graph</tt>) можно хранить список индексов этих рёбер в массиве рёбер (<tt>vector<vector<int>> graph</tt>).		Если в графе присутствуют кратные рёбра между одной и той же парой вершин, то логику определения кратчайшего пути придётся усложнить. В данных условиях можно явно сохранить все рёбра графа в отдельном массиве, а в массив <tt>parent</tt> записывать индекс того ребра, по которому осуществлялась релаксация. При этом можно изменить представление графа: вместо хранения списка смежных рёбер для каждой вершины (<tt>vector<vector<Edge>> graph</tt>) можно хранить список индексов этих рёбер в массиве рёбер (<tt>vector<vector<int>> graph</tt>).

	~~== Ссылки на задачи ==~~

	* [http://acmp.ru/?main=task&id_task=132 ACMP #132 — Алгоритм Дейкстры]
	* [http://acmp.ru/?main=task&id_task=133 ACMP #133 — Заправки]
	* [http://acmp.ru/?main=task&id_task=134 ACMP #134 — Автобусы]
	* [http://acmp.ru/?main=task&id_task=260 ACMP #260 — Олимпиада по алхимии]
	* [http://acmp.ru/?main=task&id_task=469 ACMP #469 — Химическая тревога]
	* [http://codeforces.ru/gym/100070/problem/L Codeforces #100070.L — Островные государства]

	== Ссылки ==		== Ссылки ==
	* [http://e-maxx.ru/algo/dijkstra ~~e-maxx.ru —~~ Алгоритм Дейкстры за O(N<sup>2</sup> + M)]		Теория:
	* [http://e-maxx.ru/algo/dijkstra_sparse ~~e-maxx.ru —~~ Алгоритм Дейкстры за O(MlogN)]		* e-maxx.ru — [http://e-maxx.ru/algo/dijkstra Алгоритм Дейкстры за O(N<sup>2</sup> + M)], [http://e-maxx.ru/algo/dijkstra_sparse Алгоритм Дейкстры за O(MlogN)]
	* [~~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%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B neerc.ifmo.ru/wiki ~~—~~ Алгоритм Дейкстры]		* cp-algorithms.com — [https://cp-algorithms.com/graph/dijkstra.html Dijkstra Algorithm], [https://cp-algorithms.com/graph/dijkstra_sparse.html Dijkstra Algorithm for sparse graphs]
	* [~~http~~://brestprog.by/topics/dijkstra/ brestprog — Взвешенные графы. Алгоритм Дейкстры]		* [https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B neerc.ifmo.ru/wiki — Алгоритм Дейкстры]
	* [http://algorithmica.org/tg/shortest-paths ~~algorithmica.org —~~ Кратчайшие пути в графе]		* [https://brestprog.by/topics/dijkstra/ brestprog.by — Взвешенные графы. Алгоритм Дейкстры]
	* [~~http~~://~~informatics~~.~~mccme~~.ru/~~course~~/~~view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 4~~]		* algorithmica.org — [http://algorithmica.org/tg/shortest-paths Кратчайшие пути в графе], [https://ru.algorithmica.org/cs/shortest-paths/dijkstra/ Алгоритм Дейкстры]
	* [~~http~~://algs4.cs.princeton.edu/lectures/44ShortestPaths.pdf algs4.cs.princeton.edu/lectures ~~—~~ 4.4 Shortest Paths]		* [https://algs4.cs.princeton.edu/lectures/keynote/44ShortestPaths.pdf algs4.cs.princeton.edu/lectures — 4.4 Shortest Paths]
	* [~~http~~://brilliant.org/wiki/dijkstras-short-path-finder ~~Brilliant~~.org — Dijkstra's Shortest Path Algorithm]		* [https://brilliant.org/wiki/dijkstras-short-path-finder brilliant.org — Dijkstra's Shortest Path Algorithm]
	* [~~http~~://visualgo.net/sssp.~~html VisuAlgo —~~ Single-Source Shortest Paths]		* [https://usaco.guide/gold/shortest-paths?lang=cpp#dijkstra usaco.guide — Dijkstra]
	* [~~http~~://github.com/indy256/codelibrary/blob/master/~~java~~/~~src~~/~~Dijkstra~~.~~java CodeLibrary — Dijkstra's algorithm in O(V^2)~~]		Демонстрация:
	* [~~http~~://github.com/~~indy256~~/~~codelibrary~~/blob/master/java/~~src~~/~~DijkstraHeap~~.java ~~CodeLibrary~~ &~~mdash; Dijkstra's algorithm in O(ElogV)~~]		* [https://visualgo.net/en/sssp visualgo.net — Single-Source Shortest Paths]
	* [http://~~github~~.~~com~~/~~ADJA~~/~~algos~~/~~blob~~/~~master~~/~~Graphs~~/~~DijkstraSet~~.~~cpp Algos~~ &~~mdash; Dijkstra on set for sparse graphs~~]		* [https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html www.cs.usfca.edu/~galles — Dijkstra Shortest Path]
			Код:
			* [https://github.com/indy256/codelibrary/blob/master/cpp/graphs/shortestpaths/dijkstra.cpp indy256/codelibrary/cpp/graphs/shortestpaths/dijkstra.cpp]
			* [https://github.com/ADJA/algos/blob/master/Graphs/DijkstraSet.cpp ADJA/algos/Graphs/DijkstraSet.cpp]
			* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/DijkstraSP.java kevin-wayne/algs4/DijkstraSP.java]
			Задачи:
			* [https://informatics.msk.ru/course/view.php?id=6#section-4 informatics.msk.ru — Курс «Алгоритмы на графах», тема «Алгоритм Дейкстры»]
			* [http://acmp.ru/?main=task&id_task=132 ACMP #132 — Алгоритм Дейкстры]
			* [http://acmp.ru/?main=task&id_task=133 ACMP #133 — Заправки]
			* [http://acmp.ru/?main=task&id_task=134 ACMP #134 — Автобусы]
			* [http://acmp.ru/?main=task&id_task=260 ACMP #260 — Олимпиада по алхимии]
			* [http://acmp.ru/?main=task&id_task=469 ACMP #469 — Химическая тревога]
			* [http://codeforces.ru/gym/100070/problem/L Codeforces #100070.L — Островные государства]

	[[Category:Кратчайшие пути из одной вершины]]		[[Category:Кратчайшие пути из одной вершины]]

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

2021-12-26T03:32:12Z

← Предыдущая версия		Версия от 03:32, 26 декабря 2021
Строка 34:		Строка 34:
	const int INF = 1e9;		const int INF = 1e9;

	~~void~~ dijkstra(vector<vector<Edge>> &graph, int start) {		vector<int> dijkstra(vector<vector<Edge>> &graph, int start) {
	vector<bool> visited(graph.size());		vector<bool> visited(graph.size());
	vector<int> dist(graph.size(), INF);		vector<int> dist(graph.size(), INF);
Строка 51:		Строка 51:
	dist[to] = dist[nearestV] + weight;		dist[to] = dist[nearestV] + weight;
	}		}

			return dist;
	}		}

Строка 65:		Строка 67:
	const int INF = 1e9;		const int INF = 1e9;

	~~void~~ dijkstra(vector<vector<Edge>> &graph, int start) {		vector<int> dijkstra(vector<vector<Edge>> &graph, int start) {
	vector<int> dist(graph.size(), INF);		vector<int> dist(graph.size(), INF);
	set<pair<int, int>> unvisited;		set<pair<int, int>> unvisited;
Строка 83:		Строка 85:
	}		}
	}		}

			return dist;
	}		}

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

2021-12-26T03:27:37Z

Внесённые изменения

Ctrlalt в 17:12, 15 февраля 2020

2020-02-15T17:12:40Z

Внесённые изменения

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

2020-01-02T18:38:53Z

Ссылки

← Предыдущая версия		Версия от 18:38, 2 января 2020
Строка 149:		Строка 149:
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 4]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 4]
	* [http://algs4.cs.princeton.edu/lectures/44ShortestPaths.pdf algs4.cs.princeton.edu/lectures — 4.4 Shortest Paths]		* [http://algs4.cs.princeton.edu/lectures/44ShortestPaths.pdf algs4.cs.princeton.edu/lectures — 4.4 Shortest Paths]
			* [http://brilliant.org/wiki/dijkstras-short-path-finder Brilliant.org — Dijkstra's Shortest Path Algorithm]
	* [http://visualgo.net/sssp.html VisuAlgo — Single-Source Shortest Paths]		* [http://visualgo.net/sssp.html VisuAlgo — Single-Source Shortest Paths]
	* [http://github.com/indy256/codelibrary/blob/master/java/src/Dijkstra.java CodeLibrary — Dijkstra's algorithm in O(V^2)]		* [http://github.com/indy256/codelibrary/blob/master/java/src/Dijkstra.java CodeLibrary — Dijkstra's algorithm in O(V^2)]

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

2019-08-30T13:50:04Z

Ссылки

← Предыдущая версия		Версия от 13:50, 30 августа 2019
Строка 146:		Строка 146:
	* [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%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B 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%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B neerc.ifmo.ru/wiki — Алгоритм Дейкстры]
	* [http://brestprog.neocities.org/lections/dijkstra.html brestprog.neocities.org — Взвешенные графы. Алгоритм Дейкстры]		* [http://brestprog.neocities.org/lections/dijkstra.html brestprog.neocities.org — Взвешенные графы. Алгоритм Дейкстры]
			* [http://algorithmica.org/tg/shortest-paths algorithmica.org — Кратчайшие пути в графе]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 4]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 4]
	* [http://algs4.cs.princeton.edu/lectures/44ShortestPaths.pdf algs4.cs.princeton.edu/lectures — 4.4 Shortest Paths]		* [http://algs4.cs.princeton.edu/lectures/44ShortestPaths.pdf algs4.cs.princeton.edu/lectures — 4.4 Shortest Paths]

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

2016-01-27T20:10:14Z

Ссылки

← Предыдущая версия		Версия от 20:10, 27 января 2016
Строка 145:		Строка 145:
	* [http://e-maxx.ru/algo/dijkstra_sparse e-maxx.ru — Алгоритм Дейкстры за O(MlogN)]		* [http://e-maxx.ru/algo/dijkstra_sparse e-maxx.ru — Алгоритм Дейкстры за O(MlogN)]
	* [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%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B 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%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B neerc.ifmo.ru/wiki — Алгоритм Дейкстры]
			* [http://brestprog.neocities.org/lections/dijkstra.html brestprog.neocities.org — Взвешенные графы. Алгоритм Дейкстры]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 4]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 4]
	* [http://algs4.cs.princeton.edu/lectures/44ShortestPaths.pdf algs4.cs.princeton.edu/lectures — 4.4 Shortest Paths]		* [http://algs4.cs.princeton.edu/lectures/44ShortestPaths.pdf algs4.cs.princeton.edu/lectures — 4.4 Shortest Paths]

Ctrlalt: /* Ссылки на задачи */

2014-10-26T00:45:55Z

Ссылки на задачи

← Предыдущая версия		Версия от 00:45, 26 октября 2014
Строка 139:		Строка 139:
	* [http://acmp.ru/?main=task&id_task=260 ACMP #260 — Олимпиада по алхимии]		* [http://acmp.ru/?main=task&id_task=260 ACMP #260 — Олимпиада по алхимии]
	* [http://acmp.ru/?main=task&id_task=469 ACMP #469 — Химическая тревога]		* [http://acmp.ru/?main=task&id_task=469 ACMP #469 — Химическая тревога]
			* [http://codeforces.ru/gym/100070/problem/L Codeforces #100070.L — Островные государства]

	== Ссылки ==		== Ссылки ==