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

Союз Советских Социалистических РеспубликОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВ ЯЛЬСТВУд-ву 51)М. Клз 50092/1 006 Г 15 есударственныя кемнтет СССР яе дедам нзебретеннй я еткрытнйата опубликова писания 30.07. оротников, В.В. Ре(54) устРОИСт длн ОпРеделения кРАтчАЙши тей нА ГРАФе выходами первого и второго регистров, блок регистров и триггер, включает блок памяти, счетчики, два регистра промежуточного результата, блок индикации, третий и четвертый регистры и два сумматора; выход первого из которых соединен с первым входом второго сумматора, первый выход которого связан с первыми входамн 0 третьего регистра и триггера, выходтриггера подключен ко второму входу генератора импульсов, выход которого соединен со входом первого счетчика, первый выход которого подключен 15 ко входу второго счетчика, выходкоторого соединен с третьим входом блока сравнения и с первым входом блока памяти, первый выходкоторого через третий счетчик .подключен к 20 первому входу блока регистров, выход которого связан с первым входом.первого сумматора, второй вход которого.подключен к первому выходу четвертого регистра и ко второму вхо З ду второго сумматора; второй выходкоторого соединен с первым входом четвертого регистра, второй выход .которого подключен к первому входу блока инднкации, второй вход которо" 30 го соединен.с выходом третьего ре(61) Дополнительное к авт. (22) Заявлено 26.10.79 (2 с присоединением заявки Йе Изобретение относится к вычисли- тельной технике, в частности к электронным модулирующим. устройствам, и может быть применено при расчетах транспортной сети, сетевых графиков, тестов контроля релейных структур электрических сетей и т.п.Известно устройство для моделирования кратчайших путей на графе, содержащее блок автоматического формирования топологии, блок управления, генератор, модели ветвей .11 .Наиболее близким к предлагаемому является устройство для анализа маршрутов в сети связи; содержащее генератор, выходной регистр, группу элементов И, два элемента И, регистр, блок сравнения, узел опроса, триггер 2.Недостатком известных устройств является большой объем оборудования.- Цель изобретения - сокращение оборудования.указанная цель достигается тем, что устройство для определения кратчайших путей на графе, содержащее генератор импульсов, первый вход которого подключен,к выходу. блока сравнения, первый и второй входы которого соединены соответственно. с Ц лвюиикрвгистра, первый выход четвертого счетчика подключен ко вторым входамтретьего и четвертого регистров,блока памяти,а такие ко входу второгорегистра, второй выход блока памятисоединен с первым входом первогорегистра промекуточного результата,первый выход которого через пятыйсчетчик связан со входом первогорегистра, второй выход первого регистра промежуточного результата через второй регистр промежуточного . 10результата подключен ко входу четвертого счетчика, второй выход которого соединен с вторыми входами первого регистра промежуточного результата и триггера, второй выход первого счетчика связан с четвертымвходом блока сравнения и третьимвходом блока памяти, четвертый входкоторого является входом устройстваи соединен со вторым входом блокарегистров, третий вход которого подключен к выходу блока сравнения,На чертехе показана функциональная схема предлагаемого устройства.Устройство содержит блок 1 памяти,блок 2 регистров, третий счетчик 3,первый регистр 4 промежуточного результата, первый счетчик 5, блок 6сравнения, второй счетчик 7, генератор 8 импульсов, первый регистр 9,второй регистр 10, пятый счетчик11, четвертый регистр 12, третийрегистр 13, четвертый счетчик 14,втсрой регистр 15 промежуточногорезультата, триггер 1 б, первый сум"матор 17, второй сумматор 18, блок 3519 индикации.Перед началом работы формируетсяблок памяти в зависимости от исследуемого графа следующим образом,В блок памяти 1 заносятся едини"цы только в те ячейки, которые соответствуют вершинам графа, а в блокрегистров 2 - значения соответствующих дуг этого графа. Во второй регистр 15 заносят единицу в разряд,соответствующий номеру вершины граФа, в которую требуется определитькратчайшие пути. Затем производяткопирование содержимого строки блока 1 памяти, соответствующей номерувершины графа,в которую требуется оп Оределить кратчайшие пути, на первыйрегистр 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 заново начинается работа устройства, Критерием останова является ситуация, когда во время очередного цикла не меняется ни одна из ячеек регистра13, т.е. триггер 16 остается в нуле, чем блокирует дальнейшую работу устройства. Синхронизация отдельных блоков устройства осуществляется с помощью блока. управления (не показан).Благодаря введенным блокам и 5 связям между блохами сократился объемоборудования.формула изобретенияУстройство для определения кратчайших путей на графе, содержащеегенератор импульсов, первый входкоторого подключен к выходу блокасравнения, первый и второй входы которого соединены соответственно свыходами первого и второго регистров, блок регистров и триггер,о т л и ч а ю щ е е с я тем, что,с целью сокращения оборудования, оносодержит блок памяти,.счетчики, дварегистра промежуточного результата,блок индикации, третий и четвертыйрегистры и два сумматора, выходпервого из которых соединен с первымвходом второго сумматора, первый выход которого соединен с первыми входами третьего регистра и триггера,выход триггера подключен ко второмувходу генератора импульсов, выход 30которого соединен со входом первогосчетчика, первый выход которого под.ключен ко входу второго. счетчика,выход которого соединен с третьимвходом блока сравнения и с первым 35входом блока памяти, первый выход ко"торого через третий счетчик подключен .к первому входу блока регистров, выход которого соединен с первымвходом первого сумматора, второй входкоторого подключен к первому выходучетвертого регистра и к второму входу второго сумматора, второй выходкоторого соединен с первым входомчетвертого регистра, второй выходкоторого подключен к первому входублока индикации, второй вход которогосоединен с выходом третьего регистра,первый выход четвертого счетчика подключен ко вторым входам третьегои четвертого регистров, блока памяти,а также ко входу, второго регистра,второй выход блока памяти соединенс первым входом первого регистра промежуточного результата, первый выходкоторого через пятый счетчик соединен со входом первого регистра, второй выход первого регистра промежуточного результата через второй регистр промежуточного результата подключен ко входу четвертого счетчика,второй выход которого соединен совторыми входами первого регистрапромежуточногО результата и триггера,второй выход первого счетчика соединен с четвертым входом блока сравнения и третьим входом блока памяти,четвертый вход которого являетсявходом. устройства и соединен совторым входом блока регистров, третийвход которого подключен к выходублока сравнения.Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 485451, кл. 6 Об Г 15/20, 1971.2. Авторское свидетельство СССРР 547771, кл. 6 Об Г 15/20, 1975СоставТехре Тираж 745 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 3035, Москва,й, Раушская наб., д. 4/5