|
gptkbp:instanceOf
|
gptkb:algorithm
graph
shortest path algorithm
|
|
gptkbp:category
|
computer science
operations research
|
|
gptkbp:complexity
|
O((V+E) log V) with min-priority queue
O(V^2) with simple implementation
|
|
gptkbp:countryOfPublication
|
Dutch
|
|
gptkbp:doesNotWorkOn
|
graphs with negative edge weights
|
|
gptkbp:firstPublished
|
1959
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Dijkstra's algorithm
|
|
gptkbp:input
|
source vertex
weighted graph
|
|
gptkbp:introducedIn
|
1956
|
|
gptkbp:inventedBy
|
gptkb:Edsger_W._Dijkstra
|
|
gptkbp:namedAfter
|
gptkb:Edsger_W._Dijkstra
|
|
gptkbp:originalPublicationJournal
|
gptkb:Numerische_Mathematik
|
|
gptkbp:originalPublicationTitle
|
gptkb:A_note_on_two_problems_in_connexion_with_graphs
|
|
gptkbp:output
|
shortest path distances
shortest path tree
|
|
gptkbp:relatedTo
|
gptkb:A*_search_algorithm
gptkb:Bellman-Ford_algorithm
gptkb:Floyd-Warshall_algorithm
|
|
gptkbp:solvedBy
|
single-source shortest path
|
|
gptkbp:usedIn
|
routing
network analysis
map navigation
|
|
gptkbp:worksWith
|
graphs with non-negative edge weights
|
|
gptkbp:bfsParent
|
gptkb:Edsger_Dijkstra
|
|
gptkbp:bfsLayer
|
4
|