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

Союз СоветскикСоциал истицескихРеспублик О П И С А Н И Е и)в 25854ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ) М. Кл. С 06 У 15/2 осударстеенный комитетСовета Мннистроа СССРпо делан изобретенийн открытий 23) Приоритет -43) Опубликовано45) Дата опубли 08 76 Бюллетень 31 (5 З) 681.33 (088.8) ния 23,12,7 ння(72) Авторы изобретенн А. Г. Додонов, В. В. нов и В. М марев Институт электродинамики АН 1) Заявител скои( 54) УСТРОЙ Я ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТ В ГРАФЕ Известны также устройства ные для решения указанной зад топология моделируемого графа автоматически в процессе реше предназначеичи, в которых формируется ия25 Изобретение относится к вычислительной хинке и может быть использовано при по- роении специализированных вычислительны тройств,Задача определения кратчайшего пути меж- ду узлами в графе заключается в определении величины минимального из всевозможных путей, соединяющих эти узлы.Известны устройства, позволяющие решить эту задачу моделированием веса каждой дуги 10 графа формирователями весов дуг, основу которых составляют счетчики. Необходимойоперацией на таких устройствах является ручной набор топологии моделируемых сетей.Известны устройства, содержащие по чис лу узлов графа формирователи в строках и столбцах матричной модели сети, блок управления и соединенный с ним генератор импульсов. Однако при помощи таких устройств не-. возможно определить величины кратчайших 20 путей в графе. Это устройство содержит формирователивесов дуг в строках и столбцах матричноймодели сети, элементы И, ИЛИ, триггерыпо числу узлов графа, блок управления, соединенный входом с выходом генератора импульсов.Недостатком такого устройства являетсяразделение во времени процесса формирования топологии графа и процесса формирования весов дуг, что снижает быстродействиеустройства,Цель изобретения - увеличение быстродействия устройства,Для этого в предлагаемом устройстве выходы формирователей весов дуг одного столбца соединены с входами одного из элементовИЛИ, число которых равно числу столбцов,выход каждого элемента ИЛИ подключен кединичному входу соответствукнцего триггера, единичный выход которого соединен свходом блока управления и с первым входомэлемента И строки, номер которой соответс 1вует номеру столбца, выход элемента И подключен к входам формирователеи весов дугэтой же строки, вторые входы элементов Ии один нз входов каждого элемента ИЛИ соединены с соответствующими выходами блока управления. Кроме того, формирователь веса дуги содержит триггер, входы которого подключенык управля:ощим входам формирователя весадуги, а выход - к одному из входов элемента И, второй вход которого соединен сходом формирователя веса дуги, выход подключен к ьходу счетчика, вьход которого со единен с выходом формирователя веса дуги,Иа фиг. 1 представлена блок-схема пред -лагаемого устройства на фиг. 2 - блок-схема формирователя весов дуг ( ФВД) .Устройство содержит модель сети 1 МС),бок 2 ,поавления, генератор импульсов 3,формирователи весов дуг (ФВД) 41, 14 4элемсты ИЛИ 5 55 П триггеры 6201 2,6 6 элементы И 7, 7 , 783 Р у9,10,11. -11 полюсы модели.ГМодель сети поедставляет собой матрицу 25одно юдных ячеек формирователей весов дугразмером с х й где П, - максимальное число узлов моделируемого графа.Выходы формирователей весов дуг, расположенных в одном столбце МС подключены 30к входам одного из многовходовых элементо.: ,ЛИ 5, 5,, 5, вь.ход которого7" П,с:и;д:.пеп с единичным входом соответствуюь. го триг ера 6"диничаый вьход триггера 6 первого 35столбца МС соединен с элементом И 7вьход которого подключен к входам формирователей весов дуг первой строки МС. Единична;й выход триггера 6 второго столбца2МС соединен с элементом И 7, выход которого подключен к входам формирователейвесов дуг второй строки МС и т.д. Выходытриггеров 6, 6 , 6, кроме того, соединены с блоком управления, Дополнительные входы схем ИЛИ д 1, 52, 5 и втоГ45рь 1 е входы схем И 71, 72, 7 подключены соответственно к блоку управления.Формирователь весов дуг 1,см, фиг, 2)содержит счетчик 12, элемент И 13, триггео 14,Вход ФВД является входом элемента И 13,второй вход этого элемента И соединен сединичным выходом триггера 14, входы которого соединены с полюсами установки топологии и подключены полюсами 15 и 16 кблоку управления (на фиг. 1 эти полюса исвязи не указаны). Выход элемента И 13подключен к входу счетчика 12, выход которого является выходом ФВД. 4Устройство работает следующим образом.Первоначально в МС заносится информация о топологии моделируемого графа и весах дуг, При этом один из триггеров 616., 6, соответствующий начальному уз 2лу, через один из полюсов 11 111 2 "1 1 МС сигналом из блока 2 управленияустанавливается в единичное состояние. Соответствующая ячейка ФВД определяется пересечением строки МС с номером, равнымномеру начального узла моделируемой ветки,и столбца МС и номером, равным номеру ееконечного узла,Триггеры 14 ФВД, которые не участвуютв формировании топологии моделируемогографа, блокируются сигналом из блока управления на полюсе 15, который устанавливаеттриггер в нулевое состояние,Триггеры 14 ФВД, моделирующих ветвиграфа, устанавливаются в единичное состояние сигналом из блока управления, поступающим на полюс 16.В счетчики 12 соответствующих ФВД заносится количество импульсов, дополняющеедлительности ветвей до полной емкости счетчиков,С появлением пускового сигнала блок 2управления разрешает прохождение импульсов генератора 3 с полюса 10 на полюс 9,на входы всех элементов И 7 . 7 модее ули сети 1.Пройдя через тот элемент И,на другомвходе которого присутствует разрешение содного из триггеров 6 , 6 6 столб 1 2 Г 1ца, моделирующего начальный узел, эти импульсы поступают на входы ФВД строки, одноименной данному столбцу. При этом импульсы будут проходить на входы тех ФВД,которые моделируют веса дуг, исходящих изначальных узлов. Отсчитав количество импульсов, пропорциональное весу моделируемой дуги, счетчик 12 ячейки ФВД, имеющийминимальный вес, переполнится, Импульс переполнения, пройдя через соответствующийэлемент ИЛИ (51, 5 5 ) устанавливает в единичное состояние триггер ( 6 61 26 ) столбца МС, в котором находитсяэтаячейка ФВД. Сигнал этого триггера поступает на соответствующий элемент И (7, 71 2.7) и разрешает прохождение импульсов наФВД строки, одноименной данному столбцу,Счетчик 12 ФВД, имеющий наименьший весв этой строке, своим импульсом переполнения через соответствующий элемент ИЛИустанавливает в единичное состояние триггерстолбца МС, в котором находится данныйФВД,525954 Фиг. 1 Вычислительный процесс продолжается до тех пор, пока на всех полюсах 8 , 8 8 не появятся высокие потенциалы, Это свидетельствует о том, что все узлы исследуемого графа сформированы. Блок 2 управления при этом прекращает подачу импульсов на полюс 9.Суммарное количество импульсов, поступившее на полюс 9, будет равно кратчайшему пути графа, 1 О Формула изобретения 1, Устройство для определения кратчай щего пути в графе, содержащее формирователи весов дуг в строках и столбцах матричной модели сети, элементы И, ИЛИ, триггеры по числу узлов графа, блок управления, соединенный входом с выходом генерато ра импульсов, отличающееся тем, что, с целью повышения бь.стродействия, ь нем выходы формирователей весов дуг одного столбца соединены с входами одного изэлементов ИЛИ, число которых раьно числустолбцов, выход каждого элемента ИЛИ подключен к единичному входу соответствующего триг-.ера, единичный выход которого соединен с входом блока управления и с первым входом элемента И строки, номер которой соответствует номеру столбы. выход элемента И подключен к входам формирователей весов дуг этой же строки, вгорыо входы элементов И и один из входов каждого элем нта ИЛИ соединены с соответствуюшими выходами блока управления.2. Устройство по и. 1, о .: л и ч а 1 ош е е с я тем, что формирователь веса дуги содержит триггер, входы которого подключены к управляющим входам формирователя веса дугп, а выход - к одному из 1 ходов элемента И, второй вход которого соединен с входом формирователя веса дуги, вь - ход - подключен к входу счетчика, вь:ход которого соединен с выходом формирователя веса дуги.52595415 7 ЮСоставитель А. Жеренов Редактор Т, Иванова Техред А. Богдан Корректор Л. Боринская Заказ 5144/485 Тираж 864 Подписное ЦНИИПИ Государственного комитета Совета Министров СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская набд. 4/5филиал ППП фПатентф, г. Ужгород, ул. Проектная, 4