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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Рвслублнк

К АВТОРСКОМУ СВИ ЕТЕЛЬСТВУ (61) Дополнительное к авт, свид-ву (22) Заявлено 270779 (21) 2830339/18-24 (51)М. Кл. с присоединением заявки М (23) Приоритет

G 06 G 7/122

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

СССР но делам изобретений и открытий

Опубликовано 30,0681, Бюллетень 89 24 (53) УДК 681. 333,088.8) Дата опубликования описания 300681 (72) Авторы изобретения

-В.A. Титов, В.Л. Гайдуков, С.В. Назаров и В.A. Тафинцев (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙ1ЛЕГО

ПУТИ В ГРАФЕ

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

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

Известно устройство- для формирования кода кратчайшего пути в цифровой сети связи, содер><атее генератор, счетчик, три группы элеменiов И, элемент ИЛИ, узел опроса, . два регистра кода адреса, буферный и выходной регистры (1) .

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

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

ИЛИ, генератот> тактовых импульсов, выход которого подклпчен к входу блока управления j2) .

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

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

Указанная цель достигается тем, что в устройство для определения

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

«лодели графа первую группу триггеров, первые входы которых подключены к первому выходу блока управления, по числу столбцов матричной модели графа первую и вторую группы элементов И, входы счетчиков каждой строки «латричной «лодели графа соединены с выходогл элемента И первой группы одноименного столбца «латричной модели графа и подключены к соответствующему входу группы блока управления, введены по числу столбцов матричной модели графа группа элементов НЕ, третья и четвертая группы зле«лентов И, первая и вторая группы счетчиков, группа схем сравнения и вторая группа триггеров, счетные входы каждого из которых подключены графа зле«ленты ИЛИ 8, первая группа триггеров 9, группа элементов НЕ 10, вторая 11 и первая 12 группы элементов И, третья 13 и четвертая 14 группы элементов И, первая 15 и вторая 16 группы счетчиков, группа схем 17 сравнения и вторая группа

18 триггеров. к выходу соответству«>щей схемы сравнения группы, управляющий вход которой соединен.со вторым выходом бло-

Блок управления (фиг.2) содержит первый элемент И 19, блок 20 пуска и останова, второй элемент И- 21, счетчик 22 и дешифратор 23. Выход

24 дешифратора подключен к управляемы«л входам элементов 13, выход 25— к управляющим входам элементов 14

40 и первому входу блока 20, выход 26 к управляющим входам схем 17 сравнения, и второ«лу входу блока 20. Выход счетчика 22 подключен ко входу дешифратора 23, а вход — к выходу элемента И 21, управляющий вход которого подключен к выходу блока 20, а информационные входы 27 подключены к выходам элементов И 12. Выход ветствующих элементов И второй груп- 28 блока 20 подключен к установочным входам триггеров 9 первой группы, а третий выход — к управля>эдему входу элемента И 19, информационный вход 29 которого подключен к выходу генератора 3, а выход 30 — к информационным входа«л элементов И 11 и

12 групп.

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

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

На фиг.1 показано устройство для определения кратчайшего пути в графе, структурная схема; на фиг.2 блок управления, блок-схема.

Устройство содержит (фиг.1) матричную модель графа 1, блок 2 управ20 ления, генератор 3 тактовых импульсов, по числу строк и столбцов матричной модели графа формирователи 4 дуг, включающие триггеры 5 и счетчики 6, дифференцирующие цепочки 7, по числу столбцов матричной модели.триггера 9, выход триггера 9 подключен к входу элемента HE 10 и управg5 ляе«лому входу эле«лента И 12. Выход

842842

25 элемента HE 10 подключен к управля- ющему входу элемента И 11, а информационные входы злеглентов И 11 и 12 подключены к выходу 30 элемента И

19 блока .управления. Выход элемента

И 11 подключен к инфорглационным

5 входам элеглентов И 13 и 14, выходы которых подключены к счетным входам счетчиков 15 и 16 соответственно.

Выходы счетчиков 15 и 16 подключены ко входам схемы 17 сравнения, выход которой подключен к счетному вхо- ду триггеров 18. Выходы элементов И

12 подключены к входаи счетчиков б одноименной. строки матричной модели rpaAa и одноименным входаг1 27 элемента И 21 блока управления. 15

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

В исходном состоянии все триггеры 18, счетчики 15, 16 и 22 находятся в нулевом состоянии. Определение 2О вершин, образующих кратчайший путь осуществляется в трй этапа. Первоначально в модель 1 заносится информация о топологии моделирующего графа сети. При этом триггеры 5

