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

us. S Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах. ЦельнУ изобретения является повыше ние быстродействия устройства при ре шении задачи определения кратчайшего пути в графе со взвешенными вершинами. На фиг.1 представлена функциональ ная схема устройства; на фиг.2 - фун кциональная схема блока управления; на фиг.З - пример моделирования графа, на фи.4 - этапы; определения кра чайшего пути в графе; на фиг.5 - обо щенная структурная схемаустройства. Устройство,, (фиг. 1) содержит регистр 1 сдвига, реверсивный регистр 2 сдвига, сумматор 3, блок 4 управления, триггер 5, группу триггеров 6(1)-6(В), элементы И 7 и 8, две груп пы элементов И 9(1)-9(В) и 10(1) - / 10(В), элементы ИЛИ 11-13, элемент .И-ИПИ 14, элемент ИСКЛКНАЮ1ЦЕЕ ИЛИ 15 элемент ИЛИ-НЕ 16, группу элементов ИЛИ-НЕ 17(1)-17(В), ключи 18 и 19, информационные входы 20(1)-20(В), ин формационный выход 21, информационные входы 22(1)-22(В) и индикационные выходы 23(1)-23(В), где В - количество вершин в графе. Блок 4 управления (фиг.2) содержит генератор 24 импульсов, распределитель 25 импульсов, генератор 26 одиночных импульсов, когФ1утаторы 27 29, т иггеры 30-33, элемент 34 задержки, элементы И 35-39, элементы ИЛИ 40-42, элемент ИЛИ-НЕ 43, элементь1 НЕ 44 и 45. На фиг.5 обозначены блок 46 задания матрицы смежности, блок 47 определения кратчайшего маршрута, регистр 48, коммутатор 49 смежных вершин, многоканальный накапливающий блок 50 выбора минимальной суммы,вхо ды 51 задания весов вершин устройства, входы 52 задания начальной вершины устройства, выходы 53 признаков принадлежности дуг множеству дуг кратча;йшего пути устройства, -лактовые входы 54 и 55 устройства, коммутатор 56 инцидентных дуг и входы 57 задания конечной вершины графа устройства,.. На фиг.4а изображен пример графа со взвешенными вершинами, веса которых указаны внутри обозначения вер- шины. Начальная вершина обозначена буквой Н, а конечная - буквой К. Алгоритм поиска кратчайшего пути ; на графе фиг.4 заключается в следуюшем. Отмечают все вершины, связанные с начальной вершиной. Метка вершин осуществляется квадратом внутри вершины графа. К весу всех отмеченных вершин 8, 7 и 2 прибавляют вес начального узла, равный единице. Полученную сумму запоминают в отмеченных вершинах 9, 8 и 3. После этих операций завершают первый шаг вычислений, получают граф, изображенный fia фиг.46. Дальнейшие вычисления выполняют от всех ранее меченых вершин. Отмечают все вершины графа,связанные дугами с мечеными вершинами на предыдущем шаге вьгчйслений. На втором шаге вычислений метке подлежит конечная вершина и вершина с весом 4. Выделяют минимальную сумму весов из всех меченых ранее вершин, связанных направленными дугами с отмеченными вершийами Кис еесом 4.Вершина с весом 4 связана с :мечеными вершинами,в которых после первого шага вычислений сумма весов равна 8 и 3(фиг.4б). Минимальная сумма из 8 и 3 равна 3. Эта минимальная сумма 3 суммируется с весом вершины 4 и запоминается в ней в виде нового веса 4.+ 3 7 (фиг.4в). Аналогично для конечной вершины следует выбрать минимальную сумму из двух меченых вершин 9 и 8. Минимальная сумма, равная 8, цоступагацая из всех меченых на первом шаге вершин, суммируется с нулевым весом .конечной вершины и запоминается в ней . После второго шага ВЕ1числений имеем граф, изображенный на фиг.4в. Дуга, соединяющая конечную вершину с вершиной с весом 4, на втором шаге вычислений не учитывалась, так как вершина с весом 4 до начала второго шага вычислений не бьша мечена. Вычисления на третьем шаге вычислений выполняют Для всех меченьпс узлов . Теперь при выборе минимальной суммы весов, поступающей в конечный узел графа, необходимо учитывать все вершины графа, связанные направленными дугами с конечной вершиной., Итак, на третьем шаге вычислений в конечную вёрцину поступают суммы веCQg.-ИЗ вершин 9, 8 и 7 (фиг.4г). Минимальная сумма из 9, 8 и 7, равная 7, суммируется с нулевым весом конечной вершины и запоминается в конечной вершине вместо предыдущего значения 8, которое сформировалось на предыдущем шаге. На этом вычисления заканчиваются, так как состояние все меченых вершин не изменяется.

