Live briefing
Everything about Dijkstra's algorithm
Algorithm for finding shortest paths
Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, a road network. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Dijkstra's algorithmA 5-minute orientation
- Skim a recent paper: Advanced heterogeneous block-parallel all-pairs shortest path algorithmInfluential work since 2022
- Pick up a classic book: Introduction to AlgorithmsThe most-reprinted book on the subject
- Read the landmark paper: Finding All-Pairs Shortest Path for a Large-Scale Transportation Network Using Parallel Floyd-Warshall and Parallel Dijkstra AlgorithmsCited 60 times
- Go sideways: Prim's algorithmA closely related topic
- Go sideways: Johnson's algorithmA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🏆 Landmark papers (most cited)
Finding All-Pairs Shortest Path for a Large-Scale Transportation Network Using Parallel Floyd-Warshall and Parallel Dijkstra Algorithms
Scalability of parallel algorithms for the all-pairs shortest-path problem
A Decomposition Algorithm for the All-Pairs Shortest Path Problem on Massively Parallel Computer Architectures
A task parallel algorithm for finding all-pairs shortest paths using the GPU
Parallel All-Pairs Shortest Path Algorithm: Network Decomposition Approach
Parallel Algorithm for Shortest Pairs of Edge-Disjoint Paths
All-pairs Shortest Path Algorithm based on MPI+CUDA Distributed Parallel Programming Model
Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementa- tion.
🆕 Influential since 2022
📚 Books worth reading
Introduction to AlgorithmsThomas H. Cormen, Charles E. Leiserson · 1990
Parallel Programming in C with MPI and OpenMPMichael J. Quinn · 2003
Fundamentals of data structures in CEllis Horowitz · 1993
Computer algorithmsEllis Horowitz · 1997
Algorithm designMichael T. Goodrich, Roberto Tamassia · 2001
Fundamentals of computer algorithmsEllis Horowitz · 1978
Fundamentals of data structures in CEllis Horowitz · 2008
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Prim's algorithm In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset…
- Johnson's algorithm Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. It allows some of the edge weights…
- Suurballe's algorithm In theoretical computer science and network routing, Suurballe's algorithm is an algorithm for finding two disjoint paths in a nonnegatively-weighted directed…
- Parallel single-source shortest path algorithm A central problem in algorithmic graph theory is the shortest path problem. One of the generalizations of the shortest path problem is known as the si…
- Floyd–Warshall algorithm In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm)…
- Bellman–Ford algorithm The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph…
- Graph traversal In computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph.…
- Contraction hierarchies In computer science, the method of contraction hierarchies is a speed-up technique for finding the shortest path in a graph. The most intuitive applications…