Numerical Solutions to the Variational Problems by Dijkstra’s Path-Finding Algorithm

Abstract

In this work, we propose the general idea of using a path-finding algorithm to solve a variational problem. By interpreting a variational problem of finding the function that minimizes a functional integral as a shortest path finding, we can apply the shortest path-finding algorithm to numerically estimate the optimal function. This can be achieved by discretizing the continuous domain of the variational problem into a spatially weighted graph. The weight of each edge is defined according to the function of the original problem. We adopt the Moser lattice as the discretization scheme since it provides adjustable connections around a vertex. We find that this number of connections is crucial to the estimation of an accurate optimal path. Dijkstra’s shortest path-finding algorithm was chosen due to its simplicity and convenience in implementation. We validate our proposal by applying Dijkstra’s path-finding algorithm to numerically solve three famous variational problems, i.e., the optical ray tracing, the brachistochrone, and the catenary problems. The first two are examples of problems with no constraint. The standard Dijkstra’s algorithm can be directly applied. The third problem is an example of a problem with an isoperimetric constraint. We apply the Lagrangian relaxation technique to relax the optimization in the standard Dijkstra algorithm to incorporate the constraint. In all cases, when the number of sublattices is large enough, the results agree well with the analytic solutions. In all cases, the same path-finding code is used, regardless of the problem details. Our approaches provide more insight and promise to be more flexible than conventional numerical methods. We expect that our method can be useful in practice when an investigation of the optimal path in a complex problem is needed.

Keywords

• path finding
• Dijkstra’s algorithm
• variational problems
• optimization