Publication detail
An Efficient Algorithm for All-Pairs Shortest Paths Problem
ŠEDA, M.
English title
An Efficient Algorithm for All-Pairs Shortest Paths Problem
Type
conference paper
Language
en
Original abstract
The All-Pairs Shortest Paths Problem that finds shortest paths between all pairs of vertices in a connected weighted graph is usually solved by the Floyd-Warshall algorithm based on dynamic programming approach. In this paper, we propose a 'Repeated' Dijkstra algorithm based on a binary heap data structure and show that, for graphs with nonnegative weights, it has lower time complexity than the classical Floyd-Warshall algorithm
English abstract
The All-Pairs Shortest Paths Problem that finds shortest paths between all pairs of vertices in a connected weighted graph is usually solved by the Floyd-Warshall algorithm based on dynamic programming approach. In this paper, we propose a 'Repeated' Dijkstra algorithm based on a binary heap data structure and show that, for graphs with nonnegative weights, it has lower time complexity than the classical Floyd-Warshall algorithm
Keywords in English
shortest path, dynamic programming, binary heap
RIV year
2002
Released
01.09.2002
Publisher
MARQ
Location
Ostrava
ISBN
80-85988-77-1
Book
Proceedings of the XXIVst International Autumn Colloquium Advanced Simulation of Systems ASIS 2002
Pages count
6
BIBTEX
@inproceedings{BUT10546,
author="Miloš {Šeda},
title="An Efficient Algorithm for All-Pairs Shortest Paths Problem",
booktitle="Proceedings of the XXIVst International Autumn Colloquium Advanced Simulation of Systems ASIS 2002",
year="2002",
month="September",
publisher="MARQ",
address="Ostrava",
isbn="80-85988-77-1"
}