Аннотация:
Рассматривается расширение класса решетчатых графов с
включением в окрестность на решетке дополнительных ребер с весами,
равными соответствующим длинам векторов в евклидовом пространстве с
целью приближения к евклидовой метрике. Установлено соответствие
координат вершин, инцидентных дополнительным ребрам,
последовательностям несократимых дробей Фарея-Коши. Предложен
соответствующий алгоритм построения множества кратчайших путей на такой
взвешенной решетке, который по существу моделирует “волновой” процесс
построения поля всех кратчайших (от множества-источника) путей. Приведены
оценки и примеры при машинной реализации.