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

Сефз Советских Социалистнческик РеслублнкОПИСАНИЕИ.ЗОБРЕТЕНИЯК АВТОРСКОМУ СВИ ЕТЕЛЬСТВУ о 1 842842(23) Приоритет 6 06 6 7/122 Государственный комитет СССР ио делам изобретеиий и открытийДата опубликования описания 300681(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙ 13 ЕГО ПУТИ В ГРАФЕ Изобретение относится к вычислительной технике и может быть использовано при исследовании параметров сетевых графиков.Задача определения кратчайшего пути в графе заклвчается в идентиФикации вершин,. составляющих кратчайший путь, а также в определении значения критического минимального времени для каждой вершины графав том числе и. всего графа в целом.Известно устройство. для формирования кода кратчайшего пути в цифровой сети связи, содерхатее генератор, счетчик, три группы элементов И, элемент ИЛИ, узел опроса два регистра кода адреса, буферный и выходной регистры 11 .Указанное устройство обладает ограниченными Функциональными возможностями, обеспечивает только определение величины кратчайшего пути графа.Наиболее близким техническим решением к предлагаемому иэобретени.о является устройство для определения кратчайшего пути, содержацее мат. - рицу Формирователей весов дуг, каждый иэ которых содерхит триггер и счетчик, выход которого подключен ко входу триггера, выход триггерака:хдого стслбца матрицы.формирователей весов дуг через диФФеренцирувшун цепочку"соединен с информационным входом соответствующего элементаИЛИ, генератор тактовых импульсов,выход которого подклпчен к входублока управления 2 .Недостатком известного устройства является невозможность определения вершин, образувдих кратчайший путь в графе, Необходимость ватом возникает, йапример, при решении задач планирования выполнения некоторого множества работ, представленных сетевым графиком.В этом случаевозникает необходимость определениявершин графа сети, образущих кратчайший путь, а также величин крат 20 чайших путей для всех вершин графа.Цель изобретения - повышениебыстродействия и расширение Функциональных воэмохностей устройства засчет идентификации вершин графа,образующих кратчайший путь и определенна величин кратчайших пу 1 ейдля всех вершин графа,Указанная цель достигается тем,что в устройство для определения30 кратчайшего пути в графе, содержа842842 та И , выход которого через счетчиксоединен со входол дешифратора,третий выход которого соединен совторым входил блока пуска и остащее блок управления, импульсныйвход которого соединен с выходомгенератора импульсов, по числустрок и столбцов матричной моделиграфа цепочки из последовательносоединенных счетчика и триггера,выход триггера каждого столбца через соответствующую дифференцируюцую цепочку соедйнен с информационным входом соответствующего элемента ИЛИ, по числу столбцов матричной нова и является вторым выходом блока модели графа первую группу триггеров,первые входы которых подключенык первому выходу блока управления,по числу столбцов матричной моделиграфа первую и вторую группы элементов И, входы счетчиков каждой строки матричной модели графа соединены с выходом элемента И первой группы одноименного столбца матричной модели графа и подключены к соответствующему входу группы блока управления, введены по числу столбцовматричной модели графа группа элементов НЕ, третья и четвертая группы элементов И, первая и вторая группы счетчиков, группа схем сравненияи вторая группа триггеров, счетныевходы каждого из которых подключены графа злеленты ИЛИ 8, первая группатриггеров 9, группа элементов НЕ 10,вторая 11 и первая 12 группы элементов И, третья 13 и четвертая 14группы элементов И, первая 15 ивторая 16 группы счетчиков, группасхем 17 сравнения и вторая группа18 триггеров. к выходу соответствупцей схемы сравнения группы, управляющий вход которой соединен.со вторым выходом блоБлок управления (Фиг.2) содержит первый элемент И 19, блок 20 пускаи останова, второй элемент И,счетчик 22 и дешифратор 23. Выход 24 дешифратора подключен к управляемыи входам элементов 13, выход 25 - к управляющим входам элементов 1440 и первому входу блока 20, выход 26 к управляющим входам схем 17 сравнения, и второму входу блока 20. Выход счетчика 22 подключен ко входу дешифратора 23, а вход - к выходу 45 элемента И 21, управляющий вход которого подключен к выходу блока 20, а информационные входы 27 подключены к выходам элементов И 12. Выход ветствующих элементов И второй груп блока 20 подключен к установочным входам триггеров 9 первой группы,а третий выход - к управляющемувходу элемента И 19, информационныйвход 29 которого подключен к выходу генератора 3, а выход 30 - к информационным входам элементов И 11 и 12 групп.Иодель 1 представляет собой матрицу однородных ячеек Формирователей весов дуг с дифференцирующими цепочками размером о,п, где и - мак 40 симальное число узлов моделируемого графа. Выход каждого элемента ИЛИ 8 соединен с кодовым входом ка управления, третий и четвертыйвыходы которого, подключены к управляпцим входам соответствующихэлелентов И третьей и четвертойгрупп, выходы элементов И третьейи четвертой групп соединены соответственно со входами счетчиковпервой и второй группы, выходы которых подключены к информационнымвходам соответствующих схем сравнения группы, выходы элементов ИЛИсоединены со вторыми входами соотвествуюцих триггеров первой группы, выходы которых подключеныкпервым входам соответствующих элементов И первой группы и ко входамсоответствупцих элементов НЕ группы, выходы элементов НЕ группысоединены со вторыми входами соот.пы, пятый выход блока управленияподключен ко вторым входам элементов И первой и второй группы, выходы элементов И второй группы соединены с информационными входами соот.ветствуюцих элементов И третьей ичетвертой группы, а также тем, чтоблок управления содержит первый ивторой элементы И, блок пуска и останова, счетчик и дешифратор, первый выход которого является четвертым выходом блока, третьим выходом которого является второй выход дешифратора, соединенный с первьпл входом блока пуска и останова,первый выход которого подключен куправляющему входу второго элеменвторой выход блока пуска и остановаподключен к первому входу первогоэлемента И, выход которого являетсяпятым выходом блока, первым выходом.которого является третий выходблока пуска и останова, второй входпервого элемента И является входомблока, информационные входы второгоэлемента И являются группой входовблока.На Фиг.1 показано устройство дляопределения кратчайшего пути в граФе, структурная схема; на фиг.2блок управления, блок-схема.Устройство содержит (Фиг.1) матричную модель графа 1, блок 2 управ ления, генератор 3 тактовых импульсов, по числу строк и столбцов матричной модели графа Формирователи 4дуг, включающие триггеры 5 и счетчики 6, дифференцирующие цепочки 7,по числу столбцов матричной модели.триггера 9, выход триггера 9 подключен к входу элемента НЕ 10 и управ ляеюлому входу элемента И 12. Выходэлемента НЕ 10 подключен к управля-ющему входу элемента И 11, а информационные входы элементов И 11 и 12подключены к выходу 30 элемента И19 блока .управления, Выход элементаИ 11 подключен к инфорглационным5входам элеглентов И 13 и 14, выходыкоторых подключены к счетным входамсчетчиков 15 и 16 соответственно.Выходы счетчиков 15 и 16 подключеныко входам схемы 17 сравнения, выходкоторой подключен к счетному вхо-ду триггеров 18. Выходы элементов И12 подключены к входагл счетчиков бодноименной. строки матричной модели графа и одноименным входа:1 27элемента И 21 блока управления. 15Устройство работает следующимобразом.В исходном состоянии все триггеры 18, счетчики 15, 16 и 22 находятся в нулевом состоянии. Определение Щвершин, образующих кратчайший путьосуществляется в трй этапа. Первоначально в модель 1 заносится информация о топологии моделирующегограФа сети. При этом триггеры 525формирователей дуг 4, моделирующихветви графа, устанавливаются в единичное состояние. Соответствующийформирователь 4 дуг определяетсяпересечением строки с номером, равным номерУ начального узла моделируемой ветви и столбца с номером,равным номеру ее конечного узла. Всчетчики 6 соответствующих формирователей дуг 4 заносятся числа импульсов, дополнягщие длительность ветвей З 5до полной емкости счетчиков. Послезанесения исходной информации блокпуска и останова 20 блока 2 устанавливает дополнительный триггер 9,в,единичное состояние, так как первая вершина в сетевых графах - начальная вершина (или фиктивнаявершина с нулевым временем работы).Поэтому на выходе элемента 9, высокий потенциал. Это объясняется45тем, что в однонаправленном графебез циклов и петель начальные узлы не содержат входящих ветвей,следовательно, на выходе элемента10, НЕ нулевой потенциал и импульсыс выхода 30 блока 2 через элементИ 11, не поступают на вход элементовИ 13, и 14, . С выхода 24 дешифратора, 23 на все управляющие входы элементов И 13 подаются разрешающие сиг-налы, поэтому через все другие элементы И 13 на счетные входы счетчиков 15 (2,п) поступают импульсы. Такие же импульсы через элементыИ 12 поступают на счетчики б первой строки матричной модели сети. ггОтсчитав число импульсов пропор"ционально весу моделируемой дугисчетчик б одного из формирователей переполняется и устанавливаетсоответствующий триггер 51 в еди ничное состояние и на вход элементовИЛИ 8; через дифференцирующую цепочку 7 поступает импульс, который1затем поступает на кодовый входтриггера 9, . Триггер 9 перебрасывается в единичное состояние и сего выхода высокий потенциал черезэлемент НЕ 10; закрывает поступление счетных импульсов на входсчетчика 15; через элемент И 13Высокий пОтенциал с выхода триггера9 обеспечивает также прохождениесчетнггх импульсов через элементИ 12 на входы триггеров 5 формирователей -ой строки матричноймодели сети. Это свидетельствуето том, что один из весов дуг, входящих в узел, номер которого соответствует ноглеру столбца формирователей, .объединенных элементом ИЛИ8 через дифференцирующие цепочки 7,сформирован. При этом Формируется разрешение поступления импульсовна входы счетчиков б; , моделирующих ветви графа, исходящие из сформированного узла.Вычислительный процесс продолжается до тех пор, пока на выходахвсех триггеров 9 не будут присутствовать высокие потенциалы. Это свидетельствует о том, что все узлы исследуемого графа сформированы,При этом на информационных входах27 элемента И 21 будут высокиепотенциалы, поэтому импульс с выхода элемента И 21 поступает навход счетчика 22, на котором зафиксируется код 01, в результате возбуждается выход 25 дешифратора 23,поэтому разрешагщий сигнал на управляемых входах элеглентов И 13снимается и подавтся на, управляеглые входы элементов И 14, Одновременно блок 20 пуска и остановапрекращает подачу разрешающегосигнала на элЕглент И 19, тем самымпрекращается подача счетных импульсов с.генератора 3. Кроме этогоблок 20 подает импульсы на нулевыевходы триггеров 9, тем самым сниглаются с их выходов высокие потенциалы. Сумматорное число импульсовпоступившее с выхода генератораимпульсов 3 через элемент И 19 насчетчики 15 соотвествует, кратчайшим величинам пути для соответствующей вершины графа. На этом первыйэтап работы устройства заканчивается.На втором этапе осуществляетсявосстановление информации о топологии моделируемого графа сети, приэтом исходный граф заносится в матричную модель сети в инверсном порядке, т.е. матрица смежности заносимого графа будет транспортированаотносительно главной диагонали(см.пример). С выхода 25 дешифратора23 на все управляющие входы элементов И 14 подаются разрешающие сигналы. С появлением пускового сигнала блок управления 2 разрешает прохождение импульсов е выхода генератора 3 на входы всех элементов И 11 и 12. Вычислительный процесс продолжается далее аналогично цервому.этапу.В результате на счетчиках 16 зафиксируются коды, соответствующие кратчайшим расстояниям для всех вершин нового графа, а на счетчике .22 код 10.Третий этап работы устройства заключается в сравнении показаний счетчиков 15 и 16 путем подачи с выхода 26 дешифратора 23 управляпщего сигнала на схемы 17 сравнения. С выхода схем 17 сигнал сравнения перебрасывает триггеры 18 в единичное состояние. Единичные состояния триггеров 18 соответствуют вершинам графа, образующих кратчайший путь.Работа устройства при определении вершин, образующих кратчайший путь к графе сети, поясняется на следующем примере.Пусть задан граф О, описываемый матрицей смежности А и глатрицей Т-длин дуг:,О 1 1 1 О О ОО О О О 1 1 ОО О О О О 1 ОА = О О О О О 1 О00000,0100000010 000000 2 4 3 оо оо ооо оо оо оо 2 Зооооо оо д оо 4 ооТ = оо оо оо оооо 5 фоо оо о о ооообоооо оо" 2ОО оа оэ ао сооо аогде элементыО, если нет дуги из -ойвершины в -ую,Ц 1, если есть дуга из 1-ойвершины в 1-ую,1,) 1,п;время длительности дуги из 1-ой вершины в -ую.После занесения исходной информации на выходе триггера 9 первого . столбца будет высокий потенциал, поэтому через элемент И 12 проходят счетные импульсы от генератора 3 через элемент И 19 на входы счетчиков б первой строки матричной модели, а через элементы И 111 и 131 =2 ф 7) - на счетчики 15). Через2 т.е. с приходом второго импу ф эльса переполняется счетчик б первой строки второго столбца, который перебрасывает соответствующий триггер 5, с выхода дифференцирующей цепочки 7 сформированный имЮпульс через элемент ИЛИ 8 этого же столбца перебросит триггеР 9 г вединичное состояние. Появление высокого потенциала на выходе триггера 9 второго столбца разрешает посЯтупление импульсов на вход счетчиков5 6 второй строки. Одновременно эле.мент НЕ 10 прекращает доступ счетных импульсов на счетчик 15 г показания которого в данный момент времени равны с = 2,Аналогично с приходом очередного импульса (сл = 3) иглпульсы генератора 3 будут поступать на счетчикичетвертой строки," с приходом четвертого импульса (с = 1) - на счетчикитретьей строки и пятой строки, так15 как с + .с = 2 + 2 = 4; с приходомЯ1 бпятого импульса - счетчики шестойстроки, так как с + с = 5. Наконец, с приходом седьглого импульса+ с+ с = 2 + 3 + 2 = 7, пояс 6 й 720 вится высокий потенциал на триггере 9 седьмого столбца; блок 20прекращает подачу иглпульсов на входы элементов И 11 и 12 и сбрасывает триггеры 9 в нулевое состояние,при этом суммарное число импульсов,поступившее с выхода генератора 3через элемент И 19 на входы счетчиков 15 л - 15, соответствуютвеличинам кратчайших путей в графедля каждой вершины графа сети. Врезультате на счетчиках 15 следующиезначения: О, 2, 4, 3, 4, 5, 7.Далее заносится информация о топологии графа в матрицу сети в инверсивном порядке, т.е. проводитсятранспортирование матрицы А относительно главной диагонали, в результате получаем матрицу А:О 1 1 О О О ОО О О 1 1 1 О40 00000100000001000000100000010000000Аналогично получается матрица Т451После занесения информации Ана выходе триггера 9, первого столбца будет высокий потенциал, поэтомучерез элемент И 12, проходят счетныеимпульсы от генератора 3 на входысчетчиков б первой строки матричноймодели, а через элементы И 11), 14)(3 2-;7) - на входы счетчиков 161.С приходом второго импульса переполняется счетчик б, и перебрасывает внулевое состояние триггер 5 а г импульс с выхода триггера 5, черездифференцируищую цепочку 7 ли элемент ИЛИ 8 перебрасывает триггер9 о в единичное состояние. На счетчи 0 ке 16 зафиксируется код, равный 2,Переходный процесс заканчивается,если на выходах всех триггеров 9высокий потенциал, В результате насчетчиках 16 следующие эначения: О,2, б, 7, б, 5, 7, а н счетчике 22код 10. Далее с выхода дешифратора 23 подается управляющий сигнал на схемы 17 сравнения. Сгггналы сравнения с выхода схегл 17 сравнения перебрасывают триггеры 18 в единичное состояние. В данном случае триггеры 18, 18, 18 и 18 что соответствует вершинам, лежащим на кратчайшем пути графа сети.Таким образогл, устройство за счет введения дополнительных элементов с новыми связями обеспечивает получение нового положительного эффекта, который заключается в тогл, что, кроме величины кратчайшего пути всего графа одновременно определяются кратчайшие пути всего графа, одновременно определяются кратчайшие пути для всех вершин графа, а также вершины, образующие кратчайший путь в графе сети и повышает быстродействие известного устройства.Фориула изобретения1. Устройство для определения кратчайшего пути в графе, содержащее блок управления, импульсный вход которого соединен с выходом генератора импульсов, по числу строк и столбцов матричной модели графа цепочки из последовательно соединенных счетчика и триггера, выход тригГера каждого столбца через соответствующую дифференцирующую цепочку соединен с информационным входом соответствуюцЕго элемента ИЛИ, по числу столбцов матричной модели графа первую группу триггеров, первые входы которых подключены к первому выходу блока управления, по числу столбцов матричной модели графа первую и вторую гРуппы элементов И, входы счетчиковкаждой строки матричной модели графа соединены с выходом элемента И первой группы одноименного столбца матричной моде" ли графа и подключены к соответствугощеиу входу группы, блока управления, о т л и ч а ю щ е е с я тем, что с целью повышения быстродействия, в него введены по числу столбцов матричной модели графа группа элементов НЕ, третья и четвертая группы элементов И, первая и вторая группы счетчиков, группа схем сравнения и вторая группа триггеров, счетные входы каждого из которых подключены к выходу соотетствующей схемы сравнения группы, управлятий вход которой соединен совторым выходом блока управления, третий и четвертый выходы которого подключены к управляющим входам соотвествующих элементов И третьей из четвертой групп, выходы элементов Итретьей и четвертой группы соединены соответственно со входамисчетчиков первой и второй группы,выходы которых подключены к информационным входам соответствующих схемсравнения группы, выходы элементовИЛИ соединены со вторыми входаии соответствующих триггеров первойгруппы, выходы которых подкжчены кпервым входам соответствующих эле 15 ментов И первой группы и ко входамсоответствующих элементов НЕ группы, выходы, элементов НЕ группысоединены со вторыми входагли соответствугмцих элементов И второй20 группы, пятый выход блока управленияподключен ко вторым входам элементовИ первой и второй группы, выходыэлементов И второй группы соединеныс инфдрмационными входами соответствующих элементов И третьей ичетвертой группы.2. Устройство по п.1, о т л ич а ю щ е е с я тем, что, блокуправления содержит первый и второйГэлементы И, блок пуска и останова,счетчик и дешифратор, первый выходкоторого является четвертыи выходомблока, третьим выходогл которого является второй выход дешифратора,соединенный с первым входом блокапуска и останова, первый выход которого подключен к управляющему. входувторого элемента И, выход которогочерез счетчик соединен со входомдешифратора, третий выход которого40 соединен со вторым входом блокапуска и останова и является вторымвыходом блока, второй выход блокапуска и остахова подключен к первому входу первого элемента И, выход которого является пятым выхо 45 дом блока, первым выходом которогоявляется третий выход блока пускаи останова, второй вход первогоэлемента И является входом блока,инфориационные входы второго элеменз 0, та И являются группой входов блока.Источники информации,принятые во внимание при экспертизе1, Авторское свидетельство СССР9 547770, кл. С 06 Г 15/20, 1976.55 2. Авторское свидетельство СССРВ 640314, кл. С 06 С 7/122, 1977/5 сква, Жент" у ул.Проект иал Тираж 745ИИПИ Государственного кпо делам изобретений и3035, Ио 357 Раую итета Скрытийкая наб ректор С. цома