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

нйт .:,ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик(И) М. Кл, 006 15/2 осударствеииый иомит Совета Министров ССС по делам изооретеиийи открытий(43) Опубликовано 25 09 75 Бюллетень35 (45) Дата опубликования описания 3 О О 1 76 УДК681,326(088.8) 2) Авторы изобретения В, Васильев, А. Г, Додонов, Е, А,гин и В. В. Хаджино Н Украинской СС 1) Заявитель нститут электродинам(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАН КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ ных интервалов и со вторым входом блокауправления, а другой его выход подключенк третьему входу блока управления, входыформирователей временных интервалов каждой модели соединены с выходами задатчиков адресов узлов и триггера блокировки,а их выходы подключены к схемам индикации,триггеру блокировки и четвертому входублока управления, входы первой и второйсхем совпадения моделей ветвей подклю 10 ены соответственно к выходам перво и второго задатчиковтриггера блокировкиходы схем совпаденияления каждой модели ду блока авто опологии и к л ения. На чертеже представлена блок-схе устройства,Устройство содер блок 2 автоматическжит модель ветви 1,ого формирования топо огии, блок 3 управ ения, генератор 4 атель 5 времеппог 6 и 7 адресов уз топо- ременмпульс нтервал фор мировз адатч ика исоединением заявкиПредлагаемое устройство относится к вычислительной технике, Известны устройств для моделирования кратчайших путей на графе, содержащие блок автоматического формирования топологии, блок управления, к первому входу которого подключен выход генератора, модели ветвей, включающие два задатчика адресов узлов, формирователь временных интервалов схему индикации, две схемы совпадения, схему разделения и триггер блокировки, причем первый выход,блока управления соединен с блоком автоматического формирования топологии и задатчиков адресов узлов, второй выход подключен к схемам индикации моделей. ветвей, а третий выход - к формирователям временных интервалов моделей, Однако известные устройства имеют сравнительно малую надежность и пониженное быстродействие,11 ель изобретения - повышени быстродействия устройства.Это достигается тем, что в нем выход блока автоматического формирования логии соединен с формирователями в адресов и выходу этих моделей, а вычерез схему разде- подключены ко вхоатического формированияятому входу блока управ3триггер 8 блокировки, схема 9 и 10 совпадения, схему 11 разделения, схему 12индикации, разделитель 13 импульсов, схему 14 разделения, триггеры 15 и схемы 165совпадения.Устройство работает следующим образом,Предварительно в задатчики 6 и 7 адресов, в качестве которых будем рассматривать счетчики, заносят, соответствен 10но, адреса узлов, принадлежащих моделируемой ветви, В формирователи 5 временного интервала заносят длительности соответствующих ветвей. Триггеры 8 блокировкивсех моделей ветвей и триггеры 15 блока,автоматического формирования топологиипредварительно устанавливают в единочноесостояние. При этом на соответствующихвходах схем 9 и 10 совпадения будет присуствовать запрещающий сигнал с нулевого выхода триггера 8, а на соответствующих входах схем 16 совпадения блока 2автоматического формирования топологиисигналы с единичных выходов соответствующих триггеров 15,25Дпя запуска всех моделей ветвей, исходящих из начального узла, блок управления разрешает прохождение импульсов на входы всех задатчиков 6 и 7 адресов узлов всех моделей ветвей 1 и распределителя 13 импульсов блока 2 автоматического формирования топологии. При этом, в момент переполнения задатчиков 6 и 7 адресов, в одном из которых записан адрес начального узла, блок управления выдаст пусковой импульс на входы схемы 16 совпадения блока 2 автоматического формирования топологии, Пусковой сигнал пройдет через ту схему совпадения, на 40. втором входе которой будет, присутствовать сигнал разделителя 13 импульсов и через схему 14 разделения поступит на все модели ветвей 1 на соответствующие входы формирователей 5 временных интервалов.При совпадении в этот момент времени, с выходным. сигналом одного из задатчиков 6 или 7 адресов, в котором записан начальный узел, этот сигнал подготовит формирователя 5 временного интервала р моделей ветвей 1, исходящих из начального узла, к отсчету импульсов измерительной серии, Одновременно пусковой сигнал, прошедший через схему 16 совпадения блока автоматического формирования топологии, установит в нулевое состояние соответствующий триггер 15, При появлении на выходе блока 2 автоматического формирования топологии выходного сигнала. распределителя блок управления прекращает подачу импульсов и разрешает поступление импульсов измерительной серии на все модели ветвей 1, В момент окончания формирования временного интервала какой пибо модели ветви выходной сигнал соответствующегоформирователя 5 временного интервала уссановит,в нулевое состояние триггер 8блокировки и поступит на соответствующийвход блока управления. При этом блок управления прекращает подачу импульсов измерительной серии на модели ветвей 1, и вновь разрешает поступление импульсов на вход задатчиков адресов. Сигналы переполнения задатчиков адресов пройдут на выходы соответствующих схем 9 и 10, совпадения через схему 11 разделения, наблок 2 автоматического формирования топологии, т.к. на объединенных входах схем 9 и 10 совпадения имеется разрешающий сигнал с нулевого выхода тригге- ра 8, При этом сигнал с выхода задатчика адреса, в котором записан начальный узел, не прийдет через соответствующуюсхему 16 совпадения, т,к, соответствующий триггер 15 находится. в нулевом состоянии, а сигнал с выхода задатчика адреса, в котором записан конечный узел ветви, .поступит при совпадении с сигналом распределителя на выход схемы 14 разделения и черезполюса всех моделей ветвей 1 на входы формирователей 3 временного интерваЫа,На другие входы формирователей поступают выходные сигналы задатчиков адресови при совпадении с выходным сигналомблока автоматического формирования топологии будут подготовлены к отсчетуимпульсов измерительной серии те из них,в задатчиках адресов которых записан номер конечного узла рассматриваемойветви. При этом импульс выхода соответствующей схемы 16 совпадения блока 2 автоматического формирования топологии установит в нулевое состояние соответствукщий триггер.15, тем самым запрещая вторичное прохождение сигнала через эту схему совпадения, Выходной сигнал распределителя 13 с блока 2 автоматического формирования топологиизапретит вновь прохождение импульсовна вход задатчиков адресов и разрешитих поступление на модели ветвей,В момент появления сигнала на входеблока управления, свидетельствующего обокончании формирования временного интервала ветви, смежной с конечным углом, 485451устройство управления останавливает решение и выдает разрешение на моделиветвей на входы схем 12 индикации дляиндикации дерева кратчайших путей, Приэтом измерительное устройство зафиксирует величину кратчайшего пути,Предмет изобретения Устройство для моделирования краъчайших путей на графе, содержащее блок автоматического формирования топологии, блок управления, к первому входу кото- рого подключен выход генератора, модели ветвей, включающие два задатчика15 адресов узлов, формирователь временных интервалов, схему индикации, две схемы совпадения, схему разделения и триггер блокировки, причем первый выход блока управления соединен с блоком автоматичес 20 кого формирования топологии и задатчиков адресов узлов, второй выход подключен к схемам индикации моделей ветвей, а третий выход к формирователям временных интервалов моделей, о т л и ч а ю ш е е с я тем, что, с целью повышения надежности и быстродействия, выход блока автоматического формирования топологии соединен с формирователями временных интервалов и со вторым входом блока управления, а другой его выход подключен к третьему, входу блока управления, входы формирова гегелям временных интервалов моделей.,соединены с выходами задатчиков адресов узлов и триггера блокировки, а их выходы подключены к схемам индикации, триггеру блокировки и четвертому входу блокауправления, входы первой и второй схем совпадения моделей ветвей подключены соответственно к выходам первого и второго задатчиков адресов и выходу триггера блокировки этих моделей, а выходы схем совпадения через схему .разделения каждой модели подключены ко входу блока автоматического формирования топологии и к пятому входу блока управления.679 ка Подписное едпри ЗЗ ЦНИИПИсударственного комитета Совета Министровпо делам изобретений и открытийМосква, 113035, Раушская наб., 4 Патент, Москва, Г, Бережковская наб., 24