Таким образом, вес 7 конечной вершины графа после завершения вычислений равен длине кратчайшего пути. Конфигурация кратчайшего пути определяется из графа фиг.4г, начиная с конечного узла,вдоль той дуги,по которой поступает минимальная сумма весов, равная 7. Эта дуга соединяет ко нечную вершину с вершиной 7 на фиг.4г. Вершина 7 дугой кратчайшего пути соединяется с вершиной 3, которая соединена дугой с начальной вершиной Н. Следовательно, кратчайший путь на исходном графе (фиг.4а) проходит чере(з вершины 1, 2, 4, О и выделен двойными дугами.

Генератор 24 импульсов блока 4 управления (фиг. 2) вырабатывает последовательность тактовых импульсов частоты f, из которых распределитель 25 импульсов формирует п последовательностей .импульсов частоты f/n, сдвинутых друг.относительно друга на время 1/f, где п - количество разрядов представления веса узла графа,

. В режиме ввода веса узлов графа в регистр 1 сдвига коммутатором 28 (выполнен, например, в ввде переключателя на два положения) блока 4 управления подключают выход генератора 26 одиночных импульсов к входу установки в единицу триггера 30. С помоШ;ью-коммутатора 27 (выполненного, например, в виде клавишного переключателя) блока 4 управления задают двоичный код веса узла графа. Коммутатор 27 подключает в единичных разрядах двоичного кода веса узла соответствующие выходы распределителя 25 импульсов к входам элемента ИЛИ 40, на выходе которого формируется после- довательньш двоичный код веса узла, Например, если вес узла равен пяти 101, то выходы первого и третьего, разрядов распределителя 25 импульсов подключаются коммутатором 27 к входам элемента ,

Ввод последовательного двоичного . кода веса Узла в п-разрядный регистрЛ 1 сдвига осуществляется после подачи с помощью коммутатора 29 (выполненного, например, в виде кнопочного пере ключателя) единичного сигнала с выхода элемента НЕ 44 на вход запуска генератора 26 импульсов, который выделяет из последовательности импульсов выхода элемента И 35, действ тощих с частотой f/2n, одиночный импульс, устанавливающий через коммуQ татор 28 триггер 30 в единичное состояние на время n/f.

Триггер 31 из последовательности импульсов п-го разряда распределителя 25 импульсов формирует две последовательности импульсов.

Эти чередующиеся с частотой f/2n две последовательности импульсов на прямом и инверсном выходах триггера 31 определяют два временных цикла 0 работы устройства. Будем считать,что последовательность импульсов на прямом выходе триггера 31 определяет первый цикл, а на инверсном выходе - второй. Тогда триггер 30, установленный в единичное состояние одиночным импульсом в конце второго цикла, будет находиться в единичном состоянии в течение первого цикла, в конце которого он- устанавливается в нулевое состояние импульсом п-го раз-ряда распределителя 25 импульсов.

Единичный сигнал прямого выхода триггера 30,.поступая на управляющий вход регистра 1 сдвига, обеспечивает запись, начиная с младшего разряда,

5 последовательного двоичного кода веса узла графа, поступающего с вькода элемента ИЛИ 40 блока 4 управления на вход ввода данных регистра 1 сдвига. Запись двоичного кода в регистр

0 1 сдвига осуществляется под действием тактовых импульсов генератора 24 импульсов блока 4 управления, поступаюй1их на вход синхронизации регистра 1 сдвига. После записи двоичный

5 код веса узла графа хранится динамическим способом в регистре 1 сдвига за счет его циркуляции с выхода регистра 1 сдвига на его информационный Q вход под действием тактовых импульсов генератора 24 импульсов блока 4 управления.

В режиме ввода весов триггеры 6(1)-6(В) находятся в нулевом состо55

.янии, в которое их устанавливает по инверсному нулевому входу одиночной импульс генератора 26 одиночных им пульсов, поступающий через элемент НЕ 45 блока 4 управления. Триггер 5 устанавливается в нулевое состояние импульсами, действующими на выходе генератора 26 одиночных импульсов блока 4 управления. Триггер 32 блока 4 управления устанавливается в нулевое состояние импульсами первого разряда распределителя 25 импульсов. Последовательность импульсов выхода элемента И 35, действующая через элемент И 38, открыташ инверсным выходом триггера 32, устанавливает триггер 33 в нулевое состояние. После записи в первом цикле двоичного кода веса узла в регистр 1 сдвига этот код во втором цикле под действием, тактовых импульсов генератора 24 импульсов блока 4 управления записьшается, начиная с младшего разряда, через сумматор 4 в реверсивный регистр 2 сдвига. В режиме моделирования коммутатором 28 блока 4 упр авления подключают выход генератора 26 одиночных импульсов к единичному входу триггера 33. Начальный узел графа задают с помощью ключа 18, подключая выход генератора 26 одиночных импульсов блока 4 управления к входу элемента ИЛИ 11. Конечный узел грасЬа задают ключом 19, который соединяет инверсный выход триггера 33 блока 4 управления с одним из входов элемента ИЛИ 12. Пуск устройства осутдествляют коммутатором 29 блока 4 управления, с помощью которого на вход запуска генератора 26 одиночных импульсов п6дшот сигнал выхода элемента НЕ 44. Выходной импульс генератора 26 одиночных импульсов блока 4 управления поступает через коммутатор 28 на еди ничный вход триггера 33, устанавлива его в единичное состояние, и через. ключ 18 модуля, содержащего начальный узел графа, устанавливает триггер 5 этого модуля в единичное состо яние. Триггер 5 начального узла графа в единичном состоянии снимает блокировку первой и второй групп вхо дов элемента И-ШШ 14, блокируя его третью группу входов. Во время первого цикла работы уст ройства под действием единичнЪго сиг нала прямого выхода триггера 31 и по следовательности тактрвых импульсов генератора 24 импульсов блока 4 управления из реверсивного регистра 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 начинает поступать последовательность импульсов п-го разряда второго цикла, задержанная элементом 34 задержки на длительность тактового импульса генератора 24 импульсов блока 4 управления. Первьй .импульс последовательности выхода эл мента И 39 блока 4 управления устанавливает триггеры 6(1)-6(В) во всех модулях моделирующей структуры в еди ничные состояния, при которых снимается блокировка элементов ИЛИ-НЕ 17(1)-17(B), так как на инверсных выходах триггеров 6(1)-6(В) устанавливаются нулевые сигналы. Кроме того, в режиме моделирования, когда триггер 33 блока 4 управления устанавливается в единичное состояние, снимается блокировка элемента ИЛИ-НЕ 43 блока 4 управления со стороны инверсного выхода триггера 33. Управля ющая последовательность второго цикл с инверсного выхода триггера 31 блок 4 управления инвертируется элементом ИЛИ-НЕ 43 блока 4 управления и в виде управлякю1ей последовательности первого цикла поступает на вход элементов И 7 всех модулей моделирующей структуры. в первом цикле работы устройства в модулях моделирующей структуры,на информационные входы которых 20(1)-20(В) поступают последовательные двоичные коды, начиная со старшего разряда, осуществляется выбор наименьшего двоичного кода. Это выполняется следующим образом. Если хоть в одном двоичном коде в старшем разряде содержится нуль, то на выходе соответствующего элемента ИЛИ-Н 17 формируется единичный сигнал, который проходит через элемент И 7 на все элементы И 10(1)-10(В) и сбрасывает в нулевые состояния триггеры 6(1)-б(В) в. тех каналах, в которых, н информационных входах 20(1)-20(В) в старшем разряде действует единичный сигнал. Дальнейший анализ двоичных кодов по входам 20(1)-20(В) выполняется аналогично - поразрядно от стар шего разряда к .младшему - за, время первого цикла, составляющего п тактов. После окончания первого цикла в единичном состоянии оказывается триг гер 6 (к) К-го канала, в котором дей ствовал наименьший двоичный код (К 1,...,В). Во втором цикле работы устройства модули моделирующей структуры, наход щиеся в возбужденном состоянии, вьода 1 ют из реверсивного регистра 2 сдвига через элементы И-ИЛИ 14 на информационный выход 2 последовательный двоичный код веса, начиная с младшего разряда, т.е. младшими разрядами вперед. Выдача двоичного кода из реверсивного регистра 2 сдвига осуществляется под действием тактовых импульсов генератора 24 импульсов и управляющей последовательности второго цикла, действующей на инверсном выходе триггера 31 блока 4 управления. Наименьший последовательный двоичный код, действующий, например, в К-м канале, поступает младшими разрядами вперед через элементы ШШ-НЕ 17 (К), ИЛИ 13 и ИЛИ-НЕ 16 на вход посладовательно:ГО двоичного сумматора 3,на другой. вход которого под действием тактовък импульсов генератора 24 импульсов блока 4 управления сдвигается с выхода регистра 1 сдвига последовательный двоичный код веса узла данного модуля моделируюп ей структуры. Сумиатор 3 выполняет последовательно во времени, начиная с младшего разряда, суммирование двоичного кода регистра 1 сдвига и наименьшего двоичного кода, поступающего по информационному входу 20 (к). Результат суммирования с выхода сумматора 3 записьшается, начиная с младшего разряда, в реверсивный регистр 2 сдвига под действием тактовых икшульсов генератора 24 импульсов и управляющей последовательности второго цикла, формируемой на инверсном выходе триггера 31 блока 4 управления. Причем связь одного из входов элемента ИЛИ-НЕ 16 с прямым входом триггера 31 блока 4 управления обеспечивает передачу кодов через этот элемент только во время второго цикла работы устройства. Во время передачи наименьшего двоичного кода с информационного входа 20(К) через элементыЦПИ-НЕ 17 .(К) и ИЛИ 13 в последнем п-м разряде второго цикла происходит установка триггера 5 данного модуля в единичное ,, состояние, т.е. передача возбузвдения от одного МОДУЛЯ моделирующей структура. к другому. Действительно, в п-м . (старшем) разряде наименьшего кода содержится нуль, который преобразуется при передаче через элемент ИЛИ-НЕ 17 (к) в единичный сигнал, устанавли-: вающий через элементы И 8 и ИЛИ t.1 , 15 триггер 5 данного модуля в -единичное состояние. В дальнейшем устройство работает аналогичным образом. Последовательный двоичный код веса начального узла графа передает возбуждение вычислительного процесса на другие модули моделирующей структуры, которые в первом цикле выделяют. наименьший двошгный код из всех кодов, действующих на информационных входах 20(1)-20(В)5 а во .втором цикле прибавляют к наименьшему двоичному коду вес узла данного модуля моделирункцей структурь. Невозбужденные модули моделирующей структуры в процессе работы выдают в первом цикле максимальньш двоичный :код - единицу в первом (старшем) разряде, поступающу с выхода элементй И 37 блока 4 управ ления через атемент 42 блока 4 управ ления и элемент И-ИЛИ 14 на информационный выход 21 данного модуля. Поэтому максимальные двоичные коды, по отстающие от невозбу кденных модулей моделирующей структуры на информационные входы 20(1)-20(В) данного мо дуля, не влияют на выбор наименьшего двоичного кода из всех кодов, поступагацих от возбужденных модулей. Если на все информационные входы 20(1)-20(В) данного модуля пос тупают максимальные двоичные коды от невозбулденных других модулей, то данный модуль остается в невозбужденном состоянии, так как импульс п-го разряда второго цикла с выхода элемента И 35, поступая через элемент . ИЛИ 42 блока 4 управления и элемент .И-ИЛИ 14 невозбякденного модуля, про ходит по входу 20(к) данного модуля на в.ыход элемента 1-ШИ-НЕ 17(К) в виде нулевого сигнала, который блоки- рует элемент И 8 и предотвращает установку триггера 5 данного модуля в единичное состояние. В это время эле мент 16 блокируется импульсом п-го разряда второго цикла, поступающего с выхода элемента И 35 блока 4 управления. В процессе моделирования триггер 33 блока 4 управления сохраняет единичное состояние, так как в процессе вычислений последовательные двоичные коды, сдвигаемые младшими разрядами вперед с выхода реверсивного регистра 2 сдвигс, и двоичные коды, действующие на выходе суммато4ра 3, различны. Поэтому на выходах элементов ИСКЛЮЧАЮЩЕЕ РШИ 15 модулей формируются единичные сигналы, которые поступают на входы элемента ЕЛИ 41 блока 4 управления и через элемент И 36, открытый во втором цикле сигналом инверсного выхода триггера 31, устанавливают триггер 32 в единичное состояние до момента действия импульса п-го разряда второго цикла на выходе элемента И 35. В результате элемент И 38 во время действия импульса п-го разряда второго цикла закрыт нулевым сигналом инверсного выхода триггера 32, и триггер 33 сохраняет в процессе вычислений единичное состояние. Процесс вычислений в моделирующей структуре заканчивается, когда процесс возбуждения распространяется от начального узла графа во все другие его узлы В этом случае в моделирующей структуре наступает динамическое равновесие. Каждый модуль модулирующей структуры на Р-м шаге вычислений выделяет по входам 20(1) 20(в) такой же наименьший двоичный код, который был выделен на предьщущем (Р-1)-м шаге вычислений. В каждом модуле моделирующей структуры сумма наименьшего двоичного кода, вьщеленного по входам 20(1)-20(В), с двоичным кодом веса узла данного модуля, сдвигаемого с выхода регистра 1 сдвига, на Р-м шаге вычислений равна сумме, выделенной на предыдущем (Р -О-м шаге вычислений и хранящейся в реверсивном регистре 2 сдвига. На BbiKcie элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 15 всех модулей моделирующей структуры действует во время вторых циклов нулевые сигналы, и триггер 32 блока 4 управления устанавливается в нулевое состояние импульсом первого разряда распределителя 23 импульсов. Импульс п-го разряда, второго цикла, действующий на выходе элемента И 35, устанавливает через элемент И 38 триггер 33 в нулевое состояние. Единичный сигнал, формируемый на инверсном выходе триггера 33 блока 4 управления, поступает через ключ 19 в модуль,содержащий конечный узел графа. Если в этом модуле наименьший двоичный код действует по Т-му входу и триггер 6 (т) находится в единичном состоянии, то единичный сигнал с выхода ключа 19 проходит через элементы ИЛИ 12, и 9 (к) на индикационный выход 23 (т) и далее поступает на один из индикационных входов 22(1) 22(в) предащущего модуля моделирующей структуры. Если в этом модуле на меньший двоичный код действует по К-му входу и триггер 6 (К) находится в единичном состоянии, то единичный сигнал индикации 23 (К) и далее рас пространяется по модулям моделирующей структуры от конечного узла графа к начальному узлу вдоль кратчайше пути, I оторому соответствует наимень щая сумма весов узлов графа,. Двоичный код, пропорциональный дл не кратчайшего пути, формируется в процессе моделирования в реверсивном регистре 2 сдвига модуля, содержащего конечный узел графа. После окончания вычислений наименьшая сумма ве сов графа между начальным и конечным узлами выдается во время второго цик ла под действием тактовых импульсов генератора 24 импульсов блока 4 управления из реверсивного регистра 2 сдвига через элемент И-ИЛИ 14..на информационный выход 21 модуля, содержащего конечный узел графа. Таким образом, в общем виде работа устройства может быть представлен следующим образом (фиг.5). Перед началом работы обнуляют регистр 48, в блок 46 задания матрицы смежности заносят информацию о топол гии графа, в каналы блока 50 заносят коды весов вершин графа-, те же коды подают на входы 51. Один из разрядов регистра 48, который соответствует номеру начальной вершины пути, устанавливают по входу 52 в единичное со стояние. При этом коммутатор 49 выдает на свои выходы состав вершин. смежных с опрошенными, а коммутатор 56 на свой (К,М)-й информацио ный вход (К 1,... ,В; М 1,.,.,В) код, поступивший на его К-й информационный вход, если К-й информационный вход подключен и есть разрешение , на подключение К-го информациоцнтэго входа на М-й информационный выход, тем на (К,М)-й информационный выход передается вес пути, накопленный К-м каналом блока 50. Через врлмя, достаточное для завершения указа ных операций, на вход 55 устройства

подают импульс уровня логической еди;ницы. При этом каждый канал блока 50 складывает значение первого слаглемрмножеству дуг кратчайшего пути ус тройства, отличающееся тем, тем, что, с целью повышения быстродейго со значениями каждого из В вторых, слагаемых (отличных от нуля), выбирает минимальное значение суммы, сравнивает его с ранее накопленным и, если последнее окажется больше, фиксирует текущее значение суммы и номер второго слагаемого. Таким образом, выбирается минимальный из всех путей в каждую вершину из всех уже достигнутых вершин и отмечаются дуги, принадлежащие кратчайшему пути,Через время, достаточное окончания указанных процессов, на вход 54 устройства подакху импульс уровня логической единицы. При этом регистр 48 фиксирует (по ИЛИ) информацию, поступившую на его информационный вход, тем самым в состав достигнутых включаются новые вершины. Далее работа устройства повторяется до тех пор, пока блок 50 не зафиксирует отсутствие каких-либо изменений (значения минимальной суммы в любом из каналов или ее позиции). При этом блок 47 определения кратчайшего маршрута формирует на выходах 53 устройства признаки принадлежности дуг множеству дуг кратчайшего пути. Формула изобретения Устройство для решения задач на графах, содержащее блок задания матрицы смежности, блок определения кратчайшего маршрута, регистр, коммутатор смежных вершин и коммутатор инцидентных дуг, причем К-й разряд информационного выхода регистра (К 1,...,,В, где В - количество вершин в графе) подключен к К-му информационному входу коммутатора смежных вершин и к входу подключения К-го информационного направления коммутатора инцидентных дуг, выход значения (К,М)-го элемента блока задания матрицы смежности (М 1,...,В) подключен к входам разрешения подключения К-го информационного входа на М-й информационный выход коммутатора смежных вершин и коммутатора инцидентных дуг и к входу признака наличия (К,М)гй дуги блока определения кратчайшего маршрута, выход признака принадлежности (К,М)-и дуги кратчайшему маршруту которого является выходом признака принадлежности (К,М)-й дуги ;: ствия устройства при определении кратчайшего пути в графе со взвешенными вершинами, в него введен многоканальный накапливающий блок выбора минимальной суммы, причем, М-й инфор мационный выход коммутатора смежных вершин подключен к М-му разряду информационного входа регистра, вход установки в 1 К-го разряда которого является входом задания начальной вершины графа устройства, вход задания веса К-й вершины которого подключен к входу, первого слагаемого К-го канала мнЬгоканального накапливающего блока выбора минимальной суммы, информационный выход К-го канала которого подключен к К-му информационному входу коммутатора инцидентных дуг, (К,М)-й информационный выход которого подключен к К-му входу второго

„ Z2rfJ слагаемого М-го канала многоканального накапливакж его блока выбора минимальной суммы, К-й выход позиции минимальной суммы М-го канала которого подключен к входу признака принадлежности (К,М)-й дуги множеству дуг кратчайшего маршрута блока определения кратчайшего маршрута, М-й вход заданий конечной вершины маршрута которого является М-м входом задания конечной вершины графа устройства, первый и второй тактовые входы которого подключены соответственно к входу .: . признака записи регистра и к тактовому входу многоканального накапливающего блока выбора минимальной суммы, выход признака отсутствия изменений которого подключен к входу опроса конечной вершины блока определения кратчайшего маршрута.

.

1

н

Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графах. Целью изобретения является повышение быстродействия устройства при решении задачи определения кратчайшего пути в графе со взвешенными вершинами. Устройство содержит блок 46 задания матрицы смежности, блок 47 определения кратчайшего маршрута, регистр 48, коммутатор 49 смежных вершин, многоканальный накапливающий блок 50 выбора минимальной суммы, входы 51 задания весов вершин устройства, входы 52 задания начальной вершины устройства, выходы 53 признаков принадлежности дуг множеству дуг кратчайшего пути устройства, тактовые входы 54, 55 устройства, коммутатор 56 инцидентных дуг и входы 57 задания конечной вершины графа устройства. Перед началом работы обнуляют регистр 48, в блок 46 заносят информацию о топологии графа, в каналы блока 50 заносят коды весов вершин графа, те же коды подают на входы 51. Один из разрядов регистра 48, соответствующий номеру начальной вершины пути, устанавливают по входу 52 в единичное состояние. На входы 54, 55 подают поочередно тактовые импульсы уровня логической единицы. При этом блок 47 формирует на выходах 53 устройства признаки принадлежности дуг множеству дуг кратчайшего пути. 5 ил.