In the last article we briefly introduced what is the graph traversal algorithm, this article will introduce the single source shortest path algorithm (SSSP algorithm) commonly used in the graph calculation.
In the international Graph500 rankings released on July 1, “Tianhe” was ranked first in the SSSPGraph500 (Single Source Shortest Path) list and the BIGDataGreenGraph500 (Big Data Graph Computing Energy Efficiency) list. This article introduces the common shortest path algorithm of SSSP.
The single-source shortest path algorithm (SSSP) computs a classical problem in graph theory, giving the shortest path length from a given node (called the source node) to the remaining nodes. SSSP is applicable to network routing and path design. Both Bellman-Ford algorithm and Dijkstra algorithm are algorithms for solving the shortest paths of graphs.
The characteristics of Dijkstra algorithm are mainly based on the starting point as the center of the outer layer expansion until the extension to the end point. Dijkstra algorithm adopts the greedy strategy. Its basic algorithm idea is to specify the starting point S and introduce two sets S and U. S is used to record the vertices that have found the shortest path, while U contains the vertices that have not found the shortest path. The system is constantly finding the vertices with the shortest path, and moving them out of the U set and into the S set. Initially, S is the empty set, and the U set contains all vertices. The system executes continuously. After traversing all vertices, the U set is updated to the empty set, and the task ends.
The principle of Bellman-Ford algorithm is to relax continuously and update each edge at each relaxation. If it can be updated after n-1 relaxation, it means that there is a negative loop in the graph, so the result cannot be obtained. Otherwise, the task is completed. The Bellman-Ford algorithm first calculates the estimate of the shortest distance of all vertices except the source point, and then performs a relaxation operation for each edge in the edge set, so that the estimate of the shortest distance of each vertex from the source point gradually approximates its actual shortest distance.
The above is an introduction to two simple single-source shortest path algorithms. It is not difficult to find that Dijkstra focuses on point-based scanning (until all points are marked), while Bell-Ford focuses on edg-based relationships (until no updates occur), which is also the difference between the two designs. Interested friends can implement both algorithms and experience their differences, and I recommend graphScope as a platform for this purpose. Graphscope is the world’s first one-stop super-large-scale distributed graph computing platform developed and open source by The intelligent computing laboratory of Alitama Institute. It supports a variety of graph algorithms, which can easily carry out graph analysis and calculation, and also achieves extreme performance. On the LDBC GraphAnalytics Benchmark for graph analysis testing, GraphScope leads the way in almost all combinations of algorithms and data sets compared to PowerGraph and other latest systems. As you can see from the figure below, GraphScope takes 0.52 seconds to perform the single-source shortest path algorithm (SSSP algorithm), much less than PowerGraph’s 6.48 seconds.
GraphScope posted in github.com/alibaba/graphscope for open source code, you can be directly deployed trial installation.