There are various K-best route problems associated with a network. The one studied here is that of finding, for all node pairs (s,t), a best route from s to t together with an alternative route which is optimal subject to not containing the first edge of the best route. The relevance of this problem to dynamic vehicle guidance and to routing in communication networks is briefly discussed. An algorithm is developed whose complexity, under conditions likely to be met in practice, is established. An illustrative example is given.
