Cтраница 1
Алгоритм нахождения кратчайшего пути, Вычислительные системы, Новосибирск, 1963, вып. [1]
Алгоритм нахождения кратчайшего пути, приведенный в разд. [2]
Алгоритм нахождения кратчайшего пути, который применим к графу с ребрами произвольной длины, а также алгоритм построения стягивающего дерева с минимальной стоимостью ( который является усовершенствованием второго алгоритма из разд. [3]
Придумать алгоритм нахождения кратчайшего пути между двумя заданными вершинами такого графа, в котором каждому ребру поставлено в соответствие некоторое неотрицательное действительное число, обозначающее его длину. [4]
Алгоритм нахождения кратчайшего пути из одного источника. [5] |
Покажите, что алгоритм нахождения кратчайшего пути из разд. [6]
Стоимости ребер для графа с 5 узлами.| Матрица положительных целых чисел. [7] |
Докажите, что алгоритм нахождения кратчайшего пути, приведенный на рис. 5.38, строит кратчайший путь из и в каждый узел v произвольного графа, у которого могут быть ребра с отрицательными стоимостями, но циклов с отрицательными стоимостями нет. [8]
Рекуррентное соотношение ( 8) эквивалентно алгоритму нахождения кратчайшего пути на ориентированной ациклической сети. [9]
Подобный подход очень тесно связан с алгоритмом нахождения кратчайшего пути, описанным в разд. [10]
Существует нечто, о чем стоит упомянуть прежде, чем описывать алгоритм нахождения кратчайшего пути. Во многих задачах, связанных с графами, необходимо уточнить, в каком виде должен быть дан ответ. Ясно, что ответы на первый и второй вопросы мы хотим получить в виде чисел, но не очевидно, в какой форме следует представить все кратчайшие пути от X до У. Если кратчайших путей много, то наиболее компактным представлением их всех может быть сам граф, а не, скажем, перечисление вершины за вершиной для каждого пути. [11]
Задачи о кратчайшем пути, в которых на пути накладываются некоторые ограничения ( см. [4], [12], [23]), в настоящей главе не рассматриваются, так как к ним непосредственно не применимы те методы расстановки пометок, на которых базируются все описанные здесь алгоритмы нахождения кратчайшего пути. Эти задачи с ограничениями часто настолько сложны, что соответствующие алгоритмы позволяют находить оптимальные решения лишь таких задач, размеры которых ( например, число вершин) на несколько порядков меньше, чем у аналогичных задач без ограничений. [12]
Задачи о кратчайшем пути, в которых на пути накладываются некоторые ограничения ( см. [4], [12], [23]), в настоящей главе не рассматриваются, так как к ним непосредственно не применимы те методы расстановки пометок, на которых базируются все описанные здесь алгоритмы нахождения кратчайшего пути. Эти задачи с ограничениями часто настолько сложны, что соответствующие алгоритмы позволяют находить оптимальные решения лишь таких задач, размеры которых ( например, число вершин) на несколько порядков меньше, чем у аналогичных задач без ограничений. [13]
Таким образом, возникает следующий смешанный алгоритм. Выберем стационарную стратегию и вычислим результирующее пробное значение г. Применим алгоритм итераций по критерию ( о), приведенный в разд. Еслп при расчетах обнаруживается цикл, для которого соответствующая сумма ctj отрицательна, должным образом изменим стратегию, повторно вычислим с для этого улучшающего цикла, пересчитаем ctj и повторно выполним операции. Как только вычисления по алгоритму нахождения кратчайшего пути завершатся получением значений WL. [14]
Заданная система кабелеводов образует связывающую сеть, полюсами которой являются размещаемые объекты. В конкретной математической интерпретации возникает следующая задача. Для каждой пары полюсов - нужно найти длину кратчайшего пути между ними и один кратчайший путь, соединяющий эти полюсы. Решение задачи распадается на две последовательно работающие части. Вторая часть представляет собой алгоритм нахождения кратчайшего пути на связывающей сети с использованием данных матрицы кратчайших расстояний. Суть этого алгоритма заключается в следующем. [15]