Cтраница 4
Число pi / дает длину кратчайшего пути из xt в х /, образованного парой дуг. Вообще Da указывает длину кратчайшего пути от одной вершины до другой, составленного не менее чем а дугами. [46]
По дорожке, имеющей форму окружности, из двух диаметралью противоположных точек А и Б выбегают одновременно два спортсмена и бегут с постоянными скоростями навстречу друг другу. Найти скорости спортсменов, если под расстоянием понимается длина кратчайшего пути по дорожке. [47]
По дорожке, имеющей форму окружности, из двух диаметрально противоположных точек А и Б выбегают одновременно два спортсмена и бегут с постоянными скоростями навстречу друг другу. Найти скорости спортсменов, если под расстоянием понимается длина кратчайшего пути по дорожке. [48]
Лемма 6.4. Если точка, расположенная внутри ребра, оказывается окончательно помеченной, являясь при этом частью кандидата в интервал относительно пары ( e f), то ее метка равна длине кратчайшего f - свододного пути в нее. При присвоении окончательной метки вершине ее значение равно длине кратчайшего пути в вершину. [49]
Этот процесс продолжается до тех пор, пока не будет помечена начальная вершина. По окончании разметки индекс у начальной вершины будет равен длине кратчайшего пути. [50]
Таким образом, традиционная евклидова метрика совпадает с / - 2-метрикой. Помимо / - 2-расстояния особый интерес представляют Li-расстояние ( известное также под названием манхеттенское расстояние) - длина кратчайшего пути, каждый участок которого является отрезком, параллельным одной из осей координат, и Leo-расстояние, определяемое максимальной разностью координат. Эти метрики являются естественными для целого ряда приложений, таких как моделирование движений руки и проектирование топологии интегральных схем. [51]
В алгоритме Флойда нахождения кратчайшего пути между всеми парами вершин ( см. разд. Применение этой операции га-раз к матрице весов [ ctj ] дает заключительную матрицу, элементы которой равны длинам кратчайших путей. [52]
Если теперь мы будем сближать оба положения вдоль рассматриваемого геодезического пути, то длина этого пути и одновременно длина абсолютного кратчайшего пути будут стремиться к нулю, в то время как остальные геодезические пути остаются конечными. По крайней мере, начиная от некоторого конечного расстояния между положениями, геодезический путь, вдоль которого оба положения сближаются, должен совпасть с абсолютно кратчайшим из них. [53]