Формирователей дуг 4, моделирующих ветви графа, устанавливаются в единичное состояние. Соответствующий формирователь 4 дуг определяется пересечением строки с номером, равным номерУ начального узла моделируемой ветви и столбца с номером, равным номеру ее конечного узла. В счетчики 6 соответствующих формирователей дуг 4 заносятся числа импульсов, дополнягщие длительность ветвей до полной емкости счетчиков. После занесения исходной информации блок пуска и останова 20 блока 2 устанавливает дополнительный триггер 9, в.единичное состояние, так как пер- 4Q вая вершина в сетевых графах — начальная вершина (или фиктивная вершина с нулевым временем работы).

Поэтому на выходе элемента 9, высокий потенциал. Это объясняется

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

10, НЕ нулевой потенциал и импульсы с выхода 30 блока 2 через элемент

И 11, не поступают на вход элементов И 13, и 14, . С выхода 24 дешифратора, 23 на все управляющие входы элемен тов И 13 подаются разрешающие сигналы, поэтому через все другие элементы И 13 на счетные входы счетчиков 15i (i 2,n) поступают импульсы. Такие же импульсы через элементы

И 12 поступают на счетчики б первой строки матричной модели сети. щ

Отсчитав число импульсов пропорционально весу моделируемой дуги счетчик б„. одного из формирователей переполняется и устанавливает соответствующий триггер 511 в еди- б5 ничное состояние и на вход элементов

ИЛИ 8; через дифференцирующую цепочку 7 поступает импульс, который

Й затем поступает на кодовый вход триггера 9, . Триггер 9 перебрасывается в единичное состояние и с его выхода высокий потенциал через элемент HE 10; закрывает поступление счетных импульсов на вход счетчика 15; через элемент И 13

Высокий пОтенциал с выхода триггера

9, обеспечивает также прохождение счетных импульсов через элемент

И 12„ на входы триггеров 5< формирователей i-ой строки матричной модели сети. Это свидетельствует о том, что один из весов дуг, входящих в узел, номер которого соответствует номеру столбца Формирователей, .объединенных элементом ИЛИ

8„ через дифференцирующие цепочки 7«, сформирован. При этом формируется разрешение поступления импульсов на входы счетчиков б;., моделирующих ветви графа, исходящие из сформированного узла.

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

При этом на информационных входах

27 элемента И 21 будут высокие потенциалы, поэтому импульс с выхода элемента И. 21 поступает на вход счетчика 22, на котором зафиксируется код 01, в результате возбуждается выход 25 дешифратора 23, поэтому разрешагэщий сигнал на управляемых входах элеглентов И 13 снимается и подавтся на, управляеглые входы элеглентов И 14. Одновременно блок 20 пуска и останова прекращает подачу разрешающего сигнала на элЕглент И 19, тем самым прекращается подача счетных импульсов с.генератора .3. Кроме этого блок 20 подает импульсы на нулевые входы триггеров 9, тем самым сниглаются с их выходов высокие потенциалы. Сумматорное число импульсов поступившее с выхода генератора импульсов 3 через элемент И 19 на счетчики 15 соотвествует, кратчайшим величинам пути для соответствующей вершины графа. На этом первый этап работы устройства заканчивается.

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

23 на все управляющие входы элемен842842 тов И 14 подаются разрешающие сигналы. С появлением пускового сигнала блок управления 2 разрешает прохождение импульсов е выхода генератора

3 на входы всех элементов И 11 и 12.

Вычислительный процесс продолжается далее аналогично цервому.этапу.

В результате на счетчиках 16 зафиксируются коды, соответствующие кратчайшим расстояниям для всех вершин нового графа, а на счетчике .22 код

10.

Третий этап работы устройства заключается в сравнении показаний счетчиков 15 и 16 путем подачи с выхода 26 дешифратора 23 управляпщего сигнала на схемы 17 сравнения.

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

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

Пусть задан граф G, описываемый матрицей смежности А и глатрицей

Т-длин дуг: .

О 1 1 1 О О О

О О О О 1 1 О

О О О О О 1 О

A = О О О О О 1 О

О О О О 0 0 1

О О О О О О 1

О О О О О О О оо 2 4 3 с < о 2 3

Т = о " " 5" о 6 ..г

o0 cr» оэ сю сю оо а где элементы

О, если нет дуги из i-ой вершины в j-ую, Ц 1, если есть дуга из i-ой вершины в j-ую, i,j 1,п;

t; ° — время длительности дуги из i-ой вершины в j-ую.

