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

(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ В ГРАФЕ(57) Изобретение относится к вычислительной технике и может быть использовано для нахождения кратчайших путей меж ду двумя выбранными узлами. Устройство для определения кратчайшего пути в графе содержит источник 1 регулируемого напряжения, модели 2=1, , 2 - 5 узлов и модели 3=1,23=3,5 ветвей. В состав каждой модели узла входит блок 4 задания веса, содержащий переменный резистор 5 и источник 6 напряжения, тиристор 7, информационные вход 8 и выход 9 модели узла и блок 10 индикации, содержащий резистор. В состав модели 3 ветви входит блок 4, тиристор 7, блок 10, с первого по восьмой развязывающие диоды 1118, первый и второй информационные входы 19 и 20 и выходы 21 и 22 модели ветви. В исходном состоянии напряжение на входе источника 1 равно нулю. С помощью блоков 4 в управляющих цепях тиристоров 7 устанавливают токи, соответствующие напряжениям переключения тиристоров, пропорциональным весам узлов и ребер графа.Положительный полюс источника напряжения 1 подключают к входу 8 начального узла, отрицательный полюс источника 1 - к выходу 9 конечного узла. Постепенно увеличивают напряжение источника 1 до того момента, когда произойдет переключение тиЯ ристоров 7, через которые проходит кратчайший маршрут между начальным и конечным узлами графа. Устройство позволяет, фф ф задавая одинаковыми веса ветвей, находить С кратчайший путь в графах со взвешенными узлами или, задавая одинаковыми веса уз- Я лов, находить кратчайший путь в графе со взвешенными ветвями, 1 ил. Ваввй1314354 Изобретение относится к вычислительнойтехнике и может быть использовано для решения задач нахождения кратчайших путеймежду двумя выбранными узлами.Целью изобретения является расширениефункциональных возможностей устройстваза счет нахождения кратчайшего пути вграфе с взвешенными узлами и ветвями.На чертеже изображено устройство,моделирующее граф, имеющий пять узлови шесть ветвей.В состав устройства входит источник 1регулируемого напряжения, модели 2 - 12 - 5 узлов и модели 3 - 1,2; ; 3 - 3,5 ветвей.В состав каждой модели узла входит блок4 задания напряжения веса, содержащий переменный резистор 5 и источник 6 напряжения, тиристор 7, информационные вход 8и выход 9 модели узла и блок 10 индикации,содержащий резистор,В состав модели 3 ветви входит блок 4, блок 10, тиристор 7, с первого по восьмой развязываюшие диоды 11 - 18, первый и второй информационные входы 19 и 20 и выходы 21, 22 модели ветви. Устройство работает следующим образом.С помощью блоков 4 устанавливают в управляющих цепях тиристоров 7 токи, соответствующие напряжениям переключения тир исторов, пропорциональным весам узлов ветвей. Полюса источника 1 подключают к моделям начального и конечного узлов графа.При увеличении напряжения источника 1 от нуля до некоторой определенной величины происходит переключение тиристоров, принадлежащих кратчайшему пути.В этой цепи потечет ток, создавая падение напряжения на резисторах блоков 10, в результате чего будут отмечены узлы и вершины кратчайшего пути (элементы индикации, обеспечивающие выдачу сигналов о протекании тока, на чертеже не показаны).Устройство позволяет задавая одинаковыми веса ветвей, находить кратчайший путь в графах со взвешенными узлами, или, задавая одинаковыми веса узлов, находить кратчайший путь в графе со взвешенными ребрами. 5 10 15 20 25 30 35 40 2Фориула изобретенияУстройство для определения кратчайшего пути в графе, содержащее источник регулируемого напряжения и модели ветвей графа, каждая из которых содержит блок задания напряжения веса, два развязываюших диода, блок индикации и тиристор, причем выход блока задания веса подключен к управляюгцему электроду тиристора, анод которого подключен к выходу блока индикации, а катод - к опорному входу блока задания веса, отличающееся тем, что, с целью расширения функциональных возможностей уст ройства за счет нахождения кратчайшего пути в графе с взвешенными узлами и ветвями, в него введены модели узлов, содержагцие блок задания веса, блок индикации и тиристор, причем выход блока задания веса подключен к управляющему электроду тиристора, анод которого подключен к выходу блока индикации, информационный вход которого является информационным входом модели узла, информационный выход которой подключен к катоду тиристора и к опорному входу блока задания веса, модели узлов и ветвей соединены согласно топологии графа, в модель ветви введены шесть развязывающих диодов, причем аноды первого и второго диодов подключены к опорному входу блока задания напряжения веса, катод первого развязываюгцего диода подключен к катоду третьего и анодам четвертого и пятого развязывающих диодов, катод второго развязывающего диода подключен к анодам шестого и седьмого и к катоду восьмого развязывающего диода, катоды пятого и шестого развязывающего диодов подключены к входу блока индикации, аноды третьего и восьмого развязывающих диодов являются первым и вторым информационными входами модели ветви соответственно, катоды четвертого и седьмого развязывающих диодов являются первым и вторым информационными выходами модели ветви соответственно, выход источника регулируемого напряжения подключен к информационному входу модели узла, находящегося в начале пути, опорный вход - к информационному выходу модели узла, находягцегося в конце пути.Составитель Л. Мишин Редактор А. Долиниц Техред И. Верес Корректор . Решетняк Заказ 2007/50 Тираж 673 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий3035, Москва, Ж - 35, Раушская наб, ь 4,5 Производственно-полиграфицеское предприятие, г. Ужгород, л. роектная, 4