Shortest Path First (SPF) algorithm
GPTKB entity
Statements (23)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:algorithm
|
| gptkbp:alsoKnownAs |
gptkb:Dijkstra's_algorithm
|
| gptkbp:application |
computer networking
robotics transportation planning |
| gptkbp:category |
graph
|
| gptkbp:complexity |
O(V^2) with simple implementation
O(E + V log V) with min-priority queue |
| gptkbp:creator |
gptkb:Edsger_W._Dijkstra
|
| https://www.w3.org/2000/01/rdf-schema#label |
Shortest Path First (SPF) algorithm
|
| gptkbp:input |
graph
source node |
| gptkbp:introducedIn |
1959
|
| gptkbp:limitation |
does not handle negative edge weights
|
| gptkbp:output |
shortest path tree
|
| gptkbp:purpose |
find shortest path in a weighted graph
|
| gptkbp:relatedTo |
gptkb:Bellman-Ford_algorithm
gptkb:Floyd-Warshall_algorithm gptkb:A*_algorithm |
| gptkbp:usedIn |
gptkb:IS-IS_routing_protocol
gptkb:OSPF_routing_protocol |
| gptkbp:bfsParent |
gptkb:OSI_IS-IS_Intra-domain_Routing_Protocol
|
| gptkbp:bfsLayer |
8
|