задача о кратчайшем пути
Sign in to saveAlso known as single-pair shortest path problem
задача поиска кратчайшего пути во взвешенном графе между двумя вершинами
Wikidata facts
- Instance of
- computational problem
- Image
- Shortest path with direct weights.svg
Show 1 more fact
- maintained by WikiProject
- WikiProject Mathematics
Sources (3)
via Wikidata · CC0
Article · Русский
Зада́ча о кратча́йшем пути́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь. Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для её решения. У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе. Значимость данной задачи определяется её различными практическими применениями. Например, в GPS-навигаторах осуществляется поиск кратчайшего пути между точкой отправления и точкой назначения. В качестве вершин выступают перекрёстки, а дороги являются рёбрами, которые лежат между ними. Если сумма длин дорог между перекрёстками минимальна, тогда найденный путь самый короткий.
Abstract from DBpedia / Wikipedia · CC BY-SA