Маршрутизация на решетчато-клеточных структурах
Рябов Г.Г.

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

Рябов Г.Г. - Институт точной механики и вычислительной техники РАН им. С.А. Лебедева, Ленинский пр., 51, Москва; e-mail: ggr@ipmce.ru