Устройство для определения крат-чАйшЕгО пуТи B гРАфЕ Советский патент 1981 года по МПК G06G7/122 

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙГ ГО ПУТИ В ГРАФЕ

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

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

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

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

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

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

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

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

5 образу1адих кратчайший путь и определения величин кратчайших путей для всех вершин графа.

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

0 кратчайшего пути в графе, содержа-щее блок управления, импульсный вход которого соединен с выходом генератора импульсов, по числу строк-и столбцов матричной модели графа цепочки из последовательно соединенных счетчика и триггера, выход ка-эдого столбца через соответствугадую дифференцируюliyio цепочку соединен с информационным входом соответствующего элемента ИЛИ, по числу столбцов матричной модели графа первую группу триггеро первые входы которых подключены к первому выходу блока управления, по числу столбцов матричной модели графа первую и вторую группы элемен тов И, входы счетчиков строки матричной модели графа соединены с выходом элемента И первой груп пы одноименного столбца матричной м дели графа и подключены к соответствующему входу Группы блока управления, введены по числу столбцов матричной модели графа группа элементов НЕ, третья и четвертая групп элементов И, первая и вторая группы счетчиков, группа схем сравнения и вторая группа триггеров, счетные входы казхдого из которых подключены к выходу соответству1Х1ей схемы срав нения группы, управляющий вход кото рой соединен, со вторым выходом бло ка управления, третий и четвертый выходы которого. подкл эчены к управляющим входам соответствугодих элементов И третьей и четвертой групп, выходы элементов И третьей и четвертой групп соединены соответственно со входами счетчиков первой и второй группы, выходы которых подключены к информационным входам соответству1а1их схем сравнения группы, выходы элементов ИЛИ соединены со вторыми входами соотвествующих триггеров первой группы, выходы которых подключены к первым входам соответствующих элементов И первой группы и ко входам соответствующих элементов НЕ группы, выходы элементов НЕ группы соединены со вторыгли входами соответствующих элементов И второй груп .пы, пятый выход блока управления подключен ко вторым входам элементов И первой и второй группы, выходы элементов И второй группы соединены с информационными входами соот ветствующих элементов И третьей и четвертой группы, а также тем, что ,блок управления содержит первый и второй элементы И, блок пуска и останова, счетчик и дешифратор, первый выход которого является четвертым выходом блока, третьим выходом которого является второй выход дешифратора, соединенный с первым входом блока пуска и останова, первый выход которого подключен к управляющего входу второго элемента И , выход которого через счетчик соединен со входом дешифратора, третий выход которого соединен со вторым входом блока пуска и останова и является вторым выходом блока второй выход блока пуска и останова подключен к первому входу первого элемента И, выход которого является пятым выходом блока, первым выходом которого является третий выход блока пуска и останова, второй вход первого элемента И является входом блока, информационные входы второго элемента И .являются группой входов блока. На фиг.1 показано устройство для определения кратчайшего пути в графе, структурная схема; на фиг.2 блок управления, блок-схема. Устройство содержит (фиг.1) матричную модель графа 1, блок 2 управления, генератор 3 тактовых импульсов, по числу строк и столбцов матричной модели графа формирователи 4 дуг, включающие триггеры 5 и счетчики б, дифференцируквдие цепочки 7, по числу столбцов матричной модели графа элементы ИЛИ 8, первая группа триггеров 9, группа элементов НЕ 10, вторая 11 и первая 12 группы элементов И, третья 13 и четвертая 14 группы элементов И, первая 15 и вторая 16 группы счетчиков, группа схем 17 сравнения и вторая группа 18 триггеров. Блок управления (фиг.2) содержит первый элемент И 19, блок 20 пуска и останова, второй элемент И 21, счетчик 22 и дешифратор 23. Выход 24 дешифратора подключен к управляемым входам элементов 13, выход 25 к управляга-дим входам элементов 14 и первому входу блока 20, выход 26 к управляющим входам схем .17 сравнения, и второму входу блока 20. Выход счетчика 22 подключен ко входу дешифратора 23, а вход - к выходу элемента И 21, управляющий вход которого подключен к выходу блока 20, а информационные входы 27 подключены к выходам элементов И 12. Выход 28 блока 20 подключен к установочным входам триггеров 9 первой группы, а третий выход - к управляющему входу элемента И 19, информационный вход 29 которого подключен к выходу генератора 3, а выход 30 - к информационным входам элементов И 11 и 12 групп. Модель i представляет собой матрицу однородных ячеек формирователей весов дуг с дифференцирующими цепочками размером п.чп, где п - максимальное число узлов моделируемого графа. Выход кагкдого элемента ИЛИ 8 соединен с кодовым входом триггера 9, выход триггера 9 подключен к входу элемента НЕ 10 и управляемому входу элемента И 12. Выход элемента НЕ 10 подключен к управляющему входу элемента И 11, а информационные входы элементов И 11 и 12 подключены к выходу 30 элемента И 19 блока управления. Выход элемента И 11 подключен к информационным входам элементов И 13 и 14, вых.оды которых подключены к счетным входам счетчиков 15 и 16 соответственно. Выходы счетчиков 15 и 16 подключены ко входам схемы 17 сравнения, выход которой подключен к счетному входу триггеров 18. Выходы элементов И 12 подключены к входам счетчиков б одноименноп.строки матричной модели графа и одноименным входат 27 элемента Н 21 блока управления. Устройство работает следующим обраэом. В исходном состоянии все триггеры 18, счетчики 15, 16 и 22 находят ся в нулевом состоянии. Определение вершин, образующих кратчайший путь осуществляется в три этапа. Первоначально в модель 1 заносится информация о топологии моделирующего графа сети. При этом триггеры 5 формирователей дуг 4, моделирующих ветви графа, устанавливаются в единичное состояние. Соответствующий формирователь 4 дуг определяется пересечением строки с номером, равным номеру начального узла моделируемой ветви и столбца с номером, равным номеру ее конечного узла. В счетчики 6 соответствующих формиров телей дуг 4 заносятся числа импульсов, дополня1Э1 1ие длительность ветве до полной емкости счетчиков. После занесения исходной информации блок пуска и останова 20 блока 2 устанавливает дополнительный триггер 9, в.единичное состояние, так как первая вершина в сетевых графах - начальная вершина (или Фиктивная вершина с нулевым временем работы). Поэтому на выходе элемента 9 высокий потенциал. Это объясняется тем, что в однонаправленном графе без циклов и петель начальные узлы не содержат входш-шх ветвей, следовательно, на выходе элемента 10, НЕ нулевой потенциал и импульсы с выхода 30 блока 2 через элемент И 11) не поступают на вход элементо И 13, и 14, . С выхода 24 дешифратор , 23 на все управлякяцие входы эламен тон И 13 подаются разрешающие сигналы, поэтому через все другие элементы И 13 на счетные входы счетчиков 15i (i 2,n) поступают импульсы. Такие же импульсы через элемент И 12 поступают на счетчики 6 первой строки матричной модели сети. Отсчитав число импульсов пропорционально весу моделируемой дуги счетчик 6,4 одного из формирователей переполняется и устанавливает соответствующий триггер в единичное состояние и на вход элементов ИЛИ 8; через дифференцирующую цепочку поступает импульс, который затем поступает на кодовый вход триггера 9i . Триггер 9 перебрасывается в единичное состояние и с его выхода выЬокий .нциал через элемент НЕ закрывает поступление счетных импульсов на вход счетчика 15; через элемент И 13|. Высокий потенциал с выхода триггера 9, обеспечивает также прохождение счетных импульсов через элемент И 12; на входы триггеров 5;,j формирователей i-ой строки матричной модели сети. Это свидетельствует о том, что один из весов дуг, входящих в узел, номер которого соответствует номеру столбца формирователей, .объединенных элементом ИЛИ 8v через дифференцируьэщие цепочки , сформирован. При этом формируется разрешение поступления импульсов на входы счетчиков 6-,j , моделирующих ветви графа, исходящие из сформированного узла. Вычислительный процесс продолжается до тех пор, пока на выходах всех триггеров 9 не будут присутствовать высокие потенциалы. Это свидетельствует о том, что все узлы исследуемого графа сформированы. При этом на информационных входах 27 элемента И 21 будут высокие потенциалы, поэтому импульс с выхода элемента И. 21 поступает на вход счетчика 22, на котором зафиксируется код 01, в результате возбуждается выход 25 дешифратора 23, поэтому разрешающий сигнал на управляемых входах элементов и 13 снимается и подается на. управляеглые входы элементов И 14. Одновременно блок 20 пуска и останова прекращаетподачу разрешающего сигнала на элемент И 19, тем самым прекра11ается подача счетных импульсов с. генератора -3. Кроме этого блок 20 подает импульсы на нулевые входы триггеров 9 тем самым снимаются с их выходов высокие потенциалы. Сумматорное число импульсов поступившее с выхода генератора импульсов 3 через элемент И 19 на счетчики 15 соотвествует, кратчайшим величинам- пути для соответствующей вершины графа. На этом первый Этап работы устройства заканчивается. На втором этапе осуществляется восстановление информации о топологии моделируемого гр,афа сети, при этом Исходный граф заносится в матричную -модель сети в инверсном порядке, т.е. матрица смех ности заносимого графа будет транспортирована относительно главной диагонали (см.пример). С выхода 25 дешифратора 23 на все управляющие входы элементов и 14 подаются разрешающие сигн лы., С появлением пускового сигнгша блок управления 2 разрешает прохож дение импульсов е выхода генератор 3 на входы всех элементов И 11 и 1 Вычислительный процесс продолжаетс далее аналогично цервому.этапу. В результате на счетчиках 16 зафик сируются коды, соответствующие кра чайьаим расстояниям для всех вершин нового графа, а на счетчике 22 код 10. Третий этап работы устройства заключается в сравнении показаний счетчиков 15 и 16 путем подачи с выхода 26 дешифратора 23 управляющего сигнала на схемы 17 сравнени С выхода схем 17 сигнал сравнения перебрасывает триггеры 18 в единич ное состояние. Единичные состояния триггеров 18 соответствуют вершина графа, образующих кратчайший путь. Работа устройства при определении вершин, образующих кратчайший путь к графе сети, поясняется на следующем примере. Пусть задан граф G, описываемый матрицей смежности А и матрицей Т-длин дуг: . 0111000 0000110 0000010 л 0000010; о о о о о .0 1 0000001 0000000 00 2 4 3 « со 00 со 00 2 300 00 00 4 ее г со 00 00 оО 00 О ао off 00 00 fo 00 6 QO fo f o o f 2 off o off- 3o ) где элементы О, если нет дуги из 1 -ой вершины в j-ую, i3 1, если есть дуга из i-о вершины в J-ую, i , J 1 . п; время длительности дуги из 1-ой вершины 8 j-ую. После занесения исходной информ ции на выходе триггера 9 первого столбца будет высокий потенциал, поэтому через элемент И 12 проходят счетные импульсы от генератора через элемент И 19 на входы счетчи ков 6 первой строки матричной модели, а через элементы И 11j и 13 () - на счетчики 15J. Через 2, т..е. с приходом второго им льса переполняется счетчик 6 первой строки второго столбца, которы перебрасывает соответствующий триггер , с выхода дифференциру щей цепочки 7(,j сформированный импульс; через элемент ИЛИ 8,j этого ж столбца перебросит триггер Эд, в единичное состояние. Появление высокого потенциала на выходе триггера 9 второго столбца разрешает поступление И1утульсов на вход счетчиков 6 второй строки. Одновременно элемент НЕ 10 прекращает доступ счетных импульсов на счетчик 15; | показания которого в данный момент времени равны t Аналогично с приходом очередного шлпульса ( 3) импульсы генератора 3 будут поступать на счетчики четвертой строки; с приходом четвёртого импульса (t,,, 4) - на счетчики третьей строки и пятой строки, так как t,j+ 2 + 2 4; с приходом пятого импульса - счетчики шестой 5. Накостроки, так как нец, с приходом седьмого импульса t, + tog + t,i7 2 + 3 + 2 7, появится высокий потенциал на триггере 9 седьмого столбца; блок 20 прекращает подачу импульсов на входы элементов И 11 и 12 и сбрасывает триггеры Э в нулевое состояние, при этом суммарное число импульсов, поступившее с выхода генератора 3 через элемент И 19 на входы счетчиков 15 - iSf , соответствуют величинам кратчайших путей в графе для Кс1ждоП вершины графа сети. В результате на счетчиках 15 следующие значения: О, 2, 4, 3, 4, 5, 7. Далее заносится информация о топологии графа в матрицу сети в инверсивном порядке, т.е. проводится транспортирование матрицы А относительно главной диагонали, в результате получаем матрицу А: 0110000 000111 000001 000000 000-000 000000 000 0000 Аналогично получается матрица Т . После занесения информации А на выходе триггера 9 первого столбца будет высокий потенциал, поэтому через элемент И 12 проходят счетные импульсы от генератора 3 на входы счетчиков 6 первой строки матричной Модели, а через элементы И llj, 14J (J 2-77) - на входы счетчиков 16j. С приходом второго импульса переполняется счетчик 6,2 и перебрасывает в нулевое состояние триггер 5(2 , импульс с выхода триггера Sjj через дифференцирующую цепочку 7 и элемент ИЛИ S,j перебрасывает триггер 9,; в единичное состояние. На счетчике 1бг2, зафиксируется код, равный 2. Переходный процесс заканчивается, если на выходах всех триггеров 9 высокий потенциал, в результате на счетчиках 16 следушще значения; О, 2; 6, 7, 6, 5, 7, а на счетчике 22 код 10. Далее с выхода дешифратора 23 подается управляющий сигнал на схемы 17 сравнения, С11гналы сравне ния с выхода схем 17 сравнения пере брасывают триггеры 18 в единичное состояние. В данном случае триггеры 18 ,. 18,, 18 и 18т г что соответств ет вершинам, лежащим на кратчайшем пути графа сети. Таким образом, устройство за сче введения дополнительных элементов с новыгли связями обеспе,чивает получение нового положительного эффекта, который заключается в том, что, кроме величины кратчайшего пути все го графа одновременно определяются кратчайшие-пути всего графа, одновременно определяются кратчайшие пути для всех вершин графа, а также вершины, образующие кратчайший путь в графе сети и повышает быстродейст вие известного устройства. Формула изобретения 1. Устройство для определения кратчайшего пути в графе, содержащее блок управления, импульсный вход которого соединен с выходом генератора импульсов, по числу стро и столбцов матричной модели графа цепочки из последовательно соединен ных счетчика и триггера, выход триг Ьера каждого столбца через соответствующую дифференцирующую цепочку соединен с информационным входом соответствующего элемента ИЛИ, по числу столбцов матричной модели графа первую группу триггеров пёрвые входы которых подключены к первому выходу блока управления, по числу столбцов матричной модели гра фа: первую и втору э группы элементов и, входы счетчиков кагадой строки матричной модели графа соединены с выходом элемента И первой группы одноименного столбца матричной ли графа и подключены к соответству щему входу группы, блока управления, отличаю щееся тем, что с целью повышения быстродействия, в него введены по числу столбцов матричной модели графа группа элементов НЕ, .третья и четвертая группы элементов И, первая и вторая группы счетчиков, группа схем сравнения и вторая группа триггеров, счетные входы ка кдого из которых подкшзчены к выходу соотбетствующей схемы сравнения группы, управля1си-дий вход которой соединен со вторым выходом блока управления, третий и четвертый выходы которого подключены к.управляющим входам соотвествующих элементов И тр етьей и четвертой групп, выходы элементов И третьей и четвертой соединены соответственно со входами счетчиков- первой и второй группы, выходы которых подключены к информационным входам соответствующих схем сравнения группы, выходы элементов ИЛИ соединены со вторы ли входагли соответству1сидих триггеров первой группы, выходы которых подключены к первым входам соответствуощих элементов И первой группы и ко входам соответствующих элементов НЕ группы, выходы,элементов-НЕ группы соединены со вторыми входами соответствугацих элементов И второй группы, пятый выход блока управления подключен ко вторым входам элементов И первой и второй группы, выходы элементов И второй группы соединены с инфо рмационными входами соответСТВУ1СЯЧИХ элементов И третьей и четвертой группы. 2.Устройство по П.1, отлич ающеес я тем, что, блок управления содержит первый и второй элементы И, блок пуска и останова, счетчик и дешифратор, первый выход которого является четвертым выходом блока, третьим выходом которого является второй выход дешифратора, соединенный с пepвы 4 входом блока пуска и останова, первый выход которого подключен к управляющему.входу второго элемента И, выход которого через счетчик соединен со входом дешифратора, третий выход которого сбединен со вторым входом блока пуска и останова и является вторым выходом блока, второй выход блока пуска и останова подключен к первому входу первого элемента И, выход которого является пятым выходом блока, первым выходом которого является третий выход блока пуска и останова, второй вход первого элемента И является входом блока, инфорг ационные входы второго элемента И являются группой входов блока. Источники информации, ринятие во внимание при экспертизе 1.Авторское свидетельство СССР 547770, кл. G 06 F 15/20, 1976. 2.Авторское свидетельство СССР 640314, кл. G 06 G 7/122, 1977 (прототип).