Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для ее решения. Она может быть определена как для ориентированного, так и для неориентированного графа.
Существуют различные постановки задачи о кратчайшем пути:
- · задача о кратчайшем пути в заданный пункт назначения. Требуется найти кратчайший путь в заданную вершину назначения, который начинается в каждой из вершин орграфа (кроме). Поменяв направление каждой принадлежащей орграфу дуге, эту задачу можно свести к задаче о единой исходной вершине (в которой осуществляется поиск кратчайшего пути из заданной вершины во все остальные);
- · задача о кратчайшем пути между заданной парой вершин в орграфе. Требуется найти кратчайший путь из заданной вершины в заданную вершину орграфа;
- · задача о кратчайшем пути между всеми парами вершин орграфа. Требуется найти кратчайший путь из каждой вершины в каждую вершину орграфа. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.
В различных постановках задачи, роль длины дуги могут играть не только сами длины, но и время, стоимость, расходы, объем затрачиваемых ресурсов (материальных, финансовых, топливно-энергетических и т. п.) или другие характеристики, связанные с прохождением каждой дуги. Таким образом, задача находит практическое применение в большом количестве областей (информатика, экономика, география и др.).
В связи с тем, что существует множество различных постановок данной задачи, есть наиболее популярные алгоритмы для решения задачи поиска кратчайшего пути на графе. [2].
