A novel algorithm for all pairs shortest path problem based on matrix multiplication and pulse coupled neural network

Yudong Zhang; Lenan Wu; Geng Wei; Shuihua Wang

doi:10.1016/j.dsp.2011.02.004

A novel algorithm for all pairs shortest path problem based on matrix multiplication and pulse coupled neural network

Yudong Zhang^*, Lenan Wu, Geng Wei, Shuihua Wang

^*Corresponding author for this work

Southeast University, Nanjing

Research output: Contribution to journal › Article › peer-review

41 Citations (Scopus)

Abstract

All pairs shortest path (APSP) is a classical problem with diverse applications. Traditional algorithms are not suitable for real time applications, so it is necessary to investigate parallel algorithms. This paper presents an improved matrix multiplication method to solve the APSO problem. Afterwards, the pulse coupled neural network (PCNN) is employed to realize the parallel computation. The time complexity of our strategy is only O(log ²n), where n stands for the number of nodes. It is the fastest parallel algorithm compared to traditional PCNN, MOPCNN, and MPCNN methods.

Original language	English
Pages (from-to)	517-521
Number of pages	5
Journal	Digital Signal Processing: A Review Journal
Volume	21
Issue number	4
DOIs	https://doi.org/10.1016/j.dsp.2011.02.004
Publication status	Published - Jul 2011
Externally published	Yes

Keywords

All pairs shortest path
Matrix multiplication
Parallel algorithm
Pulse coupled neural network

Access to Document

10.1016/j.dsp.2011.02.004

Cite this

@article{f4e9459e936849fe96727f2d73a853b5,

title = "A novel algorithm for all pairs shortest path problem based on matrix multiplication and pulse coupled neural network",

abstract = "All pairs shortest path (APSP) is a classical problem with diverse applications. Traditional algorithms are not suitable for real time applications, so it is necessary to investigate parallel algorithms. This paper presents an improved matrix multiplication method to solve the APSO problem. Afterwards, the pulse coupled neural network (PCNN) is employed to realize the parallel computation. The time complexity of our strategy is only O(log 2n), where n stands for the number of nodes. It is the fastest parallel algorithm compared to traditional PCNN, MOPCNN, and MPCNN methods.",

keywords = "All pairs shortest path, Matrix multiplication, Parallel algorithm, Pulse coupled neural network",

author = "Yudong Zhang and Lenan Wu and Geng Wei and Shuihua Wang",

year = "2011",

month = jul,

doi = "10.1016/j.dsp.2011.02.004",

language = "English",

volume = "21",

pages = "517--521",

journal = "Digital Signal Processing: A Review Journal",

issn = "1051-2004",

number = "4",

}

TY - JOUR

T1 - A novel algorithm for all pairs shortest path problem based on matrix multiplication and pulse coupled neural network

AU - Zhang, Yudong

AU - Wu, Lenan

AU - Wei, Geng

AU - Wang, Shuihua

PY - 2011/7

Y1 - 2011/7

N2 - All pairs shortest path (APSP) is a classical problem with diverse applications. Traditional algorithms are not suitable for real time applications, so it is necessary to investigate parallel algorithms. This paper presents an improved matrix multiplication method to solve the APSO problem. Afterwards, the pulse coupled neural network (PCNN) is employed to realize the parallel computation. The time complexity of our strategy is only O(log 2n), where n stands for the number of nodes. It is the fastest parallel algorithm compared to traditional PCNN, MOPCNN, and MPCNN methods.

AB - All pairs shortest path (APSP) is a classical problem with diverse applications. Traditional algorithms are not suitable for real time applications, so it is necessary to investigate parallel algorithms. This paper presents an improved matrix multiplication method to solve the APSO problem. Afterwards, the pulse coupled neural network (PCNN) is employed to realize the parallel computation. The time complexity of our strategy is only O(log 2n), where n stands for the number of nodes. It is the fastest parallel algorithm compared to traditional PCNN, MOPCNN, and MPCNN methods.

KW - All pairs shortest path

KW - Matrix multiplication

KW - Parallel algorithm

KW - Pulse coupled neural network

UR - http://www.scopus.com/inward/record.url?scp=79955477650&partnerID=8YFLogxK

U2 - 10.1016/j.dsp.2011.02.004

DO - 10.1016/j.dsp.2011.02.004

M3 - Article

AN - SCOPUS:79955477650

SN - 1051-2004

VL - 21

SP - 517

EP - 521

JO - Digital Signal Processing: A Review Journal

JF - Digital Signal Processing: A Review Journal

IS - 4

ER -

A novel algorithm for all pairs shortest path problem based on matrix multiplication and pulse coupled neural network

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this