Single-Source Shortest Path

GPTKB entity

Predicate	Object
gptkbp:instanceOf	graph
gptkbp:appliesTo	directed graphs undirected graphs unweighted graphs weighted graphs
gptkbp:Bellman-Ford_algorithm_complexity	O(VE)
gptkbp:BFS_complexity_(unweighted)	O(V+E)
gptkbp:common_algorithm	gptkb:Dijkstra's_algorithm gptkb:Breadth-First_Search gptkb:Bellman-Ford_algorithm
gptkbp:complexity	depends on algorithm
gptkbp:Dijkstra's_algorithm_complexity	O((V+E) log V)
gptkbp:field	computer science graph theory
gptkbp:firstDescribed	1956
https://www.w3.org/2000/01/rdf-schema#label	Single-Source Shortest Path
gptkbp:input	source vertex weighted graph
gptkbp:limitation	cannot handle negative cycles
gptkbp:notableContributor	gptkb:Lester_Ford,_Jr. gptkb:Richard_Bellman gptkb:Edsger_W._Dijkstra
gptkbp:output	shortest path distances paths from source to all vertices
gptkbp:relatedConcept	gptkb:All-Pairs_Shortest_Path Negative weight cycles Single-Destination Shortest Path
gptkbp:solvedBy	gptkb:shortest_path_problem
gptkbp:used_in	robotics map navigation transportation planning network routing
gptkbp:bfsParent	gptkb:Nvidia_cuGraph
gptkbp:bfsLayer	6