Длина - кратчайший путь
Cтраница 2
Расстояние между двумя вершинами - это длина кратчайшего пути, соединяющего эти вершины. [16]
Можно показать, что для определения длины кратчайших путей между всеми парами узлов сети достаточно только дважды умножить исходную матрицу длин саму на себя, с подстановкой в эту матрицу вычисляемых элементов. При этом первый раз элемен - Ш произведения матриц вычисляют, как обычно, по строкам сверху низ, а инутри стфок - слева направо, а второй раз в обратном порядке - по строкам снизу вверх, а внутри строк - справа налево. [17]
Финальная ( предельная) матрица дает длину кратчайшего пути между любыми двумя точками. Ведя учет изменений, вносимых для получения конечной формы, можно сохранить достаточно информации для того, чтобы проследить кратчайший путь между любыми двумя вершинами. [18]
CLOSED), то ее метка равна длине кратчайшего пути от источника. Аналогично, справедлива следующая лемма. [19]
В алгоритме Дейкстры выделяются две части: отыскание длины кратчайшего пути методом расстановки меток и отыскание собственно кратчайшего пути 66-ратным ходом. Для удобства изложения будем считать, что ищется путь из входа орграфа ха в вершину хп. [20]
Допустим, что на некотором этапе постоянные пометки дают длины кратчайших путей. [21]
 |
Кратчайшие маршруты в узел 1. [22] |
Доказательство того, что конечное значение ys действительно определяет длину кратчайшего пути из узла s в узел г. следует немедленно. По построению все двойственные ограничения ( 2) удовлетворяются. [23]
Используя этот метод, мы можем определить не только длину кратчайшего пути, но и его траекторию, которая не содержит петель. Метод основан на сравнительно простом алгоритме. [24]
Можно показать [1], что величина ф / равна длине кратчайшего пути, соединяющего узлы 0 и / и состоящего ровно из q дуг. При этом значение р, при котором достигается минимум в последнем выражении, определяет узел, в котором начинается последняя дуга соответствющего кратчайшего пути. [25]
Еслир г, то I ( р) является длиной кратчайшего пути. [26]
Если p t, то I ( р) является длиной кратчайшего пути. [27]
Если все вершины отмечены как постоянные, то эти пометки дают длины кратчайших путей. [28]
Аналогичное рассуждение позволит показать, что окончательные метки, присваиваемые вершинам, равны длинам кратчайших путей в них. [29]
Функция d, определяемая по правилу: d ( p, q) равна длине кратчайшего пути, соединяющего вершины р и q, является метрикой в связном графе; диаметр графа есть наибольшее значение, принимаемое этой функцией. Обхват графа есть длина кратчайшего цикла без повторяющихся ребер, при условии, что такой цикл существует. [30]
Страницы: 1 2 3 4