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

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

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

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

Устройство содержит группу 1 элементов И, генератор 2 импульсов, первую группу 3 элементов ИЛИ, матрицу 4 моделей дуг, модели дуг 5, вход запуска устройства 6, первый коммутато 7, счетчик 8, ключ 9, вторую группу 10 элементов ИЛИ, дешифратор 11, второй коммутатор 12, В состав каждой модели дуги 5 кроме моделей дуг- пос- леднего столбца матрицы 4 моделей дуг, входят ключ 13, счетчик 14, элемент И 15, 16, входные и выходные полюса 17-22, В моделях дуг последнего столбца матрицы 4 моделей дуг ключи 13 отсутствуют,, Матрица 4 имеет размерность.

Устройство для определения кратчайшего пути графа работает следую- ЦД1М образом.

Перед началом работы в счетчик 8 заносят количество импульсов, допол- няюш,ее хщсло п до полной емкости счетчика (п - число вершин графа). С выхода счетч1П :а 8 на управляющий вход ключа 9 и управляющий вход второго коммутатора 12 поступает нулевой потенциал, поэтому сигналы на выходах коммутатора отсутствуют, В матрицу 4 моделей дуг .заносится информация о топологии исследуемого графа путем подачи единичных сигнало на установочные входы устройства 20 согласно матрице смежности. Соответствующие триггеры 16 переходят в единичное состояние, единичный потенциал с их выходов поступает па первые входы элементов И 15, Б счетчики 14 заносят количество импульсов, дополняющее веса дуг до полной емкости счетчиков. На управляюшД хе входы ключей 13 поступает нулевой потенциал, поэтому ключи 13 закрыты, С выходов счетчик ов 14 на вхо.цы элементов ШШ 3 и далее на вторые входы элементов И 1 подаемся нулевой потенциал, поэтому элементы И 1 не пропускают на

выход импульсы, поступающие на их первый вход. На управляющий вход первого коммутатора с выхода элемента ИЛИ 3 поступает нулевой потенциал, поэтому информационный вход первого коммутатора 7 скоммутирован на его первый выход.

При поступлении запускающего импульса импульсы с выхода генератора 2 через информационный вход и первый выход первого коммутатора 7 поступают, во-первых, на первые входы элементов И 1, но на их выходы не проходят ввиду нулевого потенцигша на

вторых входах элементов И 1; во-вторых, через полюса 22 моделей ветвей 5 первой строки матрицы 4 моделей дуг - на вторые входы элементов И 15 и далее через выходы этих элементов на входы счетчиков 14 моделей дуг, инцидентных первой (начальной) вершине графа. Счетчики 14 ведут счет импульсов. При переполнении счетчика 14 модели дуги наш:еньшего веса по

сравнению с остальными дугами, инцидентными первой вершине, на его выходе появляется сигнал, которьш поступает, через полюс 18 и элемент ИЛИ 3 на нулевые входы триггеров

16 одноименного данному счетчику 14 столбца матрицы моделей дуг 4 (через полюс 19), Триггеры 16 этого столбца переходят в нулевое состояние и уже до конца работы устройства запрещают прохожде1п-1е импульсов с вторь х входов элементов И 15 на их вьшоды.

Единичный потенциал переполнившегося счетчика 13 поступает на информационный вход закрытого ключа 13 этой же модели дуги. Единичный потенциал с выхода переполнившегося счетчика 14 через элемент ШШ 3 поступает на одноименный элемент И 1, на его второй вход. Поэтому импульсы генератора 2 начинают проходить

с выхода этого элемента И 1 через полюса 22 на вторые входы элементов И 15 той строки матрицы 4, которая одпоименна элементу И 1, Счет ведут счетчики 14 этой строки матрицы, Далее устройство работает ана.логично до того момента, когда .в какой-либо строке матрицы 4 первым переполнит- ся счетчик 14 модели дуги последнего, п-го столбца матрицы 4,

При этом единичный потенциал пере- полнившегося счетчика 14 через элемент ШШ 3 поступает на управляющий вход первого коммутатора 7,который

