SPFA 를기반으로개선된벨만 - 포드알고리듬 SPFA 를기반으로개선된벨만 - 포드알고리듬 진호 * 서희종 ** An improved Bellman-Ford algorithm based on SPFA Hao Chen * Hee-Jong Suh ** 요약 이논문에서 SPFA(shortest path faster algorithm) 을사용해서기존의벨만-포드 (Bellman-Ford) 을개선한효율적인알고리듬을제안한다. 벨만-포드알고리듬은딕스트라 (Dijkstra) 알고리듬과다르게부 (-) 인가중치를갖는그래프에서사용할수있다. SPFA 알고리듬은한대기열을이용하여노드를저장한다. 그래서중북을피할수있다. 벨만-포드알고리듬은시간을더사용하여노드표를업데이트를시킨다. 이개산알고리듬에서는인접리스트를이용하여표의각노드를저장한다. 한대기열을통하여데이트를저장한다. 개선방법에서는새로운점에계속 relaxation을통하여최적패스를얻을수있다. 딕스트라알고리듬과 SPFA 알고리듬과개선된알고리듬의성능을비교하기위해서시뮬레이션을하였다. 실험결과에서랜덤 (random) 그래프에서개선된알고리듬, SPFA 알고리듬과딕스트라알고리듬은효율이비슷했었는데, 격자형지도에서개선알고리듬의효율이더높았었다. 처리시간에서개선된알고리듬은 SPFA 알고리듬보다 3분의 2를감소시켰다. ABSTRACT In this paper, we proposed an efficient algorithm based on SPFA(shortest path faster algorithm), which is an improved the Bellman-Ford algorithm. The Bellman-Ford algorithm can be used on graphs with negative edge weights unlike Dijkstra's algorithm. And SPFA algorithm used a queue to store the nodes, to avoid redundancy, though the Bellman-Ford algorithm takes a long time to update the nodes table. In this improved algorithm, an adjacency list is also used to store each vertex of the graph, applying dynamic optimal approach. And a queue is used to store the data. The improved algorithm can find the optimal path by continuous relaxation operation to the new node. Simulations to compare the efficiencies for Dijkstra's algorithm, SPFA algorithm and improved Bellman-Ford were taken. The result shows that Dijkstra's algorithm, SPFA algorithm have almost same efficiency on the random graphs, the improved algorithm, although the improved algorithm is not desirable, on grid maps the proposed algorithm is very efficient. The proposed algorithm has reduced two-third times processing time than SPFA algorithm. 키워드 SPFA, Bellman-Ford, Shortest path problem, Routing SPFA, 벨만 - 포드, 최단경로문제, 라우팅 Ⅰ. Introduction The shortest path search in a graph is studying for long time to minimize the sum of the weights of its constituent edges, and has been very important in computer, communication and transportation network. etc, as the shortest path routing. In a packet switching network, the primary function * 전남대학교전자통신공학과 (chenhaock@hotmail.com) ** 전남대학교전자통신공학과 (hjsuh@jnu.ac.kr) 접수일자 : 2012. 06. 21 심사 ( 수정 ) 일자 : 2012. 07. 26 게재확정일자 : 2012. 08. 09 721
한국전자통신학회논문지제 7 권제 4 호 is to accept packets from a source station and deliver them to a destination station through the path. Routing consists of two basic tasks. The first task is to collect the state information and keep it up-to-date. The second task is to find a satisfactory path for a new connection based on the collected information[1]. Most least cost routing algorithms used in the networks and Internet are variation of one of two algorithms, known as Dijkstra's algorithm and Bellman-Ford algorithm[2]. The Bellman-Ford algorithm solves the shortest path problem, together with the Dijkstra's algorithm. This algorithm is less restrictive condition on the graph, compared to Dijkstra's algorithm. And, the time complexity of the Bellman-Ford is, and the time complexity of Dijkstra's algorithm is, where and are the number of vertices and edges respectively[3]. To improve solving this problem, the SPFA (shortest path faster algorithm) had been proposed, but it was an improved Bellman-Ford algorithm[4]. Its time complexity is, where is a constant. In sparse graph, the time complexity of SPFA algorithm is far less. But this algorithm requires more time in order to move the new nodes. In this paper, a relaxation method is used for the new node, and the implementation of algorithm has been continuously iterated. And an optimized SPFA algorithm is proposed. The result of the experiment shows that the proposed algorithm has better performance, than SPFA algorithm and Dijkstra's algorithm. In Chapter Ⅱ, SPFA algorithm is explained. In Chapter Ⅲ there is an optimized SPFA algorithm by improving the search method. In Chapter Ⅳ, there are the comparisons of the proposed algorithm with SPFA and Dijkstra's algorithm by experiments. Chapter Ⅴ provides conclusions. Next is references. Ⅱ. Related Algorithm In a digraph, a set is used to denote the adjacency list of the. The weight of each edge is used to establish the adjacency list. An array set store the current value of the shortest path from the source node to the remaining nodes. Each element of the array is initialized to maximum value. After running SPFA algorithm, the set output the shortest path value of each node. The graph for SPFA algorithm is expressed as an adjacency list, and to search the shortest path a dynamic optimal approach is applied. A FIFO queue is used to store the vertex to be optimized. When optimization, a node is removed from the queue, and a current path with the node is used to optimize the value of path with another node. If adjusted, the value of the will be getting smaller, the node will be added to the queue to be further optimized. Repeatedly the nodes from the queue is removed to optimize the current shortest path. Until the queue is empty, re-optimization will be done though searching a unnecessary shortest path. At that time, array has stored the value of the shortest path from the source node to the other nodes. SPFA algorithm: for each in do for each do read ; Read the weight of each edge to the adjacency list. ; Initialize each vertex whether the flag array into the queue. ; Initialize the shortest path array to the maximum 722
SPFA 를기반으로개선된벨만 - 포드알고리듬 value. end; ; ; The source node into the queue. ; From the source node to itself, the value is zero. while Queue not empty do ; Removed a node from the queue. ; After a node is removed, its flag array instead of zero. It means the node is not in the queue. for each do if then Judge the path from the node w to the node j is shorter than the original path, optimize the path with node j. if then ; ; When the node is node in the queue, the flag of instead of one. It means is the node is in the queue. end end end; for each in do write ; end; Optimization is complete, the array D is stored the shortest path that from the source node to each node. The result will be output. end. End of the algorithm. The time complexity of SPFA algorithm is, where is a constant. First in initialization of SPFA algorithm the weight of each edge is read. In this case there will be a time complexity is. The sum of out-degree of the vertexes is the edges. For one node, the average out-degree is. Execution time is. Set the number of vertices that is added the queue, the average of each node is added the queue once, ; the average of each node is added to the queue twice,. is a constant, it has noting to do with and. So the time complexity of SPFA algorithm is. Fig. 1 Search method of SPFA algorithm SPFA algorithm uses a FIFO queue to store the nodes. A node is removed from the first of the queue. The node is relaxed successfully, a new node will be added at the end of the queue to be further optimized. Repeatedly the node is removed to optimize the current shortest path, until the queue is empty. Fig.1 shows search method of SPFA algorithm. Ⅲ. Improving the Search Method 723
한국전자통신학회논문지제 7 권제 4 호 The data structure of the proposed algorithm also uses adjacency list as SPFA algorithm. In our algorithm, an adjacency list structure is used significantly to save memory space and reduce searching time[5]. An important property is the triangle inequality. Set is a digraph with weights. a node is the source node, and for any node, is the shortest path that from to. For all edges, is a sufficient and necessary condition for for the shortest path from to. The proposed algorithm uses relaxation operation. First set is the shortest path of node. Assignment,. Then, For, Relax If, It means that if each edge do not satisfies the triangle inequality, the destination node will be re-assigned. The essential of relaxation operation is an search constantly looking for conflicting between current state and target state. Adjustment of status is done until no conflicting. After that time, the optimal state is reached. If the Bellman-Ford algorithm is used, actually only one node is updated with each iteration, and other loops are invalid. The Bellman-Ford algorithm is inefficiency, because there are a lot of unnecessary operations. It is only when the node is updated in the last iteration that will be useful for current iteration. The proposed algorithm takes advantage of storage, using the queue optimization. Its key is to store useful state only. When the queue extent a new node, it is added at the end of the queue. The iteration is continued. This process required more time in order to move the new nodes. In order to relax the new node, an implementation of the algorithm can have an iterated. Fig. 2 Improving the search method of SPFA algorithm. Fig. 2. shows improving the search method of SPFA algorithm. The method that at the first node. By the improved algorithm, the node 1 is first removed from the queue. After the node is relaxed successfully, and a new node will be searched directly. All nodes are relaxed, until the queue is empty. Ⅳ. Results of Experiment To verify our idea, experiments were taken on large amounts of data. First, the experiment of random maps. Dijkstra's algorithm solves the graphs with only non-negative edge weights. So in the case of negative edge weights, there is a comparison of the proposed algorithm with SPFA. In the case of non-negative edge weights, there is a comparison of the proposed algorithm with SPFA and Dijkstra's algorithms. Times(ms) 9000 8000 7000 6000 5000 4000 3000 2000 1000 SPFA Proposed algorithm Dijkstra 몊 0-2 -1.5-1 -0.5 0 0.5 1 1.5 2 Edges x 10 6 Fig. 3 Comparison of three algorithms (SPFA algorithm, the proposed algorithm and Dijkstra's algorithm) on random data. 724
SPFA 를기반으로개선된벨만 - 포드알고리듬 As shown in Fig. 3, when the size of the graphs module is randomly generated, the proposed algorithm is not desirable, because it will keep iterated if a graph is great depth. It does too many times to iterate. SPFA and Dijkstra's algorithms have almost same efficiency. Grid map is widely used because it is easy to build and maintain without definite geometric parameters.[6] Keeping iterated is characteristic of the proposed algorithm. Consequently, it is used on grid maps. milliseconds that reduced two-third in time consumption. So the proposed algorithm is more effective on grid maps. We could see that on grid maps the proposed algorithm is very efficient, and the proposed algorithm than SPFA algorithm reduced two-third in time consumption by Matlab. This may broaden the development space for the proposed algorithm in the future. References Times(ms) 2.5 x 104 2 1.5 1 0.5 SPFA Proposed algorithm 0 0 1 2 3 4 5 Edges 6 7 8 9 10 x 10 5 Fig. 4 Comparison of two algorithms (SPFA algorithm, the proposed algorithm) on grid maps. In Fig. 4, we can see clearly the relationship between the proposed and SPFA algorithms. In both case, SPFA algorithm takes 31048 milliseconds, the proposed algorithm only takes 8898 milliseconds that reduced two-third in time consumption. We used Intel P7350 2.00 GHz, window 7(32 bits). [1] 서희종, " 실시간네트워크에서개선된분산 QoS 알고리듬, " 한국전자통신학회논문지," 7 권, 1 호, pp. 53-60, 2012. [2] William. Stallings, "Data and Computer Communications Eighth edition," Pearson Education International, pp. 332-347, 2007. [3] George T. Heineman, "Algorithm in a Nutshell," O'Reilly Media, pp. 322, Oct. 2008. [4] Duan. Fangding, "A Faster Algorithm for Shortest Path-SPFA," Journal of Southwest JIAOTONG University, Vol. 29, No. 6, pp. 207-212, Apr. 1994. [5] Gao. Yang, "An Improved Shortest Route Algorithm in Vehicle Navigation System," International Conference on Advanced Computer Theory and Engineering (ICACTE), Vol. 2, pp. 363-366, Aug. 1996. [6] Wang. Kun, "Simultaneous Localization and Map Building Based on Improved Particle Filter in Grid Map," International Conference on Electronic and Mechanical Engineering and Information Technology, Vol. 2, pp. 963-966, Aug. 2011. Ⅴ. Conclusions The experimental results show that SPFA algorithm and Dijkstra' algorithm have almost same efficiency on the random graphs(fig. 3). But on grid maps the proposed algorithm is very efficient. As shown in Fig. 4, SPFA algorithm takes 31048 milliseconds, the proposed algorithm only takes 8898 저자소개진호 (Hao Chen) 2010년복경석유화공학원통신공학과졸업 ( 공학사 ) 현재전남대학교대학원전자통신공학과 ( 석사과정 ) 관심분야 : 라우팅, 코딩 725
한국전자통신학회논문지제 7 권제 4 호 서희종 (Hee-Jong Suh) 1975년한국항공대학교항공통신공학과졸업 ( 공학사 ) 1996년중앙대학교대학원전자공학과졸업 ( 공학박사 ) 1980년 2006년여수대학교전자통신공학과교수 2006년 현재전남대학교전자통신공학과교수 관심분야 : 컴퓨터네트위크, 인터넷통신, 위성통신 726