An improvement of Dijkstra's method for finding a shortest path in a graph
type: Item
instance of: scholarly article
title: An improvement of Dijkstra's method for finding a shortest path in a graph
zbMATH Open document ID: 0587.05042
DOI: 10.1016/0166-218X(86)90072-7
author: Jean Bovet
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: A slight modification of Dijkstra's original method is presented. If a lower bound on the length of the shortest path between two nodes of a network is known, this modification allows to save up to 35 \% of the computing time which would be required for the original method.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3941582
zbMATH Keywords: Dijkstra's algorithm
zbMATH Keywords: shortest path
reviewed by: Philippe Vincke
MaRDI profile type: Publication
cites work: A Dual Shortest Path Algorithm
cites work: A note on two problems in connexion with graphs
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: Shortest Path and Network Flow Algorithms
cites work: A generalized permanent label setting algorithm for the shortest path between specified nodes
description: scientific article; zbMATH DE number 3941582