Пусть из города S в город T необходимо доставить некоторый груз за кротчайшее время. Города S и T связаны между собой сетью дорог, проходящих через перевалочные пункты. Изобразим город S и T и перевалочные пункты в виде вершин некоторого графа. И каждую пару вершин i и j связываем дугой, если между ними существует прямая связь, т.е. возможна транспортировка из i в j, минуя другие пункты. Длиной дуги (i,j) l_ij назовем время транспортировки груза из i в j. Необходимо найти самый короткий путь, соединяющий вершины S и T в графе. Длина этого пути и будет равна кротчайшему времени транспортировки груза из S в T.