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

 

Союз Советских

Социалистических

Республик

ОПИСЛНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ay— (22) Заявлено 05.11.74 (21) 2072541/24 с присоединением заявки №вЂ” (23) Приоритет— (51) М. Кл.

G. 067 15/20

Государственный комитет

Совета Министров СССР по делан изобретений н открытий (43) Опубликовано25.08 76.Бюллетень №31 (53) УДК 681.333 (088.8) (45) Дата опубликования описания23.12.76 (72) Авторы изобретения

A. Г. Додонов, В. В. Хаджинов и В. М. Шишмарев

Институт электродинамики AH Укра (71) Заявитель скои

В<Ц +e Нф@ Я (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ

В ГРАФЕ

Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств.

Задача определения кратчайшего пути меж-а ду узлами в графе заключается в определении величины минимального из всевозможных путей, соединяющих эти узлы.

Известны устройства, позволяющие решить эту задачу моделированием веса каждой дугин графа формирователями весов дуг, основу которых составляют счетчики. Необходимойоперацией на таких устройствах является ручной набор топологии моделируемых сетей.

Известны устройства, содержащие по чис- !5 лу узлов графа формирователи в строках и столбцах матричной модели сети, блок управления и соединенный с ним генератор импульсов. Однако при помощи таких устройств не-. возможно определить величины кратчайших 20 путей в графе.

Известны также устройства, предназначенные для решения указанной задачи, в которых топология моделируемого графа формируется автоматически в процессе решения ° 25

Это устройство содержит формирователи весов дуг в строках и столбцах матричной модели сети, элементы И, ИЛИ, триггеры по числу узлов графа, блок управления, соединенный входом с выходом генератора импульсов.

Недостатком такого устройства является разделение во времени процесса формирования топологии графа и процесса формирования весов дуг, что снижает быстродействие устройства.

Цель изобретения — увеличение быстродействия устройства.

Для этого в предлагаемом устройстве выходы формирователей весов дуг одного столбца соединены с входами одного из элементов

ИЛИ, число которых равно числу столбцов, выход каждого элемента ИЛИ подключен к единичному входу соответствующего триггера, единичный выход которого соединен с входом блока управления и с первым входом элемента И строки, номер которой соответс вует номеру столбца, выход элемента И подключен к входам формирователеи весов дуг этой же строки, вторые входы элементов И

525954 и один нз входов каждого элемента ИЛИ соединены с соответствующими выходами блока управления.

Кроме того, формирователь веса дуги содержит триггер, входь! которого подключены к управпя!ощим входам формирователя веса дуги, а выход — к одному из входов элемента И, второй вход которого соединен с

«ходом формирователя веса дуги, выход подкл.очен к входу счетчика, вь ход которого со-10 единен с выходом формирователя веса дуги.

Иа фиг. 1 представлена блок-схема пред— лагаемого устройства на фиг. 2 — блок-схема формирователя весов дуг (ФВД).

Устройство содержит модель сети 1 (МС), блок 2 управпен!!я, генератор импульсов 3, форм:!роеатеГ!!! весов ду- (ФВД) 4

1, 1

4 4 элемсцты ИЛИ 5 5 ... 5 П триггеры 6

1 2, 1

6,..... 6 элементы И 7, 7 ..., 7 ° 8

vý

Э I y

9,10,3 1 -11 полюсы модели. й.>

Модес!ь сети представляет собой матрицу 25 одно !однь!х ячеек формирователей весов дуг размером ц! х А, где П. — максимальное число узлов моделируемого графа.

Выходы формирователей весов дуг, распо,.!"»кс нных B одном столбце МС подключены 30 к входам одного из многовходовых элементо а . ЛИ 5, 5,,..., 5, вь ход которого

2 " п, с::.,! !пеп с ед!!яичным входом соответствуюь! ;:! о триггера 6, 6 ..., 6 1 . диничный выход триггера 6 первого З5 стог:.бпа МС соединен с элементом И 7

»:-»!ход которого подключен к входам формирователей весов дуг первой строки МС. Единична!й вь!ход триггера 6 второго столбца

МС соединен с элементом И 7, выход ко- 40 торого подключен K входам формирователей весов дуг второй строки МС и т.д. Выходы триггеров 6, 6 ..., 6, кроме того, соединены с блоком управления. ДополнительPxol b! схем ИЛИ,> 1, 52... 5 и BTGГ45 рь!е входы схем И 71, 72..., 7!.! LIogKJI!o чены соответственно к блоку управления.

Формирователь весов дуг (см. фиг, 2) содеожит счетчик 12, элемент И 13, триггер 14.

Вход ФВД является входом элемента И 13, второй вход этого элемента И соединен с единичным выходом триггера 14, входы которого соединены с по1!юсами установки топологии и подключены полюсами 15 и 16 к блоку управления (на фиг. 1 эти полюса и связи не указаны). Выход элемента И 13 подключен к входу счетчика 12, выход которого явт!яется выходом ФВД.

Устройство работает следующим образом.

Первоначально в МС заносится информация о топологии моделируемого графа и весах дуг, При этом один из триггеров 6

6„..., 6, соответствующий начальному уз2, лу, через один из полюсов 11 11

1 2 "

1 1 МС сигналом из блока 2 управления устанавливается в единичное состояние. Соответствующая ячейка ФВД определяется пересечением строки МС с номером, равным номеру начального узла моделируемой ветки, и столбца МС и номером, равным номеру ее конечного узла.

Триггеры 14 ФВД, которые не участвуют в формировании топологии моделируемого графа, блокируются сигналом из блока управления на полюсе 15, который устанавливает триггер в нулевое состояние.

Триггеры 14 ФВД, моделирующих ветви графа, устанавливаются в едини ное состояние сигналом из блока управления, поступающим на полюс 16.

В счетчики 12 соответствующих ФВД заносится количество импульсов, дополняющее длительности ветвей до полной емкости счетчиков.

С появлением пускового сигнала блок 2 управления разрешает прохождение импульсов генератора 3 с полюса 10 на полюс 9, на входы всех элементов И 7 ... 7 моде1 t ли сети 1. !

Пройдя через тот элемент И,на другом входе которого присутствует разрешение с одного из триггеров 6, 6,..., 6 столб1 2 "" Г1 ца, моделирующего начальный узел, эти импульсы поступают на входы ФВД строки, одноименной данному столбцу. При этом импульсы будут проходить на входы тех ФВД, которые моделируют веса дуг, исходящих из начапьных узлов. Отсчитав количество импульсов, пропорциональное весу моделируемой дуги, счетчик 12 ячейки ФВД, имеющий минимальный вес, переполнится. Импульс переполнения,пройдя через. соответствующий элемент ИЛИ (5, 5,..., 5 ) устанавливает в единичное состояние триггер (6 6

1 2

6 „ ) столбца МС, в котором находитсяэта ячейка ФВД. Сигнал этого триггера поступает на соответствующий элемент И (7, 7

1 2.

7„) и разрешает прохождение импульсов на

ФВД строки, одноименной данному столбцу. . Счетчик 12 ФВД, имеющий наименьший вес в этой строке, своим импульсом переполнения через соответствующий элемент ИЛИ устанавливает в единичное состояние триггер столбца МС, в котором находится данный

ФВД.

525954

Вычислительный процесс продолжается до тех пор, пока на всех полюсах 8, 8

8„не появятся высокие потенциалы, Это свидетельствует о том, что все узлы исследуемого графа сформированы. Блок 2 управления при этом прекращает подачу импульсов на полюс 9.

Суммарное количество импульсов, поступившее на полюс 9, будет равно кратчайшему пути графа. 1О

Формула изобретения

1. Устройство для определения кратчай- )5 щего пути в графе, содержащее формирователи весов дуг в строках и столбцах матричной модели сети, элементы И, ИЛИ, триггеры по числу узлов графа, блок управления, соединенный входом с выходом генерато- 20 ра импульсов, отличающееся тем, что, с целью повышения бь.стродействия, ь нем выходы формирователей весов дуг одного столбца соединены с входами одно" î,из элементов ИЛИ, число которых раьно числу столбцов, выход каждого элемента ИЛИ подключен к единичному входу соответствующего триг-ера, единичный выход которого соединен с входом блока управления и с первым входом элемента И строки, номер которой соответствует номеру столбы. выход элемента И подключен к входам формирователей весов дуг этой же строки, вгорыо входы элементов И и один из входов каждого элем нта ИЛИ соединены с соответствуюшими выходами блока управления.

2. Устройство по и. 1, о = л и ч à 10ш e e с я ч ем, что формирователь вес - д ги содержит триггер, входы которого подключены к управ-,яюшим входам формирователя веса дугп, а выход — к одному из 1ходов элемента И, второй вход которого соединен с входом формирователя веса дуги, в ход — подключен к входу счетчика, вь:ход которого соединен с выходом формирователя веса дуги.

525954

75 16

Составитель А. Жеренов

Редактор Т. Иванова Техред А. Богдан Корректор Л. Боринская

Заказ 5144/485 Тираж 864 Подписное

БНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб„д. 4/5

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4