Solving the Longest Path Problem in Directed Acyclic Graphs Based on Amoeba Algorithm
Qing Wang, Xiaoge Zhang, Sankaran Mahadevan and Yong Deng
The longest path problem (LPP) is to find a simple path with maximum length in a given graph, which plays an important role in many real-world applications, such as job shop scheduling problem, route planning. LPP in directed acyclic graphs (DAG) has important applications, such as finding the critical path in scheduling problems. In this paper, we present an amoeba algorithm, inspired by the plasmodium of Physarum polycephalum, to solve the longest path problem in the DAG. The proposed method is composed of two parts: (1) a fictional rule is constructed to replace ohm’s law. Based on this mechanism, the current tends to pass through the conductor with more resistance. (2) The original amoeba model is adjusted to work in a special circuit based on our fictional rule. As a topological sorting is necessary in model calculations, it can only deal with LPP in DAG. In addition, the evolving processes of the proposed model have been introduced in detail in this paper. A numerical example is used to show the efficiency of the proposed method.
Keywords: Longest path problem, physarum polycephalum, directed acyclic graphs, optimization