Modifying a path into the shortest path

More Info
expand_more

Abstract

The inverse shortest path problem (ISPP) is a problem based on graph theory, that is to design link weights in a graph to satisfy that given paths are the shortest between the corresponding node pairs. It can be used in networks of complex systems to solve practical problems such as re-routing in transportation systems and reallocating resources in IP networks. This thesis proposes two new methods based on the simplex algorithm, the split path method (Sp) and the limit constraints method (Lc), to solve the inverse shortest path problem with one predefined path (ISPP-S). The different approaches used to find the constraints in these two methods affect the obtained optimal solution and running time. By analyzing the simulation results (running time, adjustment of link weight as well as the relationship between path length and running time) of these two algorithms in graphs with various structures, we can evaluate the efficiency of Sp and Lc and summarize their applicable networks. After modification, these two methods can be utilized to solve the extended inverse shortest path problem with multiple target paths (ISPP-M) and with target paths in a spanning tree (ISPP-T). In addition, the applicability of these two algorithms is also extended from directed graphs to undirected graphs. The application of Sp and Lc algorithms in a variety of empirical networks is also discussed. Through the analysis of the above problems and the experimental results, we discover that Sp is more suitable to solve ISPP with relatively few constraints (ISPP-S or ISPP in small-sized networks); Lc performs better when solving ISPP with relatively more constraints (ISPP-M or ISPP in large-sized networks).