Первые шесть шагов вычисления кратчайшего пути от A к D. Стрелка указывает на рабочий узел

Первые шесть шагов вычисления кратчайшего пути от A к D. Стрелка указывает на рабочий узел

Известно несколько алгоритмов вычисления кратчайшего пути между двумя узлами графа. Один из них был создан знаменитым Дейкстрой (Dijkstra) в 1959 году. Он находит кратчайшие пути между отправителем и всеми возможными адресами назначения в данной сети. Каждый узел помечается (в скобках) расстоянием до него от узла отправителя по наилучшему известному пути. Эти расстояния должны быть неотрицательными; если они основаны на реальных величинах — таких как пропускная способность и время задержки, — это условие будет выполнено. Вначале пути неизвестны, поэтому все узлы помечаются символом бесконечности. По мере работы алгоритма и нахождения путей отметки узлов изменяются, показывая оптимальные пути. Отметка может быть постоянной или экспериментальной. Вначале все отметки являются ориентировочными. Когда выясняется, что отметка действительно соответствует кратчайшему возможному пути, она становится постоянной и в дальнейшем не изменяется.

Чтобы показать, как работает этот алгоритм, рассмотрим взвешенный ненаправленный граф на рис. 5.6, а, где весовые коэффициенты соответствуют, например, расстояниям. Мы хотим найти кратчайший путь от A к D. Для начала мы черным кружком помечаем узел A как постоянный. Затем мы исследуем все соседние с ним узлы, указывая около них расстояние до узла A. Если отыскивается более короткий путь к какому-либо узлу, то вместе с указанием расстояния в отметке меняется и узел, через который прошел более короткий путь. Таким образом, позднее можно восстановить весь путь. Если бы в сети было более одного кратчайшего пути от A до D и мы хотели бы найти их все, нам нужно было бы запоминать все узлы, которые позволяют дойти до данного узла, пройдя одинаковое расстояние.

Рассмотрев все соседние с A узлы, мы помечаем ближайший узел как постоянный, как показано на рис. 5.6, б. Этот узел становится новым рабочим узлом.