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
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.
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.