Устройство для решения задач на графах

,г:.1 Ц 33 ЯНИ 1 ИМ Ь,1 Б ,.1 ф 3 1 Я К А ИС ЕЛЬСТру и видетельство СССР06 Г 15/20, 1985. идетельство СССР06 Р 15/20, 1984. ДЛЯ РЕШЕНИЯ ЗАДАЧ ГОСУДАРСТВЕННЫЙ КОМИТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТПРИ ГКНТ СССР ВТОРСНОМУ СВИ 1(46) 30.09,90, Бюл. Нф 36 (71) Институт проблем моделирования в энергетике АН УССР(57) Изобретение относится к вычислительной технике и может .быть использовано для исследования путей в графах. Целью изобретения является повышение быстродействия устройства при решении задачи определения крат- чайшего пути в графе со взвешенными вершинами. Устроство содержит блок 46 задания матрицы смежности, блок 47 определения кратчайшего маршрута,регистр 48, коммутатор 49 смежных 2вершин, многоканальный накапливающи блок 50 выбора минимальной суммы, входы 51 задания весов вершин устрой ства, входы 52 задания начальной вер шины устройства, выходы 53 признаков принадлежности дуг множеству дуг кратчайшего пути устройства, тактовые входы 54,55 устройства, коммутатор 56,инцидентных дуг и входы 57 задания конечной вершины графа устройства, Перед началом работы обнуляют регистр 48, в блок 46 заносят информацию о топологии графа, в каналы блока 50 заносят коды весов вершин грайа, те же коды подают на входы 51 Один из разрядов регистра 48, соответствующий номеру начальной вершинь пути, устанавливают по входу 52 в единичное состояние. На входы 54, 55 подают поочередно тактовые импульсы уровня логической единицы. При этом блок 47 формирует на выходах 53 устройства признаки принадлежности дуг множеству дуг кратчайшего пути.5 ил.1596344 Составитель А.Мишинедактор Л.Веселовская Техред Л,Олийцьп Корректор М.Иароши Подписи нно-издательский комбинат "Патент", г. Ужгород, ул, Гагарина, 10 роизвод аказ 2911 Тираж 567 НИИПИ Государственного комитета по 113035, Москва, Жизобретениям и открытиям при ГКНТ СЧ Раушская наб., д. 4/5Изобретение относится к вычислительной технике и может быть использовано для исследования путей в грабах,5Целью изобретения является повышение быстродействия устройства при решении задачи определения кратчайшегопути в графе со взвешен.ыми вершинами, ЧОНа фиг.1 представлена функциональная схема устройства; на биг.2 - функциональная схема блока управления;на фиг.З - пример моделирования графа; на би.4 - этапы, определения крат чайшего пути в графе; на фиг.5 - обобщенная структурная схемаустройства.Устройство (биг. 1) содержит регистр 1 сдвига, реверсивный регистр2 сдвига, сумматор 3, блок 4 управления, триггер 5, группу триггеров6(1)-6(В), элементы И 7 и 8, две группы элементов И 9 (1) -9 (В) и 10(1)10(В), элементы ИЛИ 11-13, элемент.И-ИЛИ 14, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 15, 25элемент ИЛИ-НЕ 16, группу элементовИЛИ-НЕ 17(1)-17(В), ключи 18 и 19,информационные входы 20(1)-20(В), инбормационный выход 21, информационныевходы 22(1)-22(В) и индикационныевыходы 23(1)-23(В), где В - количество вершин в графе.Блок 4 управления (фиг.2) содержит генератор 24 импульсов, распреде-литель 25 импульсов, генератор 26одиночных импульсов, коммутаторы 27 -29, триггеры ЗО-, 33, элемент 34 за"держки, элементы И 35-39, элементыИЛИ 40-42, элемент ИЛИ-НЕ 43, элементы НЕ 44 и 45.40 На Ьиг.5 обозначены блок 46 задания матрицы смежности,блок 47 определения кратчайшего маршрута, регистр 48, коммутатор 49 смежных вершин, многоканальный накапливающий блок 50 выбора минимальной суммы,входы 51 задания весов вершин устройства, входы 52 задания начальной вершины устройства, выходы 53 признаков принадлежности дуг множеству дуг кратчайшего пути устройства, ъактовые входы 54 и 55 устройства, коммутатор 56 инцидентных дуг и входы 57 задания конечной вершины графа устройстваНа фиг,4 а изображен пример графа со взвешенными вершинами, веса кото-, рых указаны внутри обозначения вершины, Начальная вершина обозначенабуквой Н, а конечная - буквой К,Алгоритм поиска кратчайшего пути;на графе фиг.4 заключается в следующем.Отмечают все вершины, связанные с начальной вершиной. Метка вершин осуществляется квадратом внутри вершины граба. К весу всех отмеченных вершин 8, 7 и 2 прибавляют вес на чального узла, равный единице. Полученную сумму запоминают в отмеченных вершинах 9, 8 и 3. После этих операций завершают первый шаг вычислений, получают граф, изображенныйгйа биг.4 б. Дальнейшие вычислениявыполняют от всех ранее меченых вер" шин, Отмечают все вершины графа,связанные дугами с мечеными вершинамигна предыдущем шаге вычислений, На втором шаге вычислений метке подлежит конечная вершина и вершина с весом 4. Выделяют минимальную сумму весов из всех меченых ранее вершин, связанных направленными дугами с отмеченными вершийами К и с весом 4.Вершина с весом 4 связана с меченымивершинами,в которых после первого шага вычислений сумма весов равна 8 и 3 (фиг.4 б), Минимальная сумма из 8 и 3 равна 3. Эта минимальная сумма 3 суммируется с весом вершины 4 и запоминается в ней в виде нового веса 4,+ 3 = 7 (фиг.4 в). Аналогично для конечной вершины следует выбрать минимальную сумму из двух меченых вершин 9 и 8Минимальная сумма, равная 8, поступающая из всех меченых на первом шаге вершин, суммируется с ну" левым весом, конечной вершины и запоминается в ней 8 + 0 = 8. После второго шага внчислений имеем граф, изображенный на фиг,4 в. Дуга, соединяющая конечную вершину с вершиной с весом 4, на втором шаге вычислений не учитывалась, так как вершина с весом 4 до начала второго шага вычислений не была мечена.Вычисления на третьем шаге вычислений выполняют для всех меченых узловТеперь при выборе минимальной суммы весов, поступающей в конечный узел графа, необходимо учитывать все вершины графа, связанные направлен" ными дугами с конечной вершиной.Итак, на третьем шаге вычислений в конечную вершину поступают суммы ве- :аю из вершин 9, 8 и 7 (фиг.4 г). Ми 1596344 6нимальная сумма из 9, 8 и 7 равнаяр р го, например, в виде кнопочного пер7, суммируется с н левым веной ве шины и зау пк весом конеч- ключателя) единичного сигна апк ве - л с выхори запоминается в конеч- да элемента НЕ 44 на вход запусканой вершине вместо предыьдущего зна- генератора 26 импульсов, который вычения 8, которое сформировалось на деляет из последовательности импульпредыдущем шаге. На этом вычэтом вычисления сов выхода элемента И 35, действую -заканчиваются, так как состояние всех щих с частотой Е/2 п, одиночный иммеченых вершин не изменяется. пульс, устанавливающий через коммуТаким образом, вес 7 конечной татор 28 триггер 30 в единичноевершины графа после завеавершения вычис- состояние на время и/т,лений равен длине кратчайшего пути. Х риггер 31 из последовательностиКонфигурация кратчайшего пути оп еу ре- импульсов п-го разряда распределитеделяется из графа фиг.4 г начиная сР фа , (ачиная с ля 25 импульсов формирует две послеконечного узла в ольу , д ль той дуги,по ко довательности импульсов.Эти чередующиеся с " Г/2сов, равная 7. Эта дуга сое иняет ко-.Эду ди яет ко- две последовательности импульсов нанечную вершину с вершиной 7 нафиг.4 г. Вершина 7 гой кпрямом и инверсном выходах триггераиг. г. Вершина 7 дугой кратчайшего 31 определяют два временных циклапути соединяется с вершиной 3 котоо работы устройства. Будем считать,чторая соединена дугой с начальной веер- последовательность импульсов нашиной Н. Следовательно к атчайший/р тчайшии прямом выходе триггера 31 определяпуть на исходном графе (фиг,4 а) про- ет первый цикл, а на инверсном выхоходит через вершины 1, 2, 4, 0 и вы- де - второй. Тогда триггер 30, усделен двойными дугами. 25 тановленный в единичное состояниеГенератор 24 импульсов блока 4 уподиночным импульсом в конце второгоравления (фиг.2) вырабатывает после- цикла, будет находиться в единичномдовательность тактовых импульсов частоты Х из кото ыхсостоянии в течение первого цикла, втоты , из которых распределитель 25 конце которого он устанавливается вимпульсов формирует и последователь нулевое состояние импульсом и-го разностей .импульсов частоты Г/и сдви- ряда распредел т 25Уряда распределителя .5 импульсов.нутых друг.относительно друга на вре- Единичны".диничный сигнал прямого выходамя / , где и - количество разрядов триггера 30 поспоступая навход регистра 1 сдвига, обеспечивает. В режиме ввода веса узлов графа в запись, начиная с младшего разрядарегистр 1 сдвига коммутатором 28 последовательного двоичного кода ве(выполнен, например, в виде переклю- саса узла графа, поступающего с выходачателя на два положения) блока 4 уп-. эле ИЛИ 40 б 4элемента блока 4 управленияравления подключают выход генератора на вход ввода данных регистра 1 сдви 26 одиночных импульсов к входу уста- га 340 га. апись двоичного кода в регистрновки в единицу триггера 30, С помо сдвига осуществляется под действиимпульсов генератора 2пример, в виде клавишного переключа- импульсов блока 4 управления, постутеля) блока 4 управления задают дво- лаюЩих них на вход синхронизации регистичный код веса узла графа. Коммута- ра 1 Пр сдвига. осле записи двоичныйтор 27 подключает в единичных разря- код веса узлод веса узла графа хранится динамидах двоичного кода веса узла соответ- че кйм бческйм способом в регистре 1 сдвигаствующие выходы распределителя 25 им- за счет его циркуляции с выхода регипульсов к входам элемента ИЛИ 40 на ст а 1Э стра сдвига на его информационныйвыходе которого формируется после- вход под действием тактовых импульсовдовательный двоичный код веса узла. генерат 24генератора импульсов блока 4 упНапример, если вес узла равен пяти101, то выходы первого и третьего,разрядов распределителя 25 импульсов В режиме ввода весов триггерыподключаются коммутатором 27 к входам 6(1)-6(В) находятся в нулевом состоэлемента ИЛИ 40.55.янии, в которое их устанавливает поВвод последовательного двоичного инверсному нулевому входу одиночнйкода веса узла в и-разрядный регистр импульс генератора 26 одиночных им 1 сдвига осуществляется после подачи пульсов, поступающий через элементс помощью коммутатора 29 (выполненно-НЕ 45 блока 4 управления. Триггер 5устанавливается в нулевое состояниеимпульсами, действующими на выходегенератора 26 одиночных импульсовблока 4 управления. Триггер 32 блока4 управления устанавливается в нулевое состояние импульсами первого разряда распределителя 25 импульсов.(Последовательность импульсов выходаэлемента И 35, действующая через элемент И 38, открытый инверсным выходом триггера 32, устанавливает триггер 33 в нулевое состояние. После записи в первом цикле двоичного. кодавеса узла в регистр 1 сдвига этоткод во втором цикле нод действием,тактовых импульсов генератора 24 импульсов блока 4 управления записывается, начиная с младшего разряда, через сумматор 4 в реверсивный регистр2 сдвига,В режиме моделирования коммутатором 28 блока 4 управления подключаютвыход генератора 26 одиночных импульсов к единичному входу триггера 33. 25Начальный узел грайа задают с помощьюключа 18, подключая выход генератора26 одиночных импульсов блока 4 управления к входу элемента ИЛИ 11, Конечный узел грайа задают ключом 19, который соединяет инверсный выход триггера 33 блока 4 управления с однимиз входов элемента ИЛИ 12.Пуск устройства осуществляют коммутатором 29 блока 4 управления, с35помощью которого на вход запускагенератора 26 одиночных импульсов подают сигнал выхода элемента НЕ 44.Выходной импульс генератора 26 одиночных импульсов блока 4 управления.поступает через коммутатор 28 на единичный вход триггера 33, устанавливаяего в единичное состояние, ичерез.ключ 18 модуля, содержащего начальный узел графа, устанавливает триггер 5 этого модуля в единичное состояние. Триггер 5 начального узла графа в единичном состоянии снимаетблокировку первой и второй групп входов элемента И-ИЛИ 14 блокируя егоУ50третью группу входов.Во время первого цикла работы устройства под действием единичного сигнала прямого выхода триггера 31 и последовательности тактовых импульсовгенератора 24 импульсов блока 4 уп 55равления из реверсивного регистра 2сдвига осуществляется сдвиг двоично-.го кода веса начального узла графа,начиная со старшего разряда. Этотдвоичиый код, сдвигаемый из реверсивного регистра 2 сдвига старшими разрядами вперед, вновь записывается вреверсивный регистр 2 сдвига по входу записи при сдвиге влево, а такжечерез элемент И-ИЛИ 14 поступает наинформационный выход 21 модуля, содержащего начальный узел графа, и далее согласно топологии графа на информационные входы 20(1)-20(В) других модулей моделирующей структуры,Будем полагать в дальнейшем, что модули, у которых триггер 5 установленв единичное состояние, находятся ввозбужденном состоянии, а модули, содержащие триггер 5 в нулевом состоянии, находятся в невозбужденном состоянии,В невозбужденном состоянии модули вырабатывают на информационном выходе 21 последовательность двойныхимпульсов, формируемых на выходе элемента ИЛИ 42 блока 4 управления изпоследовательностей импульсов, которые вырабатываются на выходах элементов И 35 и 37 блока 4 управления, Навыходе элемента И 35 блока 4 управления формируется последовательностьимпульсов и-го разряда распределителя 25 импульсов, действующая во время второго цикла работы устройствапри единичном сигнале на инверсномвыходе триггера 31 блока 4 управления. На выходе элемента И 37 действует последовательность импульсов первого разряда распределителя 25 импульсов во время первого цикла работы устройствари единичном сигналена прямом выходе триггера 31 блока4 управления.Таким образом, на выходе элементаИЛИ 42 блока 4 управления формируетсяпоследовательность двойных импульсов, .действующих в первом разряде первогоцикла и в и-м разряде второго цикла работы устройства. Последовательность импульсов выхода элемента ИЛИ 42 блока 4 управления поступает через элементы И-ИЛИ 14 на информационные выходы 21 всех невозбужденных модулей модулирующей структуры, у которых триггер 5 находится в нулевом состоянии.После установки в единичное состояние триггера 33 блока 4 управления через элемент И 39 начинает поступать последовательность импульсов и-го раз35 ряда второго цикла, задержанная элементом 34 задержки на длительностьтактового импульса генератора 24 импульсов блока 4 управления. Первый.импульс последовательности выхода эле 5мента И 39 блока 4 управления устанавлив ае т триггеры 6 (1) -6 (В) во всехмодулях моделирующей структуры в единичные состояния, при которых снимается блокировка элементов ИЛИ-НЕ17(1)-17(В), так как на инверсныхвыходах триггеров 6(1)-6(В) устанавливаются нулевые сигналы. Кроме того, в режиме моделирования, когдатриггер 33 блока 4 управления устанавливается в единичное состояние,снимается блокировка элемента ИЛИ-НЕ43 блока 4 управления со стороны инверсного выхода триггера 33. Управляющая последовательность второго циклас инверсного выхода триггера 31 блока4 управления инвертируется элементом ИЛИ-НЕ 43 блока 4 управления и ввиде управляющей последовательности 25первого цикла поступает на вход элементов И 7 всех модулей моделирующейструктуры,В первом цикле работы устройствав модулях моделирующей структуры,на информационные входы которых20(1)-20(В) поступают последовательные двоичные коды, начиная со старшего разряда, осуществляется выборнаименьшего двоичного кода. Это выполняется следующим образом. Еслихоть в одном двоичном коде в старшемразряде содержится нуль, то на выходе соответствующего элемента ИЛИ-НЕ17 формируется единичныи сигнал, который проходит через элемент И 7 навсе элементы И 10(1)-10(В) и сбрасывает в нулевые состояния триггеры6(1)-6(В) в, тех каналах, в которых наинформационных входах 20(1)-20(В) встаршем разряде действует единичныйсигнал, Дальнейший анализ двоичныхкодов по входам 20(1)-20(В) выполняется аналогично - поразрядно от старшего разряда к,младшему - за времяпервого цикла, составляющего и тактов, После окончания первого цикла вединичном состоянии оказывается триггер 6 (К) К-го канала, в котором действовал наименьший двоичный код (К =551еуВ)еВо втором цикле работы устройетвамодули моделирующей структуры, находящиеся в возбужденном состоянии, выдают из реверсивного регистра 2 сдвига через элементы И-ИЛИ 14 на информа- ционный выход 21 последовательный двоичный код веса, начиная с младшего разряда, т.е. младшими разрядами вперед. Выдача двоичного кода из реверсивного регистра 2 сдвига осуществляется под действием тактовых импульсов генератора 24 импульсов и управляющей последовательности второго цикла, действующей на инверсном выходе триггера 31 блока 4 управления. Наимень- ший последовательный двоичный код, действующий, например, в К-м канале, поступает младшими разрядами вперед через элементы ИЛИ-НЕ 17 (К), ИЛИ 13 и ИПИ-НЕ 16 на вход последовательного двоичного сумматора З,на другой, вход которого под действием тактовъвс импульсов генератора 24 импульсов блока 4 управления сдвигается с выхода регистра 1 сдвига последовательный двоичный код веса узла данного модуля моделирующей структуры. Суьыатор 3 выполняет последовательно во времени, начиная с младшего разряда, суммирование двоичного кода регистра 1 сдвига и наименьшего двоичного кода, поступающего по информационному входу 20 (К). Результат суммирования с выхода сумматора 3 записывается, начиная с младшего разряда, в реверсивный регистр 2 сдвига под действием тактовых импульсов генератора 24 импульсов и управляющей последовательности второго цикла, формируемой на инверсном выходе триггера 31 блока 4 управления.Причем связь одного из входов элемента ИЛИ-НЕ 16 с прямым входом триггера 31 блока 4 управления обеспечивает передачу кодов через этот элемент только во время второго цикла работы устройства.Во время передачи наименьшего двоичного кода с информационного входа 20(К) через элементы ИЛИ-НЕ 17 (К) и ИЛИ 13 в последнем и-м разряде второго цикла происходит установка триггера 5 данного модуля в единичное состояние, т.е. передача возбуждения от одного модуля моделирующей структуры к другому. Действительно, в и-м (старшем) разряде наименьшего кода содержится нуль, который преобразует" ся при передаче через элемент ИЛИ-НЕ 17 (К) в единичный сигнал, устанавли-. вающий через элементы И 8 и ИЛИ 11, 1596344 2триггер 5 данного модуля в .единичное состояние.В дальнейшем устройство работает аналогичным образом.Последовательный двоичный код веса5 начального узла графа передает воз-. буждение вычислительного процесса на другие модули моделирующей структуры, которые н первом цикле выделяют наименьший двоичный код из всех кодов, действующих на информационных входах 20(1)-20(В), а но втором цикле прибавляют к нажгеньшему двоичному коду вес узла данного модуля модели15 рующей структуры. Ненозбуждепные модули моделирующей структуры в процессе работы выдают н первом цикле максимальный двоичный код - единицу в первом (старшем) разряде, поступающую 2 О с выхода элемента И 37 блока 4 управления через элемент 42 блока 4 управления и элемент И-ИЛИ 14 на информационный ньгход 21 данного модуля. По- . этому максимальные двоичные коды, поступающие от ненозбужденных модулей моделирующей структуры на информационные входы 20(1) - 20(В) данного модуля, не влияют на выбор наименьшего двоичного кода из всех кодов, поступающих от нозбужценных модулей. Если на все информационные входы 20(1)-20(В) данного модуля поступают максгпгальные двоичные коды от не возбужденных других модулей то дан 35 ный модуль остается н невозбужденном состоянии, так как импульс и-го разряда второго цикла с выхода элемента И 35, поступая через элемент ИЛИ 42 блока 4 управления и элемент 40 И-ИЛИ 14 ненозбжденного модуля, проходит по входу 20(К) данного модуля на вьгход элемента ИЛИ-НЕ 17(К) н виде нулевого сигнала, который блокирует элемент И 8 и предотвращает Ус тановку триггера 5 данного модуля в едигычное со"тояние. В это время элемент ИЛИ-НЕ 1 б блокиуется импульсом п-го разряда второго цикла, поступающего с выхода элемента И 35 блока 4 управления.В процессе моделирования триггер 33 блока 4 управления сохраняет единичное состояние, так как в процессе вычислений последовательные двоичные коды, сдвигаемые младшими разрядами вперед с выхода реверсивного регистра 2 сдвига, и двоичные коды, действующие на выходе сумматора 3, различны. Поэтому на выходах элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 модулей формируются единичные сигналы, которые поступают на входы элемента ИЛИ 41 блока 4 управления и через элемент И 36, открытый но втором цикле сигналом инверсного выхода триггера 31, устанавливают триггер 32 в единичное состояние до момента действия импульса и-го разряда второго цикла на выходе элемента И 35 В результате элемент И 38 во время действия импульса и-го разряда второго цикла закрыт нулевым сигналом инверсного выхода триггера 32, и триггер 33 сохраняет в процессе. вычислений единичное состояние.Процесс вычислений в моделирующей структуре заканчивается, когда процесс возбуждения распространяется от начального узла графа но все другие его узлы. В этом случае в моделирующей структуре наступает динамическое равновесие. Каждый модуль модулирующей структуры на Р-м шаге вычислений выделяет по входам 20(1) 20(В) такой же наименьший двоичный код, который был выделен на предыдущем (Р)-м шаге вычислений. В каждом модуле моделирующей структуры сумма наименьшего двоичного кода, выделенного по входам 20(1)-20(В), с двоичным кодом веса узла данного мо - дуля, сдвигаемого с выхода регистра 1 сдвига, на Р-м шаге вычислений равна сумме, выделенной на предыдущем (Р -1)-м шаге вычислений и хранящейся в реверсивном регистре 2 сдвига. На выхг ге элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 всех модулей моделирующей структуры действует во время вторых циклов нулевые сигналы, и триггер 32 блока 4 управления устанавливается в нулевое состояние импульсом первого разряда распределителя 25 импульсовИмпульс и-го разряда второго цикла, действующий на выходе элемента И 35, устанавливает через элемент И 38 триггер 33 в нулевое состояние. Единичный сигнал, формируемый на инверсном выходе триггера 33 блока 4 управления, поступает через ключ 19 в модуль,содержащий конечный узел графа. Если в этом модуле наименьший двоичный код действует по Т-му входу и триггер 6 (Т) находится в единичном состоянии, то единичный сигнал с выхода ключа 19 проходит через элементыИЛИ 12, И 9 (К) на индикационный выход 23 (Т) и далее поступает на1 один из индикационных входов 22(1) 22(В) предыдущего модуля моделирующей структуры. Если в этом модуле наименьший двоичный код действует по К-му входу и триггер 6 (К) находится в единичном состоянии, то единичный сигнал индикации 23 (К) и далее рас пространяется по модулям моделирующей структуры от конечного узла графа к начальному узлу вдоль кратчайшего пути,оторому соответствует наименьшая сумма весов узлов графа.Двоичный код, пропорциональный длине кратчайшего пути, формируется в процессе моделирования в реверсивном регистре 2 сдвига модуля, содержащего конечный узел графа. После окончания вычислений наименьшая сумма весов графа между начальным и конечным узлами выдается во время второго цикла под действием тактовых импульсов генератора 24 импульсов блока 4 уп равления из реверсивного регистра 2 сдвига через элемент И-ИЛИ 14.на информационный выход 21 модуля, содержащего конечный узел графа.Таким образом, в общем виде работа устройства может быть представлена следующим образом (фиг.5).Перед началом работы обнуляют регистр 48, в блок 46 задания матрицы смежности заносят информацию о топологии графа, в каналы блока 50 заносят коды весов вершин графа; те же коды подают на входы 51. Один из разрядов регистра 48, который соответствует номеру начальной вершины пути, уста навливают по входу 52 в единичное состояние. При этом коммутатор 49 выдает на свои выходы состав вершин, смежных с опрошенными, а коммутатор 56 выдает на свой (К,М)-й информационный вход (К = 1В; М = 1В) код, поступивший на его К-й информационный вход, если К-й информационный вход подключен и есть разрешение ,на подключение К-го информационного входа на М-й информационный .выход, тем самым на (К,М)-й информационный выход передается вес пути, накопленный К-м каналом блока 50. Через вр- мя, достаточное для завершения указанных операций, на вход 55 устройства55 подают импульс уровня логической единицы. При этом кажцый канал блока 50 складывает значение первого слагаемого со значениями каждого из В вторых слагаемых (отличных от нуля), выбирает минимальное значение суммы, сравнивает его с ранее накопленным и, е сли последнее окаже тся больше, фиксирует текущее значение суммы и номер второго слагаемого. Таким образом, выбирается минимальный иэ всех путей в каждую вершину из всех уже достигнутых вершин и отмечаются дуги, принадлежащие кратчайшему пути, Через время, достаточное окончания указанных процессов, на вход 54 устройства подают импульс уровня логической единицы, При этом регистр 48 фиксирует (по ИЛИ) информацию, поступившую на его информационный вход, тем самым в состав достигнутых включаются .новые вершины.Далее работа устройства повторяется до тех пор, пока блок 50 не зафиксирует отсутствие каких-либо изменений (значения минимальной суммы в любом из каналов или ее позиции). При этом блок 47 определения кратчайшего маршрута формирует на выходах 53 устройства признаки принадлежности дуг множеству дуг кратчайшего пути. Формула изобретения Устройство для решения задач на графах, содержащее блок задания матрицы смежности, блок определения кратчайшего маршрута, регистр, коммутатор смежных вершин и коммутатор инцидентных дуг, причем К-й разряд информационного выхода регистра (К =1В, где В - количество вершин в графе) подключен к К-му информационному входу коммутатора смежных вершин и к входу подключения К-го информационного направления коммутатора инцидентных дуг, выход значения (К,М)-го элемента блока задания матрицы смежности (М = 1В) подключен к входам разрешения подключения К-го информационного входа на М-й информационный выход коммутатора смежных вершин и коммутатора инцидентных дуг и к входу признака наличия (К,М)-, й дуги блока определения кратчайшегомаршрута, выход признака принадлежности (К,М)-й дуги кратчайшему маршруту которого является выходом признака принадлежности (К,М)-. й дуги;.множеству дуг кратчайшего пути услройства, о т л и ч а ю щ е е с я тем,тем, что, с целью повышения быстродей 16159634415ствия устройства при определениикратчайшего пути в графе со взвешенными вершинами, в него введен многоканальный накапливающий блок выбораминимальной суммы, причем, М-й информационный выход коммутатора смежныхвершин подключен к М-му разряду информационного входа регистра, входустановки в "1" К-го разряда которого является входом задания начальной вершины графа устройства, входзадания веса К-й вершины которогоподключен к входу. первого слагаемогоК-го канала мндгоканального накапли"вающего блока выбора минимальной суммы, инФормационный выход К-го каналакоторого подключен к К-му информационному входу коммутатора инцидентныхдуг, (К,М)-й информационный выход которого подключен к К-му входу второго слагаемого М-го канала многоканального накапливающего блока выбора минимальной суммы, К-й выход позицииминимальной суммы М-го канала которого подключен к входу признака принадлежности (К,М)-й дуги множеству дугкратчайшего маршрута блока определения кратчайшего маршрута, М-й вход заданий конечной вершины маршрута которого является М-м входом задания конечной вершины графа устройства, первый и второй тактовые входы которогоподключены соответственно к входу признака записи регистра и к тактовому входу многоканального накапливающего блока выбора минимальной суммы,выход признака отсутствия измененийкоторого подключен к входу опросаконечной вершины блока определениякратчайшего маршрута.