SPFA를 기반으로 개선된 벨만-포드 알고리듬 = An improved Bellman-Ford algorithm based on SPFA

다국어 초록 (Multilingual 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.

국문 초록 (Abstract)

이 논문에서 SPFA(shortest path faster algorithm)을 사용해서 기존의 벨만-포드(Bellman-Ford)을 개선한효율적인 알고리듬을 제안한다. 벨만-포드 알고리듬은 딕스트라(Dijkstra) 알고리듬과 다르게 부(-)인 가중치를갖는 그래프에서 사용할 수 있다. SPFA 알고리듬은 한 대기열을 이용하여 노드를 저장한다. 그래서 중북을피할 수 있다. 벨만-포드 알고리듬은 시간을 더 사용하여 노드 표를 업데이트를 시킨다. 이 개산 알고리듬에서는 인접 리스트를 이용하여 표의 각 노드를 저장한다. 한 대기열을 통하여 데이트를 저장한다. 개선 방법에서는 새로운 점에 계속 relaxation을 통하여 최적 패스를 얻을 수 있다. 딕스트라 알고리듬과 SPFA 알고리듬과개선된 알고리듬의 성능을 비교하기 위해서 시뮬레이션을 하였다. 실험 결과에서 랜덤(random) 그래프에서 개선된 알고리듬, SPFA 알고리듬과 딕스트라 알고리듬은 효율이 비슷했었는데, 격자형 지도에서 개선 알고리듬의 효율이 더 높았었다. 처리시간에서 개선된 알고리듬은 SPFA 알고리듬 보다 3분의 2를 감소시켰다.

참고문헌 (Reference)

1 서희종, "실시간 네트워크에서 개선된 분산 QoS 알고리듬" 한국전자통신학회 7 (7): 53-59, 2012

2 Wang. Kun, "Simultaneous Localization and Map Building Based on Improved Particle Filter in Grid Map" 2 : 963-966, 2011

3 William. Stallings, "Data and Computer Communications Eighth edition" Pearson Education International 332-347, 2007

4 Gao. Yang, "An Improved Shortest Route Algorithm in Vehicle Navigation System" 2 : 363-366, 1996

5 George T. Heineman, "Algorithm in a Nutshell" O'Reilly Media 322-, 2008

6 Duan. Fangding, "A Faster Algorithm for Shortest Path-SPFA" 29 (29): 207-212, 1994