Development of a software module for calculating the shortest path problem implemented by the Bellman-Ford algorithm
Mariia Maslova, Anna Mordvinova, Emine Khalilaeva · AIP conference proceedings · 2024
The tasks of finding the shortest paths are relevant in various fields of science and technology.They are used to find the optimal route, both during transportation and between any two points; in autopilot systems; switching information flow in the Internet; in time of planning travelling and studying etc.The method is considered and implemented at the software level.A computation algorithm for the shortest path problems implemented by the Bellman-Ford, Floyd-Warshall and their main computational difficulties when using these methods was presented in this article.For the implementation, the Bellman-Ford algorithm was chosen, because this algorithm uses a common matrix of weights, unlike Dijkstra's algorithm, it allows the presence of negative edge weights and has less computational complexity than the Floyd-Warshall algorithm.A computation algorithm for the shortest path problems was created, a block diagram of the software implementation of the main body of the algorithm was presented, a software product was written, implemented by the Bellman-Ford algorithm using the Python programming language, to facilitate and manual routine calculations by this method.The algorithm of this method and the implementation of the program on the example of finding the shortest path from Moscow to nearby 9 cities also was presented.