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

The problem of determining the shortest path in a weighted and directed graph is considered using an electric model with ideal diodes, voltage and current sources. Theoretical studies in the field of mathematical modeling of electrical circuits with ideal elements have been carried out. An example of determining the shortest path in a given weighted directed graph is considered. In problems of small dimension, analog electric models can be used. However, for large graphs, analog models become very cumbersome because of the need to include an isolated source of electrical energy in each circuit, and the accuracy of the solution is low because of the non-ideality of the characteristics of the elements. In this paper, we consider the development of a representation model of a weighted and directed graph without the use of a structural matrix or any other topological matrices. Instead, it is proposed to form and process in the process of analysis a list of branches with their inherent characteristics and parameters. The aim of the paper is to justify the electric model for finding the shortest path in a weighted oriented graph, the representation of the algorithm for implementing and illustrating the effectiveness of the method. Since the initial electric circuit does not contain energy storage devices and, in principle, a transient process is not possible in it, it is proposed to convert the initial electric circuit to a dynamic one by attaching to each node of the circuit in capacity, the other end of which is connected to a basic node that does not belong to this scheme and is common to all containers. As a result, a transient process becomes possible, at the end of which the capacitance currents will become equal to zero and will not affect the distribution of currents and voltages in the circuit. [ABSTRACT FROM AUTHOR]