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

 

Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов. Изобретение позволяет расширить функциональные возможности устройства за счет идентификации дуг кратчайшего пути и установления , является ли этот путь единственным . Устройство содержит группу элементов И, генератор импульсов, группу злементов ИЛИ, матрицу моделей дуг, модель дуги, вход запуска устройства , первый коммутатор, счетчик, ключ, вторую-группу злементов ИЛИ, дешифратор, второй коммутатор. Модель дуги каждого столбца, кроме пйследнего, матрицы моделей дуг содержит ключ, счетчик, элемент И, триггер, входные и выходные полюса. В моделях дуги последнего столбца матрицы от- .сутствует ключ. Матрица имеет размерность п X п. 1 ил. i W

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)4 С 06 F 15 20

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

„",,„, 1, ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А BTOPCHOMY СВИДЕТЕЛЬСТВУ можности устройства эа счет идентификации дуг кратчайшего пути и установления, является ли этот путь единственным. Устройство содержит группу элементов И, генератор импульсов, группу элементов ИЛИ, матрицу моделей дуг, модель дуги, вход запуска устройства, первый коммутатор, счетчик, ключ, вторую .группу элементов ИЛИ, дешифратор, второй коммутатор. Модель дуги каждого столбца, кроме пбследнего, матрицы моделей дуг содержит ключ, счетчик, элемент И, триггер, входные и выходные полюса. В моделях дуги последнего столбца матрицы от-.сутствует ключ. Матрица имеет размер- ф ность и х и. 1 ил. (57) Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графов. Изобретение позволяет расширить функциональные воз(21) 3843?35/24-24 (22) 15 ° 01.85 (46) 30. 08.86. Бюл. 9 32 (72) Г.С. Колесник (53) 681.333(088.8) (56} Авторское свидетельство СССР

& 640314, кл. С 06 С 7/122, 1977.

Авторское свидетельство СССР

N"- 525954, кл. G 06 F 15/20, 1974. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

КРАТЧАЙШЕГО ПУТИ ГРАФА

„„SU „„1254502 A 1

254502 2

SQ

1 1

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

На чертеже представлена функциональная схема устройства для определения кратчайшего пути графа °

Устройство содержит группу 1 элементов И, генератор 2 импульсов, первую группу 3 элементов ИЛИ, матрицу

4 моделей дуг, модели дуг 5, вход за.пуска устройства 6, первый коммутатор

7, счетчик 8, ключ 9, вторую группу

10 элементов ИЛИ, дешифратор 11, второй коммутатор 12. В состав каждой модели дуги 5 кроме моцелей дуг- последнего столбца матрицы 4 моделей дуг, входят кгноч 13, счетчик 14, элемент И 15, триггер 16, входные и выходные полюса 17-22. В моделях дуг последнего столбца матрицы 4 моделей дуг ключи 13 отсутствуют. Иатрица 4 имеет размерность.

Устройство для определения кратчайшего пути графа работает следующим образом.

Перед началом работы в счетчик 8 заносят количество импульсов, дополняющее число и до полной емкости счетчика (и — число вершин графа}. С выхода счетчика 8 на управляющий вход ключа 9 и управляющий вход второго коммутатора 12 поступает нулевой потенциал, поэтому сигналы на выходах коммутатора отсутствуют. В матрицу 4 моделей дуг заносится информация о топологии исследуемого графа путем подачи единичных сигналов на установочные входы устройства 20 согласно матрице смежности. Соответствующие триггеры 16 переходят в единичное состояние, единичный потенциал с их выходов поступает на первые входы элементов И 15. В счетчики 14 заносят количество импульсов, дополняющее веса дуг до полной емкости счетчиков. На управляющие входы ключей 13 поступает нулевой потенциал, поэтому ключи 13 закрыты, С выходов счетчиков 14 IR входы элементов NJIH

3 и далее на вторые входы элементов

И 1 подается нулевой потенциал, поэтому элементы И 1 не пропускают на выход импульсы, поступающие на их первый вход. На управляющий вход первого коммутатора с выхода элемента ИЛИ 3 поступает нулевой потенциал, поэтому информационный вход первого коммутатора 7 скоммутирован на

его первый выход.

При поступлении запускающего импульса импульсы с выхода генератора

1ð 2 через информационный вход и первый выход первого коммутатора 7 поступают, во-первых, на первые входы элементов И 1, но на их выходы не проходят ввиду нулевого потенциала на вторых входах элементов И 1; во-вторых, через полюса 22 моделей ветвей

5 первой строки матрицы 4 моделей дуг — »a вторые входы элементов И 15 и далее через выходы этих элементов о на входы счетчиков 14 моделей дуг, инцидентных первой (начальной) вершине графа. Счетчики 14 ведут счет импульсов ° При переполнении счетчика

14 модели дуги наименьшего веса по

2 сравнению с остальными дугами, инцидентными первой вершине, íà его выходе появляется сигнал, который поступает, через полюс 18 и элемент

ИЛИ 3 на нулевые входы триггеров

