Электрическая модель с идеальными элементами для поиска кратчайшего пути на взвешенном ориентированном графе
Ескіз недоступний
Дата
2018
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
Рассмотрена проблема определения кратчайшего пути во взвешенном ориентированном графе с применением электрической модели с идеальными диодами, источниками напряжения и тока. Проведены теоретические исследования в области математического моделирования электрических схем с идеальными элементами. Рассмотрен пример определения кратчайшего пути в заданном взвешенном ориентированном графе.В задачах небольшой размерности можно использовать аналоговые электрические модели. Однако для больших графов аналоговые модели становятся весьма громоздкими из-за необходимости включения в каждую цепь изолированного источника электрической энергии, а точность решения низкой из-за не идеальности характеристик элементов.В данной статье рассматривается развитие модели представления взвешенного ориентированного графа без использования структурной матрицы или каких-либо других топологических матриц. Вместо этого предлагается формировать и обрабатывать в процессе анализа список ветвей с присущими им характеристиками и параметрами.Целью работы является обоснование электрической модели для поиска кратчайшего пути во взвешенном ориентированном графе, представление алгоритма для реализации и иллюстрации эффективности метода.Так как исходная электрическая цепь не содержит накопителей энергии и в ней в принципе невозможен переходный процесс, предлагается преобразовать исходную электрическую цепь в динамическую путем присоединения к каждому узлу схемы по емкости, другой конец которой соединить с базисным узлом, не принадлежащим данной схеме и общим для всех емкостей. В результате становится возможным протекание переходного процесса, по окончании которого токи емкостей станут равными нулю и не будут оказывать влияния на распределение токов и напряжений в схеме.