подключает свой информационный вход к второму выходу. Непосредственно с выхода этого счетчика 14 через полюс 8 единичный потенциал поступает на соответствующий выход устройства из числа п-й группы егй выходов, идентифицируя тем самым дугу, вошедшую в кратчайший путь из множества дуг, инцидентных последней (конечной) вершине. Наконец, единичный потенциал поступает на соответствующий вход из числа п-й группы входов второго коммутатора 12., а также на один из входов элемента ИЛИ 10, одноименного номеру строки, в которой находится переполнившийся счетчик 14. С выхода элемента ИЛИ 10 единичный потенциал через полюса 21 поступает на управляющие входы ключей 13 одноименного столбца матрии;ы 4 и открывает их.Поэтому единичный потенциал с выхода счетчика 14, который переполнился в данном столбце матрицы 4, через полюс 17 поступает, во-первых, на один из

10

t5

20

марный вес кратчайшего пути находят (вне- рамок устройства) путем суммирования веса входящих в него дуг. Условием правильного нахождения единственного кратчайшего пути является непоступление сигнала на втopoй выход устройства с выхода дешифратора 10.

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

Устройство для определения кратчайшего пути графа, содержащее генератор импульсов, матрицу моделей дуг, группу элементов И и первую группу элементов ИЛИ, причем модель дуги содержит триггер, элемент И и счетчик, выход триггера подключен к первому входу элемента И, выход которого подключен к счетному входу счетчика модели дуги, выход переполнения счетчика i-й модели дуги каж,до- го j-ro столбца матрицы моделей дуг подключен к i-му входу j-ro элемента

выходов соответствующей группы выхо- 25 ИЛИ первой группы (где 1, 1 ,2,... ,п),

30

35

дов устройства, идентифицируя тем самым еще одну дугу кратчайшего пути; во-вторых, на один из входов соответствующей группы входов второго коммутатора 12; в-третьих, на один из входов того элемента ИЛИ 10, который одноименен номеру строки с переполнившимся счетчиком 14. Далее аналогично идентифицируются все дуги кратчайшего пути по единичным потенциалам на соответствующих выходах устройства. Импульсы генератора 2 с второго выхода первого коммутатора 7 поступают, во-первых, на вход счетчика 8, который начинает счет импульсов; во- вторых, через открытый ключ 9 - на управляющий вход второго коммутатора 12, который с поступлением каждого импульса подключает к группе своих выходов вторую, третью и т.д. группы , своих входов. Если на входах дешиф- ратора 11 единичные потенциалы отсутствуют или присутствует единичный потенциал только на одном входе, то на выходе дешифратора 11 присутствует

40

выходам эле 1ентов И (1+1)-й ртроки матрицы моделей дуг, входы установки в 1 триггеров являются установочными входами устройства, отличающееся -тем, что, с целью расширения функциональных возможностей за счет определения количества дуг, принадлежащих кратчайшему пути, в него введены ключ, счетчик, вторая группа элементов ИЛИ, первый и второй коммутаторы, дешифратор, в модели дуг всех столбцов,кроме последнего, матрицы .моделей, дуг введены ключи, причем информационньш входк.пюча каж- 1ДОЙ модели дуги подключен к выходу переполнения счетчика этой же модели дуги, управляющие входы ключей моделей дуг каждого столбца, кроме последнего, матрицы моделей дуг объединены и подключены к выходу одноименного элемента ИЛИ второй группы, выходы ключей моделей дуг каждого i-ro столбца, кроме последнего, матрицы подк,пючены к i-й группе информационных входов второго коммутатора

нулевой потенциал, если же единичный 50 являются группой выходов идентифипотенциал присутств Гет хотя бы на двух входах, на выходе дешифратора 11 появляется сигнал. После отсчета п-го импульса счетчик 8 переполняется и вьщает единичный потенциал, во- первых, на выход окончания работы устройства; во-вторых,, на управляющий вход ключа 9, закрывая его.Сум

