Microcomputer-based algorithms for large scale shortest path problems (Q1072451)

This paper reports on the implementation and computational testing in the microcomputer environment of several versions of a threshold-based in- core/out-of-core shortest path algorithm for finding the shortest path from one node to all other nodes in a network. These variants were compared to the best in-core/out-of-core label-correcting code, C5V7, developed in the 1970's. All codes were written in Pascal and tested on an 8088 microprocessor-based computer with a hard disk unit (IBM PC/XT) under the MS-DOS operating system. The results of the empirical study on a diverse set of medium and large-scale random and city transit grid networks provide new insights for the design of in-core/out-of-core shortest path algorithms and demonstrate the remarkable capability of a threshold-based algorithm to be fine tuned to a particular problem topology, processing environment, or computer configuration. In addition these results demonstrate the feasibility and computational tractability of solving large scale shortest path problems with microcomputers. The best approach solved a variety of problems ranging in size up to 15,000 nodes and 600,000 arcs in 10 minutes or less of wall clock time.