Устройство для определения кратчайшихпутей ha графе

 

Союз Советскик

Социалистических

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВ ТВЛЬСТВУ (61) Дополнительное к авт. свнд-ву (22) Заявлено 26.10.79 (2f) 2850092/18-24 Р М

G 06 F 15/20 с присоединением заявки Йо (23) Приоритет

Государственный комнтет

СССР по делам нзобретеянй я открытяй

Опубликовано 300781. бюллетень 8928

Дата опубликования описания 30. 07. 81 (53) УДК 681. 326 (088. 8) f

В.A ВоРотников, В.В. Реут и В.с. кРлиииикрв

М

) ::

j (72) Авторы изобретения

3 с (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШИХ

ПУТЕЙ HA ГРАФЕ

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

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

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

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

Указанная цель достигается тем, что устройство для определения крат- 25 чайших путей на графе, содержащее генератор импульсов, первый вход которого подключен .к выходу. блока сравнения, первый и второй входы которого соединены соответственно. с 30 выходами первого и второго регистров, блок регистров и триггер, включает блок памяти, счетчики, два регистра промежуточного результата, блок индикации, третий н четвертый регистры и два сумматора; выход первого из которых соединен с первым входом второго сумматора, первый выход которого связан с первыми входамн третьего регистра и триггера, выход триггера подключен ко второму входу генератора импульсов, выход которого соединен со входом первого счетчика, первый выход которого подключен ко входу второго счетчика, выход которого соединен с третьим входом блока сравнения.и с первым входом блока памяти, первый выход которого через третий счетчик подключен к первому входу блока регистров, выход которого связан с первым- входом. первого сумматора, второй вход которого подключен к первому выходу четвертого -регистра и ко второму входу второго сумматора; второй выход которого соединен. с первым входом четвертого регистра, второй выход . которого подключен к первому входу блока индИкации, второй вход которо" го соединен.с выходом третьего ре851411

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

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

Устройство содержит блок 1 памяти, блок 2 регистров, третий счетчик 3, первый регистр 4 промежуточного результата, первый счетчик 5, блок б сравнения, второй счетчик 7, генератор 8 импульсов, первый регистр 9, второй регистр 10, пятый счетчик

11, четвертый регистр 12, третий регистр 13, четвертый счетчик 14, втс рой регистр 15 промежуточного результата, триггер 1б, первый сумматор 17, второй сумматор 18, блок 35

19 индикации.

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

В блок памяти 1 заносятся единицы только в те ячейки, которые соответствуют вершинам графа, а в блок регистров 2 — значения соответствующих дуг этого графа. Во второй регистр 15 заносят единицу в разряд, соответствующий номеру вершины графа, в которую требуется определить кратчайшие пути. Затем производят копирование содержимого строки блока 1 памяти, соответствующей номеру вершины графа,в которую требуется on- o ределить кратчайшие пути, на первый регистр 4. В регистре 12 в ячейку соответствующего вершине графа, в которую требуется определить кратчай. шие пути, заносим ноль, в остальные 55 ячейки заносят признаки бесконечно большого числа, например единицу в нулевом разряде. В регистре 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 заново начинается работа устройства.

Критерием останова является ситуация, когда во время очередного цикла не меняется ни одна из ячеек регистра

851411

13, т.е. триггер 16 остается в нуле, чем блокирует дальнейшую работу устройства. Синхронизация отдельных блоков устройства осуществляется с помощью блока. управления (не показан).

Благодаря введенным блокам и связям между блохами сократился объем ! оборудования.

Формула изобретения

Устройство для определения кратчайших путей на графе, содержащее генератор импульсов, первый вход которого подключен к выходу блока сравнения, первый и второй входы которого соединены соответственно с выходами первого и второго регистров, блок регистров и триггер, о т л и ч а ю щ е е с я тем, что, с целью сокращения оборудования, оно содержит блок памяти,.счетчики, два регистра промежуточнога результата, блок индикации, третий и четвертый регистры и два сумматора, выход первого из которых соединен с первым входом второго сумматора, первый выход которого соединен с первыми входами третьего регистра и триггера, выход триггера подключен ко второму входу генератора импульсов, выход 30 которого соединен со входом первого счетчика, первый выход которого под .ключен ко входу второго. счетчика, выход которого соединен с третьим входом блока сравнения и с первым 35 входом блока памяти, первый выход которого через третий счетчик подключен .к первому входу блока регистров, выход которого соединен с первым входом первого сумматора, второй вход которого подключен к первому выходу четвертого регистра и к второму входу второго сумматора, второй выход которого соединен с первым входом четвертого регистра, второй выход которого подключен к первому входу блока индикации, второй вход которого соединен с выходом третьего регистра, первый выход четвертого счетчика подключен ко вторым входам третьего и четвертого регистров, блока памяти, а также ко входу, второго регистра, второй выход блока памяти соединен с первым входом первого- регистра промежуточного результата, первый выход которого через пятый счетчик соединен со входом первого регистра, второй выход первого регистра промежуточного результата через второй регистр промежуточного результата подключен ко входу четвертого счетчика, второй выход которого соединен со вторыми входами первого регистра промежуточногО результата и триггера, второй выход первого счетчика соединен с четвертым входом блока сравнения и третьим входом блока памяти, четвертый вход которого является входом. устройства и соединен со вторым входом блока регистров, третий вход которого подключен к выходу блока сравнения.

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

Р 485451, кл. G 06 F 15/20, 1971.

2. Авторское свидетельство СССР

Р 547771, кл. G 06 F 15/20, 1975 (прототип) 851411 тираж 745 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва,K-35, Раушская наб., д. 4/5 филиал ППП "Патент", г. Ужгород, ул. Проектная,4

Редактор Н. Безродная

Ю ЮЮЮ В ЮВЮВ ЮЮМю

9аказ 6366/69

Составитель И. Дубинина

Техред Н. Келушак Корректор В. Синицкая