A Research On The Shortest Path With Dynamic Time Constraints

The shortest path problem is widely used in both graph theory and algorithm design. It is also a fundamental problem with numerous applications in the real world. However, many network diagrams in the real world are dynamic, e.g., a path in traffic maps may have dynamic speed and cost. The definitions and the methods of the shortest path in such networks are different from those of the classical. The traditional path optimization considers only the source node and end node, so it cannot generally satisfy some specific requirements in pratical domains. This thesis studies variations of dynamical shortest path problem. The main works are as follows:(1) An improved Dijkstra algorithm was proposed firstly for dynamic shortest path problem. It computes the shortest path between nodes in a directed graph with dynamic speed and cost constraints. That is, each arc has dynamic speed and cost besides the static distance. The time and cost is combined by a scaling factor. By adjusting the factor it can compute shortest time / distance and minimum cost path between nodes. The improved algorithm is proved to be reliable, and the experimental results also demonstrate the effectiveness of the algorithm.(2) The problem of shortest pathes which is required to pass given nodes is studied. The problem has two scanarios. One is that the given nodes are ordered. It can be solved in terms of path partition. The other is that the given nodes are unordered. Namely, one needs to find an optimial path which passes throught all the given nodes. This problem is proved to be NP-complete. To attack this problem, we propose an approach using answer set programming on Hamiltonian path.(3) A method is also presneted which predicts the departure time for a given due of destionations. Informally, it is the inverse operation of the improved Dijkstra algorithm. Experimental results on the New York city maps demonstrate the effectiveness of the proposed methods.