Устройство для определения кратчайшего пути в графе Советский патент 1987 года по МПК G06G7/122 

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

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

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

В состав устройства входит источник 1 регулируемого напряжения, модели 2-1,..., узлов и модели 3-1,2; ...; 3-3,5 ветвей.

В состав каждой модели узла входит блок

4 задания напряжения веса, содержащий пе- ,с ми, в него введены модели узлов, содержа- ременный резистор 5 и источник 6 напря-шие блок задания веса, блок индикации и

жения, тиристор 7, информационные вход 8 тиристор, причем выход блока задания веса

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

и выход.9 модели узла и блок 10 индикации, содержащий резистор.

блока индикации, информационный вход В состав модели 3 ветви входит блок 4, 20 которого является информационным входом

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

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано для нахождения кратчайших путей между двумя выбранными узлами. Устройство для определения кратчайшего пути в графе содержит источник 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: