Dijkstra's shortest path algorithm
E1045595
Dijkstra's shortest path algorithm is a classic graph algorithm that efficiently computes the minimum-cost paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.
Statements (51)
| Predicate | Object |
|---|---|
| instanceOf |
graph algorithm
ⓘ
shortest path algorithm ⓘ single-source shortest path algorithm ⓘ |
| algorithmParadigm | greedy algorithm ⓘ |
| application |
GPS navigation systems
ⓘ
game AI pathfinding ⓘ robot path planning ⓘ routing in communication networks ⓘ transportation planning ⓘ |
| assumesEdgeWeights | non-negative ⓘ |
| correctFor | graphs with non-negative edge weights ⓘ |
| definedOn | weighted graph ⓘ |
| developedBy | Edsger W. Dijkstra NERFINISHED ⓘ |
| failsWhen |
graph has negative edge weights
ⓘ
graph has negative weight cycle ⓘ |
| field | computer science ⓘ |
| graphType |
directed graph
ⓘ
undirected graph ⓘ |
| input |
graph
ⓘ
source vertex ⓘ |
| namedAfter | Edsger W. Dijkstra NERFINISHED ⓘ |
| notCorrectFor | graphs with negative edge weights ⓘ |
| output |
shortest path distances from source to all vertices
ⓘ
shortest path tree ⓘ |
| property |
computes optimal paths under non-negative weights
ⓘ
deterministic algorithm ⓘ label-setting algorithm ⓘ |
| relatedTo |
A* search algorithm
NERFINISHED
ⓘ
Bellman–Ford algorithm NERFINISHED ⓘ Floyd–Warshall algorithm NERFINISHED ⓘ Johnson's algorithm NERFINISHED ⓘ |
| requires | non-negative edge weights ⓘ |
| solvesProblem | single-source shortest path problem ⓘ |
| spaceComplexity | O(V + E) ⓘ |
| step |
initializes all distances to infinity except source
ⓘ
relaxes outgoing edges of selected vertex ⓘ repeatedly selects vertex with minimum tentative distance ⓘ |
| subfield |
algorithms
ⓘ
graph theory ⓘ |
| terminatesWhen | all vertices are processed ⓘ |
| timeComplexity |
O((V + E) log V) with binary heap
ⓘ
O(E + V log V) with Fibonacci heap ⓘ O(V^2) with adjacency matrix and simple array ⓘ |
| usesDataStructure |
distance array
ⓘ
min-heap ⓘ predecessor array ⓘ priority queue ⓘ |
| worksOn |
dense graphs
ⓘ
sparse graphs ⓘ |
| yearProposed | 1956 ⓘ |
| yearPublished | 1959 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.