Алгоритмы определения кратчайших расстояний на графе. Интерес к задаче поиска кратчайших расстояний объясняется тем, что эта задача является одним из этапов в решении большинства задач, связанных с грузовыми перевозками. При этом в ходе решения задач, связанных с оптимизацией грузовых перевозок, приходится многократно определять кратчайшие расстояния между вершинами графа. Поэтому от быстродействия алгоритмов определения кратчайших расстояний между вершинами графа в большой степени зависит время решения всей задачи в целом.
Сформулируем задачу о кратчайшем пути. Пусть дан связанный граф, имеющий … вершин и Сориентированных дуг, причем каждой дуге поставлено в соответствие неотрицательное число … называемое ее длиной. Требуется найти на графе кратчайшие пути и их длины от заданной вершины … до всех остальных вершин этого графа. Под длиной кратчайшего пути при этом подразумевается сумма длин составляющих этот путь дуг. В каждую вершину графа может входить только одна дуга, принадлежащая какому-нибудь кратчайшему пути.