Электрическая модель с идеальными элементами для поиска кратчайшего пути на взвешенном ориентированном графе
| dc.contributor.author | В. Ю. Гнатенко, П. В. Ступень, К. В. Дікусар, Е. І. Шутєєв | |
| dc.date.accessioned | 2018-12-18T15:06:19Z | |
| dc.date.available | 2018-12-18T15:06:19Z | |
| dc.date.issued | 2018 | |
| dc.description.abstract | Рассмотрена проблема определения кратчайшего пути во взвешенном ориентированном графе с применением электрической модели с идеальными диодами, источниками напряжения и тока. Проведены теоретические исследования в области математического моделирования электрических схем с идеальными элементами. Рассмотрен пример определения кратчайшего пути в заданном взвешенном ориентированном графе.В задачах небольшой размерности можно использовать аналоговые электрические модели. Однако для больших графов аналоговые модели становятся весьма громоздкими из-за необходимости включения в каждую цепь изолированного источника электрической энергии, а точность решения низкой из-за не идеальности характеристик элементов.В данной статье рассматривается развитие модели представления взвешенного ориентированного графа без использования структурной матрицы или каких-либо других топологических матриц. Вместо этого предлагается формировать и обрабатывать в процессе анализа список ветвей с присущими им характеристиками и параметрами.Целью работы является обоснование электрической модели для поиска кратчайшего пути во взвешенном ориентированном графе, представление алгоритма для реализации и иллюстрации эффективности метода.Так как исходная электрическая цепь не содержит накопителей энергии и в ней в принципе невозможен переходный процесс, предлагается преобразовать исходную электрическую цепь в динамическую путем присоединения к каждому узлу схемы по емкости, другой конец которой соединить с базисным узлом, не принадлежащим данной схеме и общим для всех емкостей. В результате становится возможным протекание переходного процесса, по окончании которого токи емкостей станут равными нулю и не будут оказывать влияния на распределение токов и напряжений в схеме. | |
| dc.identifier.issn | 2312-931X | |
| dc.identifier.uri | https://card-file.ontu.edu.ua/handle/123456789/5808 | |
| dc.identifier.uri | https://doi.org/10.15673/atbp.v10i2.976 | |
| dc.source | Automation of technological and business processes | |
| dc.title | Электрическая модель с идеальными элементами для поиска кратчайшего пути на взвешенном ориентированном графе |