SHORTEST-PATH AND CLOSURE ALGORITHMS FOR BANDED MATRICES

被引：3

作者：

ALLISON, L

DIX, TI

YEE, CN

机构：

[1] Department of Computer Science, Monash University, Clayton, Melbourne

来源：

INFORMATION PROCESSING LETTERS | 1991年 / 40卷 / 06期

关键词：

ALGORITHMS; SHORTEST PATH; NEGATIVE CYCLE; CLOSURE; BANDED MATRIX;

D O I：

10.1016/0020-0190(91)90200-2

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A fast algorithm is given for the all-pairs shortest paths problem for banded matrices having band-width b. It solves the negative-cycle problem and calculates all path lengths within the band in O(nb2) time and calculates all other path lengths in O(n2b) time.

引用

页码：317 / 322

页数：6

共 11 条

[1]

ALLISON L, 1989, COMP APPL BIOSCIENCE, V4, P97

[2]

ALLISON L, 1989, TR89133 MON U DEP CO

[3]

Dijkstra EW., 1959, NUMER MATH, V1, P269, DOI DOI 10.1007/BF01386390

[4]

DIX TI, 1988, COMPUT APPL BIOSCI, V4, P117