16 одноименного данному счетчику 14 столбца матрицы моделей дуг 4 (через полюс 19). Триггеры 16 этого столбца переходят в нулевое состояние и уже до конца работы устройства запрещают прохождение импульсов с вторых входов элементов И 15 на их выходы.

Единичный потенциал переполнившегося счетчика 13 поступает на инфориационный вход закрытого ключа 13 этой же модели дуги. Единичный потенциал с выхода переполнившегося счетчика 14 через элемент ИЛИ 3 поступает на одноименный элемент И 1, на его второй вход. Поэтому импульсы генератора 2 начинают проходить с выхода этого элемента И 1 через полюса 22 на вторые входы элементов

И 15 той строки матрицы 4, которая одноименна элементу И 1. Счет ведут счетчики 14 этой строки матрицы. Далее устройство работает аналогично до того момепта, когда.в какой-либо строке матрицы 4 первым переполнит.ся счетчик 14 модели дуги последнего, и-го столбца матрицы 4, При этом единичный потенциал пере . полнившегося счетчика 14 через элемент ИЛИ 3 поступает на управляющий вход первого коммутатора 7,который

3 1254 подключает свой информационный вход к второму выходу. Непосредственно с выхода этого счетчика 14 через полюс

М единичный потенциал поступает на соответствующий выход устройства из числа и-й группы его выходов, идентифицируя тем самым дугу, вошедшую в кратчайший путь из множества дуг, инцидентных последней (конечной) вершине. Наконец, единичный потенциал поступает на соответствующий вход из числа и-й группы входов второго коммутатора 12., а также на один из входов элемента ИЛИ 10, одноименного номеру строки, в которой находится переполнившийся счетчик 14. С выхода элемента ИЛИ 10 единичный потенциал через полюса 21 поступает на управляющие входы ключей 13 одноименного столбца матрицы 4 и открывает их.Поэтому единичный потенциал с выхода счетчика 14, который переполнился в данном столбце матрицы 4, через полюс

17 поступает, во-первых, на один из выходов соответствующей группы выходов устройства, идентифицируя тем самым еще одну дугу кратчайшего пути; во-вторых, на один из входов соответствующей группы входов второго коммутатора 12 в-третьих на один из вхоУ У

30 дов того элемента ИЛИ 10, который одноименен номеру строки с переполнив. шимся счетчиком 14. Далее аналогично идентифицируются все дуги кратчайшего пути по единичным потенциалам на соответствующих выходах устройства.

Импульсы генератора 2 с второго выхода первого коммутатора 7 поступают, во-первых, на вход счетчика 8, которык начинает счет импульсов; вовторых, через открытый ключ 9 — на управляющий вход второго коммутатора 12, который с поступлением каждого импульса подключает к группе своих выходов вторую, третью и т.д. группы

I своих входов. Если на входах дешифратора 11 единичные потенциалы отсутствуют или присутствует единичный потенциал только на одном входе, то на выходе дешифратора 11 присутствует нулевой потенциал, если же единичный о потенциал присутствует хотя бы на двух входах, на выходе дешифратора

11 появляется сигнал. После отсчета и-го импульса счетчик 8 переполняется и выдает единичный потенциал, во- 55 первых, на выход окончания работы устройства; во-вторых,. на управляющий вход ключа 9, закрывая его.Сум502 4 марный вес кратчайшего пути находят (вне рамок устройства) путем суммирования веса входящих в него дуг.

Условием правильного нахождения единственного кратчайшего пути является непоступление сигнала на второй выход устройства с выхода дешифратора 10, формула изобретения.

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

ИЛИ первой группы (где Ц=1,2,...,n), выходам элементов И (i+1) — é строки матрицы моделей дуг, входы установки в "1" триггеров являются установочными входами устройства, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения количества дуг, принадлежащих кратчайшему пути, в него введены ключ, счетчик, вторая группа элементов ИЛИ, первый и второй коммутаторы, дешифратор, в модели дуг всех столбцов, кроме последнего, матрицы моделей. дуг введены ключи, причем информационный входключа каж,дой модели дуги подключен к выходу переполнения счетчика этой же модели дуги, управляющие входы ключей моделей дуг каждого столбца, кроме последнего, матрицы моделей дуг объединены и подключены к выходу одноименного элемента ИЛИ второй группы, выходы ключей моделей дуг каждого

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

1254502

Составитель Т. Сапунова

Редактор И. Касарда Техред И.Попович Корректор С. Черни

Заказ 4723/54 Тираж 671 Подписное

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

1 f3035, Иосква, R-35, Раушская наб., д. 4 5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

5 вход которого подключен к выходу п-ro элемента ИЛИ первой группы,первый выход первого коммутатора соединен с вторыми входами элементов И моделей дуг первой строки матрицы и с первыми входами всех элементов И группы, вторые входы которых подключены к входам одноименных элементов .ИЛИ первой группы, входы установки в "О" i-x триггеров каждого j-го

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

z-ro элемента ИЛИ второй группы и является i-м выходом группы выходов идентиФикации п-й дуги, вошедшей в кратчайший путь, вход генератора импульсов является входом запуска устройства,