Устройство для определения кратчайшихпуТЕй HA гРАфЕ Советский патент 1981 года по МПК G06F15/173 

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШИХ

1

Изобретение относится к вычислительной технике, в частности к электронным модулирующим устройствам, и может быть применено при расчетгис . транспортной сети, сетевых графиков, тестов контроля релейных структур электрических сетей и т.п.

Известно устройство для моделирования кратчайших путей на графе, содержащее блок автоматического формирования топологии, блок управления , генератор, модели ветвей fll.

Наиболее близким К предлагаемому является устройство для анализа маршрутов в сети связи, содержащее генератор, выходной регистр, группу элементов И, два элемента И, регистр, блок сравнения, узел опроса, триггер 12.

Недостатком известных устройств является большой объем оборудования.

Цель изобретения - сокращение оборудования.

Указанная цель достигается тем, что устройство для определения кратчайших путей на графе, содержащее генератор импульсов, первьй вход которого подключен к выходу блока сравнения, первый и второй входы которого соединены соответственно с ПУТЕЙ НА ГРАФЕ

выходами первого и второго регистров, блок регистров и триггер, включает блок памяти, счетчики, два регистра промежуточного результата, блок индикации, третий и четвертый регистры и два сумматора, выход первого из которых соединен с первым входом второго сумматора первый выход которого связан с первыми входгили

10 третьего регистра и триггера, выход триггера подключен ко второму входу генератора импульсов выход которого соединен со входом первого счетчика, первый выход которого подключен

15 ко входу второго счетчика, выход которого соединен с третьим входом блока сравнения и с первым входом блока памяти, первый выходкоторого через третий счетчик подключен к

20 первому входу блока регистров, выход которого связан с первым входом первого сумматора, второй вход которого подключен к первому выходу четвертого регистра и ко второму вхо25ду второго сумматора-, Ьторой выход которого соединен- с первым входом четвертого регистра, второй выход . которого подключен к первому входу блока индикации, второй вход которо30го соединен.с выходом третьего регистра, первый выход четвертого счетчика подключен ко вторым входам третьего и четвертого регистров, блока памяти,а также ко входу второг регистра, второй выход блока памяти соединен с первым входом первого регистра промежуточного результата, первый выход которого через пятый счетчик связан со входом первого , регистра, второй выход первого ре-гистра промежуточного результата через второй регистр промежуточного . результата подключен ко входу четвертого счетчика, второй выход которого соединен с вторыми входами первого регистра промежуточного результата и триггера, второй выход первого счетчика связан с четвертым входом блока сравнения и третьим входом блока памяти, четвертый вход которого является входом устройства и соединен со вторым входом блока регистров, третий вход которого подключен к выходу блока сравнения .

На чертеже показана функциональная схема предлагаемого устройства.

Устройство содержит блок 1 памяти блок 2 регистров, третий счетчик 3, первый регистр 4 промежуточного результата, первый счетчик 5, блок б сравнения, второй счетчик 7, генератор 8 импульсов, первый регистр 9, второй регистр 10, пятый счетчик 11, четвертый регистр 12, третий регистр 13, четвертый счетчик 14, второй регистр 15 промежуточного результата, триггер 16, первый сумматор 17, второй сумматор 18, блок 19 индикации.

Перед началом работы формируется блок памяти в зависимости от исследуемого графа следующим образом.

