Live briefing
Everything about Parallel single-source shortest path algorithm
Computational problem of graph theory
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 single-source-shortest-paths (SSSP) problem, which consists of finding the shortest paths from a source vertex to all other vertices in the graph. There are classical sequential algorithms which solve this problem, such as Dijkstra's algorithm. In this article, however, we present two parallel algorithms solving this problem. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Parallel single-source shortest path algorithmA 5-minute orientation
- Pick up a classic book: Introduction to AlgorithmsThe most-reprinted book on the subject
- Read the landmark paper: A Randomized Parallel Algorithm for Single-Source Shortest PathsCited 59 times
- Go sideways: Bellman–Ford algorithmA closely related topic
- Go sideways: Distance (graph theory)A closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
A Randomized Parallel Algorithm for Single-Source Shortest Paths
Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems
A Parallel Algorithm Template for Updating Single-Source Shortest Paths in Large-Scale Dynamic Networks
Parallel algorithms for the single source shortest path problem
A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs
Parallel Implementation of Single-Source Shortest Path Algorithm Based on Haloop
A Study of Different Parallel Implementations of Single Source Shortest Path Algorithms
Searching in parallel: a case study with the single-source shortest path algorithm
📚 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
- 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…
- Distance (graph theory) In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph…
- Dijkstra's algorithm Dijkstra's algorithm (/ˈdaɪk.strəz/, DYKE-strəz) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent…
- 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…
- Topological sorting In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge…
- 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…
- 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…
- Brandes' algorithm In network theory, Brandes' algorithm is an algorithm for calculating the betweenness centrality of vertices in a graph. The algorithm was first published…