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

 

@аi

J г

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Социалистических Республик

485451 (61) Дополнительное к авт. свид-ву (22) Заявлено27.12.71 (21)1729569/18-24 с присоединением заявки № (23) Приоритет— (43) Опубликовано25 09 75 Бюллетень № 35 (51) М. Кл.

Q06 f 15/20

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

Совета Министров СССР по делам изооретекий и открытий (53) УДК

681.326(088.8) (45} Дата опубликования описания 3О.О1 76 (72) Авторы изобретения

В, B. Васильев, А. Г. Додонов, Е. А. Ралдугин и В. В. Хаджинов

Институт электродинамики АН Украинской ССР (71) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ

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

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

11ель изобретения - повышение надежности и быстродействия устройства.

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

На чертеже представлена блок-схема устройства.

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

3 триггер 8 блокировки, схема 9 и 10 совпаденияя, схему 1 1 разделения, схему 1 2 индикации, разделитель 13 импульсов, схему 14 разделения, триггеры 15 и схемы 16

/ совпадения.

Устройство работает следующим образом.

Предварительно в задатчики 6 и 7 ад1 ресов, в качестве которых будем рассматривать счетчики, заносят, соответствен10 но, адреса узлов, принадлежащих моделируемой ветви. В формирователи 5 временно

ro интервала заносят длительности соответствующих ветвей. Триггеры 8 блокировки всех моделей ветвей и триггеры 15 блока, автоматического формирования топологии предварительно устанавливают в единочиое состояние. При этом на соответствующих входах схем 9 и 10 совпадения будет присуствовать запрещающий сигнал с нулевого выхода триггера 8, а на соответствующих входах схем 16 совпадения блока 2 автоматического формирования топологиисигналы с единичных выходов соответствующих триггеров 15, 25

Дпя запуска всех моделей ветвей, исходящих из начального узла, блок управления разрешает прохождение импульсов на входы всех задатчиков 6 и 7 адресов узлов всех моделей ветвей 1 и распределителя 13 импульсов блока 2 автоматического формирования топологии. При этом, в момент переполнения задатчиков 6 и 7 адресов, в одном из которых записан адрес начального узла, блок управления вы-. даст пусковой импульс на входы схемы 16 совпадения блока 2 автоматического формирования топологии, Пусковой сигнал пройдет через ту схему совпадения, на 411 втором входе которой будет . присутствовать сигнал разделителя 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 кого формирования топологии и задатчиков адресов узлов, второй выход подключен к схемам индикации моделей ветвей, а третий выход к формирователям временных интервалов моделей, о т л и ч а ю ш е е с я тем, что, с целью повышения надежности и быстродействия, выход блока автоматического формирования топологии соединен с формирователями временных интервалов и со вторым входом блока управления, а другой его выход подключен к третьему, входу блока управления, входы формирова „ гелям временных интервалов моделей. ,соединены с выходами задатчиков адресов узлов и триггера блокировки, а их выходы подключены к схемам индикации, триггеру блокировки и четвертому входу блокауправления, входы первой и второй схем совпадения моделей ветвей подключены соответственно к выходам первого и второго задатчиков адресов и выходу триггера блокировки этих моделей, а выходы схем совпадения через схему -разделения каждой модели подключены ко входу блока автоматического формирования топологии и к пятому входу блока управления.

4 85451

И". М! 0Я

Тираж 679 Подписное

Заказ, ЯЯ

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

Москва, П3035, Раушская наб., 4

Предприятие «Патент», Москва, Г-59, Бережковская наб., 24

Составитель Е,Артамонов

Редакто """P А.<орозова Ре"Ред Я.Ханеева оРРектоР Г.фисенко