В блок памяти 1 заносятся единицы только в те ячейки, которые соответствуют вершинам графа, а в блок регистров 2 - значения соответствующих дуг этого графа. Во второй регистр 15 заносят единицу в разряд, соответствующий номеру вершины графа, в которую требуется определить кратчайшие пути. Затем производят копирование содержимого строки блока 1 памяти,соответствующей номеру вершины графа,в которую требуется определить кратчайшие пути, на первый регистр 4. В регистре 12 в ячейку соответствующего вершине графа, в которую требуется определить кратчайшие пути, заносим ноль, в остальные ячей|{и заносят признаки бесконечно большого числа, например единицу в нулевом разряде. В регистре 13 заносят во все ячейки нули. Начинают сдвиг содержимого первого регистра промежуточного результата 4 влево до получения первой единицы. После этог содержимое счетчика регистра 4 копируется на регистр 9. Сдвигаем влево содержимое регистра 15 до получения.

первой единицы,после чего содержимое счетчика 14 копирует на регистр 10. Затем включается генератор импулЪсов 8,импульсы с которого поступают на счетчик 5. После каждого переполнения счетчика 5 добавляется едини,ца к содержимому счетчика 7. Так продолжается до момента сравнения . содержимого счетчиков 5 и 7 и регистров 9 и 10. При этом производится просмотр блока 1 памяти.После сравнения сигналов с блока 6 сравнения производится остановка генератора импульсов 8 и Ьыбор соответствующего регистра блока 2 регистров . Содержимое этого регистра поступает на сумматор 17, на второй вход которого поступает содержимое ячейки регистра 12, соответствующей содержимому счетчика 14. Это же содержимое поступает на второй вход счетчика 14, а также на второй сумматор 18, куда поступает результат сумматора 17. Если результат сумматора будет больше или равен содержимому соответствующей ячейки регистр 12, то никаких сигналов на вьоходе нет и никаких действий не производится. Если результат сумматора 17 меньше содержимого соответствующей ячейки регистра 12, то он через сумматор 18 заносится на место содержимого в эту ячейку в .регистре 12 и сигналом сумматора 18 производится занесение содержимого счетчика 14 в соответствующую ячейку регистра 13. Затем производится сдвиг влево содержимого регистра 4 до получения на выходе следующей единицы и производятся действия, описанные выше.

После полного просмотра регистра 4 производится сдвиг влево содержимого регистра 15 до получения на выходе следующей единицы. Далее устройство работает аналогично описанному.

Такая работа устройства продолжается до тех пор, пока не будет просмотрен регистр 15. После этого производится копирование содержимого регистра 4 на регистр 15.

Затем содержимое первого регистра 4 устанавливают равным нулю и производят сдвиг влево содержимого регистра 15 до появления первой ех иницы. После получения первой единицы производится копирование строки блока 1 памяти, соответствующей содержимому счетчика регистра 15. После полчения следующих единиц производится копирование соответствующих строк блока 1 памяти на регистр 4 без уничтожения уже имеющейся информации. После просмотра всего регистра 15 заново начинается работа устройства. Критерием останова является ситуация когда во время очередного цикла не меняется ни одна из ячеек регистра 13, т.е. триггер 16 остается в нуле чем блокирует дальнейшую работу устройства. Синхронизация отдельных блоков устройства осуществляется с помощью блока.управления (не показан). Благодаря введенным блокам и связям между блохами сократился объ оборудования. Формула изобретения Устройство для определения кратчайших путей на графе, содержащее генератор импульсов, первый вход которого подключен к выходу блока сравнения, первый и второй входы которого соединены соответственно с выходс1ми первого и второго регистров, блок регистров и триггер, отличающееся тем, что, с целью сокращения оборудования, оно содержит блок памяти, счетчики, два регистра промежуточного, результата, блок индикации, третий и четвертый регистры и два сумматора, выход первого из которых соединен с первым входом второго сумматора, первый выход которого соединен с первыми входами третьего регистра и триггера, выход триггера подключен ко второму входу генератора импульсов, выход которого соединен со входом первого счетчика, первый выход кОторого подключен ко входу второго счетчика, вькод которого соединен с третьим входом блока сравнения и с первым входом блока памяти,первый выход которого через третий счетчик подключен .к первому входу блока регистров, выход которого соединен с первым входом первого сумматора, второй вход которого подключен к первому выходу четвертого регистра и к второму входу второго сумматора, второй выход которого соединен с первым входом четвертого регистра, второй выход которого подключен к первому входу блока индикации, второй вход которого соединен с выходом третьего регистра, первый выход четвертого счетчика подключен ко вторым входам третьего и четвертого регистров, блока памяти, а также ко входу, второго регистра, второй выход блока памяти соединен с первым входом первого- регистра промежуточного результата, первый выход которого через пятый счетчик соединен со входом первого регистра, второй выход первого регистра промежуточного результата через второй регистр промежуточного результата подключен ко входу четвертого счетчика, второй выход которого соединен со вторыми входами первого регистра промежуточного результата и триггера, второй выход первого счетчика соединен с четвертым входом блока сравнения и третьим входом блока памяти, четвертый вход которого является входом устройства и соединен со вторым входом блока регистров, третий вход которого подключен к выходу блока сравнения. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 485451, кл. G Об F 15/20, 1971. 2.Авторское свидетельство СССР 547771, кл. G Об F 15/20, 1975 (прототип)