марный вес кратчайшего пути находят (вне- рамок устройства) путем суммирования веса входящих в него дуг. Условием правильного нахождения единственного кратчайшего пути является непоступление сигнала на втopoй выход устройства с выхода дешифратора 10.

Формула изобретенияУстройство для определения кратчайшего пути графа, содержащее генератор импульсов, матрицу моделей дуг, группу элементов И и первую группу элементов ИЛИ, причем модель дуги содержит триггер, элемент И и счетчик, выход триггера подключен к первому входу элемента И, выход которого подключен к счетному входу счетчика модели дуги, выход переполнения счетчика i-й модели дуги каж,до- го j-ro столбца матрицы моделей дуг подключен к i-му входу j-ro элемента

ИЛИ первой группы (где 1, 1 ,2,... ,п),

выходам эле 1ентов И (1+1)-й ртроки матрицы моделей дуг, входы установки в 1 триггеров являются установочными входами устройства, отличающееся -тем, что, с целью расширения функциональных возможностей за счет определения количества дуг, принадлежащих кратчайшему пути, в него введены ключ, счетчик, вторая группа элементов ИЛИ, первый и второй коммутаторы, дешифратор, в модели дуг всех столбцов,кроме последнего, матрицы .моделей, дуг введены ключи, причем информационньш входк.пюча каж- 1ДОЙ модели дуги подключен к выходу переполнения счетчика этой же модели дуги, управляющие входы ключей моделей дуг каждого столбца, кроме последнего, матрицы моделей дуг объединены и подключены к выходу одноименного элемента ИЛИ второй группы, выходы ключей моделей дуг каждого i-ro столбца, кроме последнего, матрицы подк,пючены к i-й группе информационных входов второго коммутатора

кации 1-й дуги, вошедшей в кратчайший путь, i-й вход каждого j-ro элемента ИЛИ второй группы соединен соответственно с выходом ключа 1-й модели дуги j-й строки матрицы моделей дуг,, выход генератора импульсов соединен с информационным входом первого коммутатора, управляющий

вход которого подключен к выходу п-го элемента ИЛИ первой .группы,пер вый выход первого коммутатора соединен с вторыми входами элементов И моделей дуг первой строки матрицы и с первыми входами всех элементов И группы, вторые входы которых подключены к входам одноименных элементов

.ИЛИ первой группы, входы установки в О i-x триггеров каждого j-ro столбца матрицы моделей дуг соединены с выходом i-ro элемента ИЛИ первой группы, второй вход первого коммутатора соединен со счетным входом счетчика и с информационным входом ключа, управляющий вход которого подключен к выходу переполнения счетчика

и является выходом окончания работы устройства, выход ключа подключен к управляющему входу второго коммутатора, группа выходов которого подключена к Труппе входов дешифратора,выход дешифратора является информационным выходом устройства, выход переполнения счетчика каждой i-и модели дуги последнего столбца матрицы подключен к одноименному входу п-й группы информационных входов второго коммутатора, к соответствующему входу i-ro элемента ИЛИ второй группы и является i-M выходом группы выходов

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

Редактор И. Касарда

Составитель Т. Сапунова

Техред И.Попович Корректор С. Черни

Заказ 4723/54Тираж 671 Подписное

ВНШПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов. Изобретение позволяет расширить функциональные возможности устройства за счет идентификации дуг кратчайшего пути и установления, является ли этот путь единственным. Устройство содержит группу элементов И, генератор импульсов, группу злементов ИЛИ, матрицу моделей дуг, модель дуги, вход запуска устройства, первый коммутатор, счетчик, ключ, вторую-группу злементов ИЛИ, дешифратор, второй коммутатор. Модель дуги каждого столбца, кроме пйслед- него, матрицы моделей дуг содержит ключ, счетчик, элемент И, триггер, входные и выходные полюса. В моделях дуги последнего столбца матрицы от- .сутствует ключ. Матрица имеет размерность п X п. 1 ил. i W