Limits...
Algorithm for shortest path search in Geographic Information Systems by using reduced graphs.

Rodríguez-Puente R, Lazo-Cortés MS - Springerplus (2013)

Bottom Line: The use of Geographic Information Systems has increased considerably since the eighties and nineties.One of the most used heuristic algorithms is the A* algorithm, the main goal is to reduce the run time by reducing the search space.The results of finding the shortest path, applying the proposed algorithm, Dijkstra's algorithm and A* algorithm, are compared.

View Article: PubMed Central - PubMed

Affiliation: Universidad de las Ciencias Informáticas, Habana, Cuba.

ABSTRACT
The use of Geographic Information Systems has increased considerably since the eighties and nineties. As one of their most demanding applications we can mention shortest paths search. Several studies about shortest path search show the feasibility of using graphs for this purpose. Dijkstra's algorithm is one of the classic shortest path search algorithms. This algorithm is not well suited for shortest path search in large graphs. This is the reason why various modifications to Dijkstra's algorithm have been proposed by several authors using heuristics to reduce the run time of shortest path search. One of the most used heuristic algorithms is the A* algorithm, the main goal is to reduce the run time by reducing the search space. This article proposes a modification of Dijkstra's shortest path search algorithm in reduced graphs. It shows that the cost of the path found in this work, is equal to the cost of the path found using Dijkstra's algorithm in the original graph. The results of finding the shortest path, applying the proposed algorithm, Dijkstra's algorithm and A* algorithm, are compared. This comparison shows that, by applying the approach proposed, it is possible to obtain the optimal path in a similar or even in less time than when using heuristic algorithms.

No MeSH data available.


Related in: MedlinePlus

Two graph examples: (a) is a graph and (b) is a reduced graph from (a).
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3755817&req=5

Fig2: Two graph examples: (a) is a graph and (b) is a reduced graph from (a).

Mentions: G the graph of Figure 2(a).


Algorithm for shortest path search in Geographic Information Systems by using reduced graphs.

Rodríguez-Puente R, Lazo-Cortés MS - Springerplus (2013)

Two graph examples: (a) is a graph and (b) is a reduced graph from (a).
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3755817&req=5

Fig2: Two graph examples: (a) is a graph and (b) is a reduced graph from (a).
Mentions: G the graph of Figure 2(a).

Bottom Line: The use of Geographic Information Systems has increased considerably since the eighties and nineties.One of the most used heuristic algorithms is the A* algorithm, the main goal is to reduce the run time by reducing the search space.The results of finding the shortest path, applying the proposed algorithm, Dijkstra's algorithm and A* algorithm, are compared.

View Article: PubMed Central - PubMed

Affiliation: Universidad de las Ciencias Informáticas, Habana, Cuba.

ABSTRACT
The use of Geographic Information Systems has increased considerably since the eighties and nineties. As one of their most demanding applications we can mention shortest paths search. Several studies about shortest path search show the feasibility of using graphs for this purpose. Dijkstra's algorithm is one of the classic shortest path search algorithms. This algorithm is not well suited for shortest path search in large graphs. This is the reason why various modifications to Dijkstra's algorithm have been proposed by several authors using heuristics to reduce the run time of shortest path search. One of the most used heuristic algorithms is the A* algorithm, the main goal is to reduce the run time by reducing the search space. This article proposes a modification of Dijkstra's shortest path search algorithm in reduced graphs. It shows that the cost of the path found in this work, is equal to the cost of the path found using Dijkstra's algorithm in the original graph. The results of finding the shortest path, applying the proposed algorithm, Dijkstra's algorithm and A* algorithm, are compared. This comparison shows that, by applying the approach proposed, it is possible to obtain the optimal path in a similar or even in less time than when using heuristic algorithms.

No MeSH data available.


Related in: MedlinePlus