После занесения исходной информации на выходе триггера 9 первого . столбца будет высокий потенциал, поэтому через элемент И 124 проходят счетные импульсы от генератора 3 через элемент И 19 на входы счетчиков 6 первой строки матричной модели, а через элементы И 111 и 13j (j= 2ф7) - на счетчики 15). Через

2 т.е. с приходом второго импу

gg» льса переполняется счетчик 6 первой строки второго столбца, который перебрасывает соответствующий триггер 5«, с выхода дифференцирующей цепочки 7 сформированный им12 пульс через элемент ИЛИ 8г этого же

» столбца перебросит триггеР 9г в единичное состояние. Появление высокого потенциала на выходе триггера 9 второго столбца разрешает посЯ тупление импульсов на вход счетчиков

S 6 второй строки. Одновременно эле.мент НЕ 10 прекращает доступ счетных импульсов на счетчик 15 г показания которого в данный момент времени равны „ = 2.

Аналогично с приходом очередного импульса (t« = 3) иглпульсы генератора 3 будут поступать на счетчики четвертой строки," с приходом четвертого импульса (t„ = 4) — на счетчики третьей строки и пятой строки, так как t + t = 2 + 2 = 4; с приходом я 9б пятого импульса — счетчики шестой строки, так как „ + = 5. Наконец, с приходом седьглого импульса

+ t + с = 2 + 3 + 2 = 7, пояо6 %7

2() вится высокий потенциал на триггере 9 седьмого столбца; блок 20

1 прекращает подачу иглпульсов на входы элементов И 11 и 12 и сбрасывает триггеры 9 в нулевое состояние, 25 при этом суммарное число импульсов, поступившее с выхода генератора 3 через элемент И 19 на входы счетчиков 15 — 15, соответствуют величинам кратчайших путей в графе для каждой вершины графа сети. В результате на счетчиках 15 следующие значения: О, 2, 4, 3, 4, 5, 7.

Далее заносится информация о топологии графа в матрицу сети в инверсивногл порядке, т.е. проводится транспортирование матрицы A относительно главной диагонали, в результате получаем матрицу А:

О 1 1 О О О О

О О О 1 1 1 О

0000001

0000001

0000001

Аналогично получается матрица Т

После занесения информации А на выходе триггера 9, первого столбца будет высокий потенциал, поэтому через элемент И 12, проходят счетные импульсы от генератора 3 на входы счетчиков б первой строки матричной модели, а через элементы И 11J, 14J (j 2-;7) - на входы счетчиков 16j.

С приходом второго импульса переполняется счетчик 6,< и перебрасывает в нулевое состояние триггер 5, импульс с выхода триггера 5 через дифференцируищую цепочку 7« и элемент ИЛИ 8л перебрасывает триггер

9 в единичное состояние. На счетчи60 ке 16< зафиксируется код, равный 2.

Переходный процесс заканчивается, если на выходах всех триггеров 9 высокий потенциал. В результате на счетчиках 16 следующие эначения: О, 65 2, 6, 7, б, 5, 7, а н; счетчике 22

842842

10 код 10. Далее с выхода дешифратора

23 подается управляющий сигнал на схемы 17 сравнения. Сигналы сравнения с выхода схегл 17 сравнения перебрасывают триггеры 18 в единичное состояние. В данном случае триггеры

18„, 18 18 и 18»„ что соответствует вершинам, лежацим на кратчайшем пути графа сети.

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

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

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

ИЛИ соединены со вторыгли входами соответствующих триггеров первой группы, выходы которых подкгвэчены к первым входам соответствующих эле11 ментов И первой группы и ко входам соответствующих элементов НЕ группы, выходы, элементов НЕ группы соединены со вторыми входагли соответствугмцих элементов И второй

Щ группы, пятый выход блока управления подключен ко вторым входам элементов

И первой и второй группы, выходы элеглентов И второй группы соединены с информационными входами соответствугЖих элементов И третьей и четвертой группы.

2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что, блок управления содержит первый и второй

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

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР .9 547770, кл. G 06 F 15/20, 1976.

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

В 640314, кл. С 06 С 7/122, 1977 .(прототип).

842842

4 иг, f

27

Фиг. 2

Составитель И. Дубинина

Редактор A. Власенко техред Ж,Кастелеви ю Корректор С. Цомак

Заказ 5104/62 Тираж 745 Подписное

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

113035, Иосква, Ж-35 Раушская наб., д.4/5 филиал ППП "Патент", r.Óæãoðîä, ул.Проектная, 4