多源多通道最短路径问题的研究

Selecting the Shortest One from Multi-Source and Multi-Channel Paths

多源、多通道的最短路径问题是应急救灾和部队机动中的一个重要问题。给出了道路通道的多边形表示以及多边形内的点应满足的条件,并基于Dijkstra算法给出了求解多边形通道内最短路径的一个改进算法。另外,当多个通道的最短路径存在共同边时,给出了有效的解决方法。

Multi-source, multi-channel shortest path problem is an important issue in emergency relief and military maneuvering. A polygon which expressing the road channel was proposed, and what kinds of conditions polygon points should meet was discussed, and the improved algorithm of solving the shortest path based on Dijkstra algorithm was given. In addition, an effective solution to find the shortest path was gaven when multiple channels shared common edges.