|
gptkbp:instanceOf
|
gptkb:algorithm
graph
|
|
gptkbp:cannotHandle
|
negative edge weights
|
|
gptkbp:category
|
greedy algorithm
|
|
gptkbp:complexity
|
O((V+E) log V) with min-priority queue
O(V^2) with simple array
|
|
gptkbp:describedBy
|
Edsger W. Dijkstra's 1959 paper
|
|
gptkbp:firstPublished
|
1959
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Dijkstra algorithm
|
|
gptkbp:implementedIn
|
gptkb:Java
gptkb:Python
gptkb:C++
C
|
|
gptkbp:input
|
source vertex
weighted graph
|
|
gptkbp:namedAfter
|
gptkb:Edsger_W._Dijkstra
|
|
gptkbp:output
|
shortest path distances
predecessor information
|
|
gptkbp:relatedTo
|
gptkb:Bellman-Ford_algorithm
gptkb:Floyd-Warshall_algorithm
gptkb:A*_algorithm
|
|
gptkbp:solvedBy
|
single-source shortest path problem
|
|
gptkbp:step
|
initialize distances
repeat until all vertices processed
select minimum distance vertex
update neighbor distances
|
|
gptkbp:usedBy
|
gptkb:Google_Maps
gptkb:OpenStreetMap
gptkb:OSPF_routing_protocol
network simulators
|
|
gptkbp:usedIn
|
routing
network analysis
map navigation
|
|
gptkbp:bfsParent
|
gptkb:LSDB_(Link_State_Database)
|
|
gptkbp:bfsLayer
|
6
|