An incremental algorithm for identification of longest (shortest) paths

Abstract

In this paper we describe an algorithm that finds the next k longest or shortest paths of a directed acyclic graph on demand, without computing all previous paths again. We also suggest a technique to find longest (shortest) paths through a specific input or a specific input output pair. This algorithm has many applications including but not limited to timing analysis of digital integrated circuits, timing driven placement of digital circuits, and delay analysis/routing of messages in computer communication networks. © 1994.