Evaluation of Route Finding Methods in GIS Application
3-Effective Parameters on the Shortest Path Algorithms
Four parameters that effect on shortest path algorithms are Network Representations, Labeling Method, Selection Rules and Data Structures (Zhan and Noon, 1996). These parameters effect on shortest path algorithms performance and cause to be developed different kind of algorithms.
3-1-Network Representations
The way in which an input network is represented and implemented in a shortest path algorithm is vital to the performance of the algorithm.There are several straightforward ways of representing a general network for computational purposes. Past research has proven that the Forward Star representation is the most efficient data structure for representing networks (Gallo and Pallottino, 1988). Two sets of arrays are used in the forward star data structure. The first array is used to store data associated with arcs, and the second array is used to store data related to nodes. All arcs of a network in question are maintained in a list and are ordered in a specific sequence. That is, arcs emanating from nodes 1, 2, 3, ..., are ordered sequentially. Arcs emanating from the same node can be ordered arbitrarily, however. All information associated with an arc, such as starting node, ending node, cost, arc length and capacity are stored with the arc in some way (e.g., corresponding arrays or linked lists).
3-2-Labeling Method
The labeling method is a central procedure in most shortest path algorithms(Gallo and Pallottino, 1988). The output of the labeling method is an out-tree from a source node, s, to a set of nodes. This out-tree is constructed iteratively, and the shortest path from s to i is obtained upon termination of the method. Three pieces of information are maintained for each node i in the labeling method while constructing a shortest path tree: the distance label, d(i), the parent node, p(i), and the node status, S(i). The distance label, d(i), stores the upper bound of the shortest path distance from s to i during iteration. Upon termination of an algorithm, d(i) represents the unique shortest path from s to i. The parent node p(i) records the node that immediately precedes node i in the out-tree. The node status, S(i), can be one of the following: unreached, temporarily labeled and permanently labeled. When a node is not scanned during the iteration, it is unreached. Normally the distance label of an unreached node is set to positive infinite. When it is known that the currently known shortest path of getting to node i is also the absolute shortest path we will ever be able to attain, the node is called permanently labeled. When further improvement is still expected to be made on the shortest path to node i, node i is considered only temporarily labeled. It follows that d(i) is an upper bound on the shortest path distance to node i if the node is temporarily labeled; and d(i) represents the final and optimal shortest path distance to node i if the node is permanently labeled.
3-3-Selection Rules and Data Structures
The performance of a particular shortest path algorithm partly depends on how the basic operations in the labeling method are implemented. Two aspects are particularly important to the performance of a shortest path algorithm: 1) the strategies used to select the next temporarily labeled node to be scanned, and 2) the data structures utilized to maintain the set of labeled nodes (Ahuja et ah,1993).
Strategies commonly used for selecting the next temporarily labeled node to be scanned are FIFO (First In First Out): the oldest node in the set of temporarily labeled nodes is selected first in this search strategy, LIFO (Last In First Out): the newest node in the set of temporarily labeled nodes is selected first in this search strategy, BFS (Best-First-Search): the minimum distance label from the set of temporarily labeled nodes is considered as the best node (Gallo and Pallottino, 1988).
A number of data structures can be used to manipulate the set of temporarily labeled nodes in order to support these strategies.These data structures include arrays, singly and doubly linked lists, stacks, buckets and queues (Sedgewick,1990). A singly linked list contains a collection of elements. Each element has a data field and a link field. The data field contains information to be stored, and the link field contains a pointer pointing to the next element in the list.A doubly linked list contains two pointers. One pointer points to the previous element in the list, and another pointer points to the next element in the list. Stack is another special type of list which only allows removal and addition of an element at one end of the list. The bucket data structure is related to the double bucket implementations of the Dijkstra algorithms. Buckets are sets arranged in a sorted fashion. Bucket k stores all temporarily labeled nodes whose distance labels fall within a certain range. A queue is related to the Graph Growth algorithms.The queue is a special type of list which allows the addition of an element at the tail and the deletion of an element at the head (Ahuja,1993).
4- Reviewing of Algorithm Theories
In this section we breifly review implementation senarios for Dijkstra's Algorithm, Huristic Methods and Genetic Algorithm.