Detail publikace

An Efficient Algorithm for All-Pairs Shortest Paths Problem

ŠEDA, M.

Anglický název

An Efficient Algorithm for All-Pairs Shortest Paths Problem

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

en

Originální abstrakt

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

Anglický abstrakt

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

Klíčová slova anglicky

shortest path, dynamic programming, binary heap

Rok RIV

2002

Vydáno

01.09.2002

Nakladatel

MARQ

Místo

Ostrava

ISBN

80-85988-77-1

Kniha

Proceedings of the XXIVst International Autumn Colloquium Advanced Simulation of Systems ASIS 2002

Počet stran

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"
}