Subgraphs Generating Algorithm for Obtaining Set of Node-Disjoint Paths in Terrain-Based Mesh Graphs

摘要

In the article an algorithm (SGDP) for solving node-disjoint shortest K paths problem in mesh graphs is presented. The mesh graph can represent e.g. a discrete terrain model in a battlefield simulation. Arcs in the graph geographically link adjacent nodes only. The algorithm is based on an iterative subgraph generating procedure inside the mesh graph (for finding a single path from among K paths single subgraph is generated iteratively) and the usage of different strategies to find (and improve) the solution. Some experimental results with a discussion of the complexity and accuracy of the algorithm are shown in detail.