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

и один из входов каждого элемента ИЛИ соединены с соответствующими выходами блока управления. Кроме того, формирователь веса дуги со держит триггер, входы которого подключены к управляющим входам формирователя веса дуги, а выход - к одному из входов элемента И, второй вход которого соединен с входом формирователя веса дуги, выход под ключен к входу счетчика, выход которого сО единен с выходом формирователя веса дуги. На фиг. 1 представлена блок-схема пред лагаемого устройства на фиг. 2 - блок-схе ма формирователя весов дуг (ФВД). Устройство содержит модель сети 1 (МС блок 2 управления, генератор импульсов 3, формирователи весов дуг (ФВД) 4 1, гг,п, 5 fq , триггеры 6 6 элементы 9,10,11-11, полюсы модели. Ti,) ---- -j --п. Модель сети представляет собой матрицу однородных ячеек формирователей весов дуг размером Т. ч П. где П. - максимальное число узлов моделируемого графа. Выходы формирователей весов дуг, распо ,io veHHbix в одном столбце МС подключены к входам одного из многовходовых элеменвь:ход которого с единичным входом соответствующего триггера 6, 6..., 6f ЕдиН лчнь Й вы.ход триггера 6 первого столбца МС соединен с элементом И 7 , выход которого подключен к входам формиро вателей весов дуг первой строки МС. Единичкьгй выход триггера 6 второго столбца соединен с элементом И 7 , выход которого подключен к входам формирователей весов дуг второй строки МС и т.д. Выходы 6 , кроме того, сотриггеоов 6. 2:- единены с блоком управления. Дополнительные входы схем ИЛИ 5, 52,..-, 5... и вто рые входы схем И 7-, 72---, подключены соответственно к блоку управления. Формирователь весов дуг (см. фиг. 2) содержит счетчик 12, элемент И 13, триггер 14. Вход ФВД является входом элемента И 13 второй вход этого элемента И соединен с единичным выходом триггера 14, входы которого соединены с поПюсами установки топологии и подключены полюсами 15 и 16 к блоку управления (на фиг. 1 эти полюса и связи не указаны). Выход элемента И 13 подключен к входу счетчика 12, выход кото рого является выходом ФВД. Устройство работает следующим образом. Первоначально в МС заносится информаия о топологии моделируемого графа и веах дуг. При этом один из триггеров 6 , б..., 6. соответствующий начальному узу, через один из полюсов 11.,, 11„,..., llj МС сигналом из блока 2 управления устанавливается в единичное состояние. Соответствующая ячейка ФВД определяется пеесечением строки МС с номером, равным омеру начального узла моделируемой ветки, столбца МС и номером, равным номеру ее онечного узла. Триггеры 14 ФВД, которые не участвуют в формировании топологии моделируемого графа, блокируются сигналом из блока управления на полюсе 15, который устанавливает триггер в нулевое состояние. Триггеры 14 ФВД, моделирующих ветви графа, устанавливаются в единичное состояние сигналом из блока управления, поступающим на полюс 16. В счетчики 12 соответствующих ФВД заносится количество импульсов, дополняющее длительности ветвей до полной емкости счетчиков. С появлением пускового сигнала блок 2 управления разрещает прохождение импульсов генератора 3 с полюса 1О на полюс 9, на входы всех элементов И 7 ..., 7 мОдели сети 1. Пройдя через тот элемент другом входе которого присутствует разрешение с одного из триггеров 6, 6 ,..., 6 столбца, моделирующего начальный узел, эти импульсы поступают на входы ФВД строки, одноименной данному столбцу. При этом импульсы будут проходить на входы тех ФВД, которые моделируют веса дуг, исходящих из начальных узлов. Отсчитав количество импульсов, пропорциональное весу моделируемой дуги, счетчик 12 ячейки ФВД, имеющий минимальный вес, переполнится. Импульс переполнения пройдя черезсоответствующий элемент ИЛИ (5, 5 ,..., 5 ) устанавливает в единичное состояние триггер (6 , 6, 6 ) столбца МС, в котором находится эта ячейка ФВД. Сигнал этого триггера поступает на соответствующий элемент И (7 , 7„ , 1 ) и разрешает прохождение импульсов на ФВД строки, одноименной данному столбцу. Счетчик 12 ФВД, имеющий наименьший вес в этой строке, своим импульсом переполнения через соответствующий элемент ИЛИ устанавливает в единичное состояние триггер столбца МС, в котором находится данный ФВД.

Вычислительный процесс продолжается до тех пор, пока на всех полюсах 8 , 8 ,... 8,, не появятся высокие потенцишты. Это свидетельствует о том, что все узлы исследуемого графа сформированы. Блок 2 управ- 5 ления при этом прекращает подачу импульсов на полюс 9. Суммарное количество импульсов, поступившее на полюс 9, будет равно кратчайшему пути графа. Формула изобретения 1. Устройство для определения кратчай- 15 шего пути в графе, содержащее формирователи весов дуг в строках и столбцах матричной модели сети, элементы И, ИЛИ, триггеры по числу узлов графа, блок управления, соединенный входом с выходом генерато- 20 ра импульсов, отличающееся тем, что, с целью повышения быстродействия, ь нем выходы формирователей весов дуг одного столбца соединены с входами одного из элементов ИЛИ, число которых равно числу столбцов, выход каждого элемента ИЛИ подключен к единичному входу соответствующе10 триггера, единичный выход которого соединен с входом блока управления и с первым входом элемента И строки, номер которой соответствует номеру столбца, выход элемента И подключен к входам формирователей весов дуг этой же строки, вторые входы элементов И и один из входов каждого элемента ИЛИ соединены с соответствующими выходами блока управления. 2. Устройство по п. 1. о т л и ч а е е с я тем, что формирователь веса дуги содержит триггер, входы которого подключены к управляющим входам формьрователя веса дуги, а выход - к одномл из i-.xo дов элемента И., второй вход которого соединен с входом формирователя веса дуги, вь ход - подключен к входу счетчика, выход которого соединен с выходом форкшрователя веса дуги.

Фиг.1

0 о

75 /ff

Фиг. 2