Электрическая модель с идеальными элементами для поиска кратчайшего пути на взвешенном ориентированном графе

Abstract

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