Johnson's algorithm for shortest paths

GPTKB entity

Statements (17)
Predicate Object
gptkbp:instanceOf gptkb:algorithm
gptkbp:citation Donald B. Johnson, 'Efficient Algorithms for Shortest Paths in Sparse Networks', JACM 1977
gptkbp:complexity O(V^2 log V + VE)
gptkbp:does_not_handle graphs with negative cycles
gptkbp:field computer science
graph theory
gptkbp:handles graphs with negative edge weights
https://www.w3.org/2000/01/rdf-schema#label Johnson's algorithm for shortest paths
gptkbp:input weighted directed graph
gptkbp:introducedIn 1977
gptkbp:output shortest paths between all pairs of vertices
gptkbp:proposedBy gptkb:Donald_B._Johnson
gptkbp:solvedBy all-pairs shortest path problem
gptkbp:uses gptkb:Dijkstra's_algorithm
gptkb:Bellman-Ford_algorithm
gptkbp:bfsParent gptkb:Donald_B._Johnson
gptkbp:bfsLayer 7