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

254502 2 5 О 55 1 1Изобретение относится к вычислительной технике и может быть использовано при исследовании параметровсетевых графов,Цель изобретения - расширениеФункциональных возможностей устройства за счет определения количествадуг, принадлежащих кратчайшему пути,и установления единственности этогопути.На чертеже представлена функциональная схема устройства для определения кратчайшего пути графа.Устройство содержит группу 1 элементов И, генератор 2 импульсов, первую группу 3 элементов ИЛИ, матрицу4 моделей дуг, модели дуг 5, вход запуска устройства 6, первый коммутатор7 счетчик 8, ключ 9вторую группу10 элементов ИЛИ, дешифратор 11, второй коммутатор 12, В состав каждоймодели дуги 5 кроме моцелей дугпоследнего столбца матрицы 4 моделейдуг, входят ключ 13, счетчик 14, элемент И 15, триггер 16, входные и выходные полюса 17-22. В моделях дугпоследнего столбца матрицы 4 моделейдуг ключи 13 отсутствуют. Иатрица 4имеет размерность.устройство для определения кратчайшего пути графа работает следующим образом,Перед началом работы в счетчик 8заносят количество импульсов, дополняющее число и до полной емкостисчетчика (и - число вершин графа). Свыхода счетчика 8 на управляющийвход ключа 9 и управляющий вход второго коммутатора 12 поступает нулевой потенциал, поэтому сигналы навыходах коммутатора отсутствуют. Вматрицу 4 моделей дуг заносится информация о топологии исследуемогографа путем подачи единичных сигналовна установочные входы устройства 20согласно матрице смежности. Соответствующие триггеры 16 переходят в единичное состояние, единичный потенциал с их выходов поступает на первыевходы элементов И 15. В счетчики 14заносят количество импульсов, дополняющее веса дуг до полной емкостисчетчиков, На управляющие входы ключей 13 поступает нулевой потенциал,поэтому ключи 13 закрыты, С выходовсчетчиков 14 на входы элементов ИЛИ3 и далее на вторые входы элементовИ 1 подается нулевой потенциал, поэтому элементы И 1 не пропускают на выход импульсы, поступающие на ихпервый вход. На управляющий входпервого коммутатора с выхода элемента ИЛИ 3 поступает нулевой потенциал, поэтому информационный вход первого коммутатора 7 скоммутирован наего первый выход.При поступлении запускающего импульса импульсы с выхода генератора 1 О 2 через информационный вход и первыйвыход первого коммутатора 7 поступают, во-первых, на первые входы элементов И 1, но на их выходы не проходят ввиду нулевого потенциала навторых входах элементов И 1; во-вторых, через полюса 22 моделей ветвей5 первой строки матрицы 4 моделейдуг - на вторые входы элементов И 15и далее через выходы этих элементов 2 О на входы счетчиков 14 моделей дуг,инцидентных первой (начальной) вершине графа. Счетчики 14 ведут счетимпульсовПри переполнении счетчика14 модели дуги наименьшего веса по 25 сравнению с остальными дугами, инцидентными первой вершине, на его выходе появляется сигнал, который поступает, через полюс 18 и элементИЛИ 3 на нулевые входы триггеров16 одноименного данному счетчику 14столбца матрицы моделей дуг 4 (черезполюс 19), Триггеры 16 этого столбцапереходят в нулевое состояние и ужедо конца работы устройства запрещаютпрохождение импульсов с вторых входов элементов И 15 на их выходы,Единичный потенциал переголнившегося счетчика 13 поступает на инфориационный вход закрытого ключа 13этой же модели дуги. Единичный потенциал с выхода переполнившегосясчетчика 14 через элемент ИЛИ 3 поступает на одноименный элемент И 1,на его второй вход. Поэтому импульсы генератора 2 начинают проходитьс выхода этого элемента И 1 черезполюса 22 на вторые входы элементовИ 15 той строки матрицы 4, котораяодноименна элементу И 1. Счет ведутсчетчики 14 этой строки матрицы. Далее устройство работает аналогичнодо того момепта, когда.в какой-либостроке матрицы 4 первым переполнится счетчик 14 модели дуги последнего,и-го столбца матрицы 4,При этом единичный потенциал пере"полнившегося счетчика 14 через элемент ИЛИ 3 поступает на управляющийвход первого коммутатора 7,который3 1254 подключает свой информационный вход к второму выходу, Непосредственно с выхода этого счетчика 14 через полюс М единичный потенциал поступает на соответствующий выход устройства из числа и-й группы его выходов, идентифицируя тем самым дугу, вошедшую в кратчайший путь из множества дуг, инцидентных последней (конечной) вершине. Наконец, единичный потенциал поступает на соответствующий вход из числа и-й группы входов второго коммутатора 12., а также на один из входов элемента ИЛИ 10, одноименного номеру строки, в которой находится переполнившийся счетчик 14. С выхода элемента ИЛИ 10 единичный потенциал через полюса 21 поступает на управляющие входы ключей 13 одноименного столбца матрицы 4 и открывает их,Поэтому единичный потенциал с выхода счетчика 14, который переполнился в данном столбце матрицы 4, через полюс 17 поступает, во-первых, на один из выходов соответствующей группы выходов устройства, идентифицируя тем самым еще одну дугу кратчайшего пути; во-вторых, на один из входов соответствующей группы входов второго коммутатора 12 в-третьих на один из вхоУЗР дов того элемента ИЛИ 10, который одноименен номеру строки с переполнив шимся счетчиком 14. Далее аналогично идентифицируются все дуги кратчайшего пути по единичным потенциалам на соответствующих выходах устройства.Импульсы генератора 2 с второго выхода первого коммутатора 7 поступают, во-первых, на вход счетчика 8, которык начинает счет импульсов; вовторых, через открытый ключ 9 - на управляющий вход второго коммутатора 12, который с поступлением каждого импульса подключает к группе своих выходов вторую, третью и т.д. группы3своих входов. Если на входах дешифратора 11 единичные потенциалы отсутствуют или присутствует единичный потенциал только на одном входе, то на выходе дешифратора 11 присутствует нулевой потенциал, если же единичный 5 Р потенциал присутствует хотя бы на двух входах, на выходе дешифратора 11 появляется сигнал. После отсчета и-го импульса счетчик 8 переполняется и выдает единичный потенциал, во первых, на выход окончания работы устройства; во-вторых, на управляющий вход ключа 9, закрывая его.Сум 502 4марный вес кратчайшего пути находят (вне рамок устройства) путем суммирования веса входящих в него дуг.Условием правильного нахождения единственного кратчайшего пути является непоступление сигнала на второй выход устройства с выхода дешифратора 10,формула изобретения.Устройство для определения кратчайшего пути графа, содержащее генератор импульсов, матрицу моделей дуг, группу элементов И и первую группу элементов ИЛИ, причем модель дуги содержит триггер, элемент И и счетчик, выход триггера подключен к первому входу элемента И, выход которого подключен к счетному входу счетчика модели дуги, выход переполнения счетчика -й модели дуги каждого 1-го столбца матрицы моделей дуг подключен к х-му входу 1-го элемента ИЛИ первой группы (где Ц=1,2п), выходам элементов И (1+1)-й строки матрицы моделей дуг, входы установки в "1" триггеров являются установочными входами устройства, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения количества дуг, принадлежащих кратчайшему пути, в него введены ключ, счетчик, вторая группа элементов ИЛИ, первый и второй коммутаторы, дешифратор, в модели дуг всех столбцов, кроме последнего, матрицы моделей. дуг введены ключи, причем информационный входключа каж,дой модели дуги подключен к выходу переполнения счетчика этой же модели дуги, управляющие входы ключей моделей дуг каждого столбца, кроме последнего, матрицы моделей дуг объединены и подключены к выходу одноименного элемента ИЛИ второй группы, выходы ключей моделей дуг каждого -го столбца, кроме последнего, матрицы подключены к -й группе информационных входов второго коммутатора и являются группой выходов идентификации 1-й дуги, вошедшей в кратчайший путь, 1-й вход каждого 1-го элемента ИЛИ второй группы соединен соответственно с выходом ключа 1-й модели дуги 1-и строки матрицы моделей дуг выход генератора импульсов соединен с информационным входом первого коммутатора, управляющий1254502 Ввход которого подключен к выходу п-го элемента ИЛИ первой группы,первый выход первого коммутатора соединен с вторыми входами элементов И моделей дуг первой строки матрицы и с первыми входами всех элементов И группы, вторые входы которых подключены к входам одноименных элементов .ИЛИ первой группы, входы установки в "О" х-х триггеров каждого 3-го10 столбца матрицы моделек дуг соединены с выходом -го элемента ИЛИ первой группы, второй вход первого коммутатора соединен со счетным входом счетчика и с информационным входом клю ча, управляющий вход которого подключен к выходу переполнения счетчика Составитель Т. СапуноваТехред И.Попович Корректор С. Черни/ Редактор И, 1(асарда Заказ 4723 Тираж 671 ВНИИ 1 П 1 Государственного коми по делам изобретений и отк 3035, Москва, Ж, Раушскаяисно ета СССытийнаб., д 4 едприятие, г. Ужгород, ул, Проектна изводственно-полиграфическо би является выходом окончания работы устройства, выход ключа подключен к управляющему входу второго коммутатора, группа выходов которого подключена к группе входов дешифратора,выход дешифратора является информационным выходом устройства, выход переполнения счетчика каждой д-й модели дуги последнего столбца матрицы подключен к одноименному входу и-й группы информационных входов второго коммутатора, к соответствующему входу -го элемента ИЛИ второй группы и яв" ляется -м выходом группы выходов идентификации п-й дуги, вошедшей в кратчайший путь, вход генератора импульсов является входом запуска устройства,