Exact Solutions of Shortest Path Problems by Using Mechanical Analogies

The NAFEMS Eastern European 2020 Virtual Conference took place on the 23rd and 24th of September 2020. The event gave participants access to high level presentations in the field of structural mechanics, computational fluid dynamics, electromagnetics and discrete element methods.

Resource Abstract

The real-world importance of shortest path problems (SPPs) leads numerous scientists to study effective algorithms for the solutions of SPPs. Although the methods used for the solution of SPPs are relatively simple, due to reasons arising from the nature of the problem, the computational cost and the time required to obtain an exact solution often reduce the effectiveness of these methods.

In this study, an effective approach based on mechanical analogies that can be used effectively in the exact solution of SPPs is presented. According to the approach, the solution process comprises transformation of graph of SPP, and boundary conditions into structural system and obtainment of numerical solution by using finite element method (FEM). Simply put, with this approach, the points where the shortest path between them is desired to be found in the SPP is transformed into the support and loading points of the structural system and the structural system is analyzed. Depending on the displacement and element positions obtained from the analysis results, the exact solution of the SPP is obtained effectively and quickly.