Concurrent path selection and real-time applications: aircraft routing and task scheduling
D.I. Lawson · 2002
A method of finding the shortest concurrent path on a graph for p concurrent players, p/spl ges/1, is presented. Real-time applications, the routing of aircraft and the scheduling of collections of tasks are then discussed and a parallel Bellman shortest path algorithm is described which finds the shortest path from node r to node s on a graph G. Using this algorithm and the proper configuration of processors the shortest path on a graph with k nodes can be found in O(log n) time for 2(m/sup -1/)+1<k<(n=2/sup m/)+1. This is faster than other algorithms currently available within the professional literature. To find concurrent paths is a new problem which has particular application for the best use of resources. The algorithm can be adapted to schedule a wide variety of concurrent tasks.