ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

ЭЛЕКТРИЧЕСКАЯ МОДЕЛЬ С ИДЕАЛЬНЫМИ ЭЛЕМЕНТАМИ ДЛЯ ПОИСКА КРАТЧАЙШЕГО ПУТИ НА ВЗВЕШЕННОМ ОРИЕНТИРОВАННОМ ГРАФЕ

Journal: Automation of technological and business processes (Vol.10, No. 2)

Publication Date:

Authors : ;

Page : 38-43

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

Source : Downloadexternal Find it from : Google Scholarexternal

Abstract

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

Last modified: 2018-12-03 23:01:27