An A* Algorithm with a New Heuristic Distance Function for the 2-Terminal Shortest Path Problem
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.2 pp.544-550
- Publication Date
- 2006/02/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e89-a.2.544
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kazuaki YAMAGUCHI, Sumio MASUDA, "An A* Algorithm with a New Heuristic Distance Function for the 2-Terminal Shortest Path Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E89-A, no. 2, pp. 544-550, February 2006, doi: 10.1093/ietfec/e89-a.2.544.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.2.544/_p
Copy
@ARTICLE{e89-a_2_544,
author={Kazuaki YAMAGUCHI, Sumio MASUDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An A* Algorithm with a New Heuristic Distance Function for the 2-Terminal Shortest Path Problem},
year={2006},
volume={E89-A},
number={2},
pages={544-550},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e89-a.2.544},
ISSN={1745-1337},
month={February},}
Copy
TY - JOUR
TI - An A* Algorithm with a New Heuristic Distance Function for the 2-Terminal Shortest Path Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 544
EP - 550
AU - Kazuaki YAMAGUCHI
AU - Sumio MASUDA
PY - 2006
DO - 10.1093/ietfec/e89-a.2.544
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2006
AB - 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.
ER -
English
