Shortest Path Problem
The shortest path problem involves finding the shortest path between two vertices (or nodes) in a graph. Algorithms such as the Floyd-Warshall algorithm and different variations of Dijkstra's algorithm are used to find solutions to the shortest path problem. Applications of the shortest path problem include those in road networks, logistics, communications, electronic design, power grid contingency analysis, and community detection.
Shortest Path Problem
Variations of the Shortest Path Problem
- Single-source shortest path (or SSSP) problem requires finding the shortest path from a source node to all other nodes in a weighted graph i.e. the sum of the weights of the edges in the paths is minimized.
- Breadth-first search (or BFS) is finding the shortest path from a source node to all other nodes in an unweighted graph i.e. the number of edges in the paths is minimized. Breadth-first search is a core primitive for graph traversal and a basis for many higher-level graph analysis algorithms. Algorithms for analyzing sparse relationships represented as graphs provide crucial tools in many computational fields ranging from genomics to electronic design automation to social network analysis.
- All-pairs shortest path (or APSP) problem requires finding the shortest path between all pairs of nodes in a graph.
- Single-source widest path (or SSWP) problem requires finding the path from a source node to all other nodes in a weighted graph such that the weight of the minimum-weight edge of the path is maximized.
Betweenness Centrality
Betweenness Centrality (BC) is an important, closely related concept to shortest path algorithms. It determines the importance of vertices in a network by measuring the ratio of shortest paths passing through a particular vertex to the total number of shortest paths between all pairs of vertices. BC is a popular analytic that determines vertex influence in a graph. It has many practical use cases, including finding the best locations for stores within cities, power grid contingency analysis, and community detection. For a detailed description of how CUDA and NVIDIA GPUs can be used to accelerate the BC computation, please refer to "Accelerating Graph Betweenness Centrality" technical blog post.
Accelerating shortest path algorithms with GPUs
The NVIDIA Graph Analytics library (nvGRAPH) comprises of parallel algorithms for high performance analytics on graphs with up to 2 billion edges. It supports both single source shortest path and single source widest path algorithms. The nvGRAPH library is freely available as part of the CUDA Toolkit. For more information about graphs, please refer to the Graph Analytics page.
Additional Resources:
- "Scalable GPU Graph Traversal" Duane Merrill. Published in: 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 1 Feb 2012.
- "Fast Spectral Graph Partitioning on GPUs" Naumov, Maxim. Parallel For All. NVIDIA, 12 May 2016.
- "Gunrock", a GPU accelerated library for BFS.