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

 

Изобретение относится к вычислительной технике и может быть использовано для нахождения кратчайших путей между двумя выбранными узлами. Устройство для определения кратчайшего пути в графе содержит источник 1 регулируемого напряжения , модели , ..., 2-5 узлов и модели ,2...,5 ветвей. В состав каждой модели узла входит блок 4 задания веса, содержаш,ий переменный резистор 5 и источник 6 напряжения, тиристор 7, информационные вход 8 и выход 9 модели узла и блок 10 индикации, содержащий резистор . В состав модели 3 ветви входит блок 4, тиристор 7, блок 10, с первого по восьмой развязываюш,ие диоды 11...18, первый и второй информационные входы 19 и 20 и выходы 21 и 22 модели ветви. В исходном состоянии напряжение на входе источника 1 равно нулю. С помощью блоков 4 в управляющих цепях тиристоров 7 устанавливают токи, соответствующие напряжениям переключения тиристоров, пропорциональным весам узлов и ребер графа. Положительный полюс источника напряжения 1 подключают к входу 8 начального узла, отрицательный полюс источника 1 - к выходу 9 конечного узла. Постепенно увеличивают напряжение источника 1 до того момента , когда произойдет переключение тиристоров 7, через которые проходит кратчайший маршрут между начальным и конечным узлами графа. Устройство позволяет, задавая одинаковыми веса ветвей, находить кратчайший путь в графах со взвешенными узлами или, задавая одинаковыми веса узлов , находить кратчайший путь в графе со взвешенны.ми ветвями. 1 ил. S (Л оо 00 ел 4:

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

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

РЕСПУБЛИК

А1 у 4 G 06 G 7/122 (21) 4055644/24-24 (22) 13.01.86 (46) 30.05.87. Бюл. № 20 (72) А. А Лелис, В. А. Клишин и Г. С. Полищук (53) 681.325(088.8) (56) Авторское свидетельство СССР № 830409, кл. G 06 G 7/122, 1979.

Авторское свидетельство СССР № 552617, кл. G 06 G 7/122, 1975. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

КРАТЧАЙШЕГО ПУТИ В ГРАФЕ (57) Изобретение относится к вычислительной технике и может быть использовано для нахождения кратчайших путей между двумя выбранными узлами. Устройство для определения кратчайшего пути в графе содержит источник 1 регулируемого напряжения, модели 2=1, ..., 2 — 5 узлов и модели

3=1,2...3=3,5 ветвей. В состав каждой модели узла входит блок 4 задания веса, содержащий переменный резистор 5 и источник 6 напряжения, тиристор 7, информационные вход 8 и выход 9 модели узла и блок 10 индикации, содержащий резисÄÄSUÄÄ 1314354 тор. В состав модели 3 ветви входит блок

4, тиристор 7, блок 10, с первого по восьмой развязывающие диоды 11...18, первый и второй информационные входы 19 и 20 и выходы 21 и 22 модели ветви. В исходном состоянии напряжение на входе источника

1 равно нулю. С помощью блоков 4 в управляющих цепях тиристоров 7 устанавливают токи, соответствующие напряжениям переключения тиристоров, пропорциональным весам узлов и ребер графа.

Положительный полюс источника напряжения 1 подключают к входу 8 начального узла, отрицательный полюс источника 1 — к выходу 9 конечного узла. Постепенно увеличивают напряжение источника 1 до того момента, когда произойдет переключение тиристоров 7, через которые проходит кратчайший маршрут между начальным и конечным узлами графа. Устройство позволяет, задавая одинаковыми веса ветвей, находить кратчайший путь в графах со взвешенными узлами или, задавая одинаковыми веса узлов, находить кратчайший путь в графе со взвешенными ветвями. 1 ил.

1314354

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

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

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

В состав устройства входит источник 1 регулируемого напряжения, модели 2 — 1,„., 2 — 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

2

Формула изобретения

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

1314354

Составитель A. Мишин

Редактор A. Долинич Техред И. Верес Корректор! . Решетняк

Заказ 2007/50 Тираж 673 !1одпнсное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий ! !3035, Москва, Ж вЂ” 35, Раушская наб., д. 4, 5

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