Bidirectional Search Algorithm Based-On Index for Shortest Path Problem

The shortest path algorithm is the core problems in intelligent transportation system (ITS), especially for the large scale networks. The problem is classically solved by Dijkstra and Floyed algorithm. Meanwhile, many techniques are proposed to improve the algorithms heuristically. In most researche...

Full description

Saved in:
Bibliographic Details
Main Authors: Baolin Yi, Fan Yang, Haiquan Qiao, Chenwei Xu
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Artificial intelligence
Computer science
Computers
Heuristic algorithms
Indexes
Shortest path problem
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The shortest path algorithm is the core problems in intelligent transportation system (ITS), especially for the large scale networks. The problem is classically solved by Dijkstra and Floyed algorithm. Meanwhile, many techniques are proposed to improve the algorithms heuristically. In most researches, such techniques are considered individually. In this paper, we propose an improved shortest path algorithm called Bidirectional Search Algorithm Based-on Index(BSABI) for large scare network. The main idea of BSABI is that it considers a combination of Search Base-on Index and Bidirectional Search. Both analysis results and experimental results indicate the effectiveness of the proposed algorithm.
DOI:10.1109/CISE.2010.5676739