Extended Dijkstra Algorithm and Moore‑Bellman‑Ford Algorithm

The shortest path problem which can not be solved by classical Dijkstra algorithm and Moore-Bellman-Ford algorithm appears frequently, for example, the Anti-risk Path Problem proposed by Xiao et al. To address this kind of shortest path problem, the present work proposes and studies a general single-source shortest path problem, which is motivated by current interest in needing to extend the total weight function of paths on a network and the classical shortest path problem. Firstly, define the path functional on a set of certain paths with same source on a graph; introduce a few concepts of the defined path functional; and make some discussions on the properties of the path functional. Secondly, develop a kind of general single-source shortest path problem (GSSSP). Thirdly, following respectively the approaches of the well known Dijkstra’s algorithm and Moore-Bellman-Ford algorithm, design an extended Dijkstra’s algorithm (EDA) and an extended Moore-Bellman-Ford algorithm (EMBFA) to solve the problem GSSSP under certain given conditions. Fourthly, under the assumption that the value of related path functional for any path can be obtained in M(n) time, prove respectively the algorithm EDA solving the problem GSSSP in O(n2)M(n) time and the algorithm EMBFA solving the problem GSSSP in O(mn)M(n) time. Finally, some applications of the designed algorithms are shown with a few examples. What we done can not only improve both the researches and the applications of the shortest path theory, but also promote the development of the researches and the applications of other combinatorial optimization problems, promote the development of the algorithm theory and promote the development of the artificial intelligence.