A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph
Prakash Mirchandani · Networks · 1996
Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n2) algorithm for solving the all-pairs shortest path problem on graph G. A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our algorithm is concise to state, intuitive to understand, and easy to implement. © 1996 John Wiley & Sons, Inc.