Premium
A simple O ( n 2 ) algorithm for the all‐pairs shortest path problem on an interval graph
Author(s) -
Mirchandani Prakash
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199605)27:3<215::aid-net6>3.0.co;2-l
Subject(s) - shortest path problem , graph , widest path problem , yen's algorithm , combinatorics , computer science , path graph , algorithm , shortest path faster algorithm , distance , floyd–warshall algorithm , mathematics , path (computing) , interval (graph theory) , dijkstra's algorithm , line graph , graph power , programming language
Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O ( n 2 ) 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.