Задача о кратчайшем пути — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь.
Кратчайшая (простая) цепь часто называется геодезической.
Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для ее решения.
У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе.
Значимость данной задачи определяется ее различными практическими применениями. Например в GPS-навигаторах, где осуществляется поиск кратчайшего пути между двумя перекрестками. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Сумма расстояний всех дорог между перекрестками должна быть минимальной, тогда найден самый короткий путь.
Задачей моего реферата, является нахождение оптимального из возможных, алгоритма-нахождения кратчайшего пути в взвешенном графе.
Задача поиска кратчайшего пути на графе может быть определена для неориентированного, ориентированного или смешанного графа. Далее будет рассмотрена постановка задачи в самом простом виде для неориентированного графа. Для смешанного и ориентированного графа дополнительно должны учитываться направления ребер.
Граф представляет собой совокупность непустого множества вершин и ребер (наборов пар вершин). Две вершины на графе смежны, если они соединяются общим ребром. Путь в неориентированном графе представляет собой последовательность вершин, таких что смежна с для. Такой путь называется путем длиной из вершины в (указывает на номер вершины пути и не имеет никакого отношения к нумерации вершин на графе).
Пусть — ребро соединяющее две вершины: и. Дана весовая функция, которая отображает ребра на их веса, значения которых выражаются действительными числами, и неориентированный граф. Тогда кратчайшим путем из вершины в вершину будет называться путь (где и), который имеет минимальное значение суммы Если все ребра в графе имеют единичный вес, то задача сводится к определению наименьшего количества обходимых ребер.
