Shortest Route Algorithms for Sparsely Connected Networks
Abstract
This report studies the shortest route problem for networks that are less fully connected. Two algorithms are presented which exploit the absence of arcs in solving the shortest route problem. The first, which is designated the NXN algorithm, would tend to be the more applicable to networks typically encountered in practice. The second, which is an improvement on Hu's decomposition shortest route algorithm, is more efficient for a small class of networks; however, it generally requires less memory to hold the required decomposition information in the computer than does the NXN algorithm.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1976
- Accession Number
- ADA032134
Entities
People
- Joe E. Defenderfer
Organizations
- Massachusetts Institute of Technology