Длина - кратчайший путь
Cтраница 3
 |
Неразделимые графы.| Разделимые графы. [31] |
Отклонение d ( А, В) вершины А графа от его вершины В равно длине кратчайшего пути из вершины А в вершину В. [32]
 |
Продублировав все ребра ЕМ. ОД, получаем граф с эйлеровым циклом. [33] |
Используя минимальное остовное дерево, можно получить приближенное решение ЗК, дающее путь, длина которого меньше удвоенной длины кратчайшего пути. [34]
 |
Окончательные пометки вершин и а - база. [35] |
Вектор пометок Iй ( х совпадает с Iй ( х4), и, следовательно, этв пометки равны длинам кратчайших путей. [36]
 |
Окончательные пометки вершин и а - бааа. [37] |
Вектор пометок Z6 ( xt) совпадает с Z6 ( жг), и, следовательно, эта пометки равны длинам кратчайших путей. [38]
В работе приведен алгоритм сложности О ( n2 log / г), строящий такое разбиение поверхности произвольного многогранника, что длина кратчайшего пути из заданной начальной точки 5 ( источника) до произвольной точки t поверхности может быть определена с помощью локализации положения точки t в разбиении. Определение положения точки может быть осуществлено стандартными методами за время О ( log / г), после чего сам путь находится обратной трассировкой за время О ( К), где К - число граней, через которые он проходит. [39]
Общее правило для нахождения кратчайшего пути в графе состоит в том, чтобы каждой вершине xi приписать индекс А /, равный длине кратчайшего пути из данной вершины в конечную. [40]
Если А п - 1 и 1Ь 1 ( яг) I ( х для всех яг, то получен оптимальный ответ и пометки равны длинам кратчайших путей. [41]
Для нахождения кратчайшего пути от блока i до блока / каждой матрице С ставится в соответствие матрица D, элементами которой являются целые числа, определяющие длину кратчайшего пути между соответствующими блоками. [42]
Если k n - 1 и lk 1 ( xt) lh ( xt) для всех xt, то получен оптимальный ответ и пометки равны длинам кратчайших путей. [43]
При этом решается задача нахождения кратчайшего пути с одним источником ( а с помощью простого обобщения и задачи с несколькими источниками, см. [11]) путем построения такого разбиения поверхности, которое позволяет определить длину кратчайшего пути до любой концевой точки простой локализацией положения этой точки в построенном разбиении. Таким образом, длина кратчайшего пути может быть определена за время О ( log / г), а сам путь затем находится за время 0 ( & logn), где k - число ребер, которые он пересекает. [44]
При этом решается задача нахождения кратчайшего пути с одним источником ( а с помощью простого обобщения и задачи с несколькими источниками, см. [11]) путем построения такого разбиения поверхности, которое позволяет определить длину кратчайшего пути до любой концевой точки простой локализацией положения этой точки в построенном разбиении. Таким образом, длина кратчайшего пути может быть определена за время О ( log / г), а сам путь затем находится за время 0 ( & logn), где k - число ребер, которые он пересекает. [45]
Страницы: 1 2 3 4