An A^* Algorithm with a New Heuristic Distance Function for the 2-Terminal Shortest Path Problem (Algorithms and Data Structures)

スポンサーリンク

概要

• 論文の詳細を見る

• The 2-terminal shortest path problem is to find a shortest path between two specified vertices in a given graph G. In this paper, we consider this problem in the following situation: G is given before the two vertices are specified so that some preprocessing is allowed to reduce the response time. We present a method for calculating lower bounds of the length of the shortest path for any pair of vertices. Experimental results show that the A^* algorithm with our method performs much better than previous methods.

• 社団法人電子情報通信学会の論文
• 2006-02-01

著者

• Masuda Sumio

  The Department Of Electrical And Electronics Engineering Kobe University

• Yamaguchi Kazuaki

  The Department Of Electrical And Electronics Engineering Kobe University

関連論文

• A Representation Diagram for Maximal Independent Sets of a Graph(Special Section on Discrete Mathematics and Its Applications)
• An A^* Algorithm with a New Heuristic Distance Function for the 2-Terminal Shortest Path Problem (Algorithms and Data Structures)

スポンサーリンク