Устройство для моделирования кратчайших путей на графе Советский патент 1975 года по МПК G06F15/173 

триггер 8 блокировки, схеМа 9 и 10 совпадения, схему 11 раздепения, схему 12 индикации, разделитель 13 импульсов, схе му 14 разделения, триггеры 15 и схемы совпадения. Устройство работает следующим образом. Предварительно в задатчики 6 и 7 адресов, в качестве которых будем рассматривать счетчики, заносят, соответственно, адреса узлов, принадлежащих моделируемой ветви, В формирователи 5 временн го интервала -заносят длительности соотве ствующих ветвей. Триггеры 8 блокировки всех моделей ветвей и триггеры 15 блока автоматического формирования топологии предварительно устанавливают в единочНое состояние При этом на соответствующих входах схем 9 и 10-совпадения будет при суствовать запрещающий сигнал с нулевого выхода триггера 8, а на соответствующих входах схем 16 совпадения блока 2 автоматического формирования топологии- сигналы с единичных выходов соответству ющих триггеров 15„ Дня запуска всех моделей ветвей, исходящих из начального узла, блок управления разрешает прохонщение импульсов на входы всех задатчиков 6 и 7 адресов узлов всех моделей ветвей 1 и распределителя 13 импульсов блока 2 автоматического формирования топологии. При это в момент переполнения задатчиков 6 и 7 адресов, в одном из которых записан адрес начального узла, блок управления вы- даст пусковой импульс на входы схемы 1 совпадения блока 2 автоматического формирования топологии. Пусковой сигнал пройдет через ту схему совпадения, на втором входе которой будет . присутствова сигнал разделителя 13 импульсов и через схему 14 разделения поступит на все модели ветвей 1 на соответствующие входы формирователей 5 временных интервалов. При совпадении в этот момент времени . с выходным сигналом одного из задатчиков 6 или 7 адресов, в котором записан начальный узел, этот сигнал подготовит формирователя 5 временного интервала моделей ветвей 1,, исходящих из начального узла, к отсчету импульсов измерительной серии. Одновременно пусковой сигнал, прощедший через схему 16 совпадения блока автоматического формирования топологии, установит в нулевое сос тояние соответствующий триггер 15. При появлении на выходе блока 2 автомати- ческого формирования топологии выходного сигнала распределителя блок управления прекращает подачу импульсов и разрешает поступление импульсов измерительной серии на все модели ветвей 1. В момент окончания формирования временного интервала какой-либо модели. ветви выходной сигнал соответствующего ; формирователя 5 временного интервала у& (гановит;/ в нулевое состояние триггер 8 ; блокировки и поступит на соответствующий вход блока управления. При этом блок управления прекращает подачу импульсов , измерительной серии на модели ветвей 1, и вновь разрещает поступление импульсов , на вход задатчиков адресов. Сигналы пе- реполнения задатчиков адресов пройдут на выходы соответствующих схем 9 и 10 совпадения через схему 1-1 разделения, на блок 2 автоматического формирования топологии, т.к. на объединенных входах схем 9 и 10 совпадения имеется-разрещающий сигнал с нулевого выхода триггера 8. При этом сигнал с выхода задатчика адреса, в котором записан начальный узел, не прийдет через соответствующую схему 16 совпадения, т.к. соответствующий триггер 15 находится в нулевом состоянии, а сигнал с выхода задатчика адреса, в котором записан конечный узел ветви, .поступит при совпадении с сигналом распределителя на выход схемы 14 разделения и через полюса всех моделей ветвей 1 на входы формирователей 3 временного интервента, На другие входы формирователей поступкают выходные сигналы задатчиков адресов и при совпадении с выходным сигналом блока автоматического формирования топологии будут Подготовлены к отсчету импульсов измерительной серии те из них, в задатчиках адресов которых записан номер конечного узла рассматриваемой ветви. При этом импульс выхода соответствующей схемы 16 совпадения блока 2 автоматического формирования топологии установит в нулевое Состояние соответствующий триггер ,15, тем самым .запрещая вторичное прохождение сигнала через эту схему совпадения. Выходной сигнал распределителя 13 с-блока 2 ав томатического формирования топологии запретит вновь прохождение импульсов на вход задатчиков адресов и разрешит их поступление на модели ветвей. В момент появления сигнала на входе блока управления, свидетельствующего об окончании формирования временного интервала ветви, смежной с конечным углом.

устройство управления останавливает решение и выдает разрешение, на модели ветвей на входы схем 12 индикации для индикации дерева кратчайших путей. При этом измерительное устройство зафшсси- рует величину кратчайшего пути.

Пред, мет изобретения

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

6

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

|Соединены с выходами задатчиков адре- со,в узлов и триггера блокировки, а их выходы подключены к схемам индикации, триггеру блокировки и четвертому входу блока управления, входы первой и второй схем совпадения моделей ветвей подключены соответственно к выходам первого и второго задатчиков адресов и выходу триг; гера блокировки этих моделей, а выходы схем совпадения через схему -разделения каждой модели подключены ко входу блока автоматического формирования топологии и к пятому входу блока управления. HU ZD