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

Rewrite rule example. On the left side is the graph Gi = ({vr1}, {}), on the right side is the graph Gj = ({v1, v2, v3}, {(v1, v2), (v2, v1), (v2, v3)}) and on the bottom is the embedding information ψout.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig3: Rewrite rule example. On the left side is the graph Gi = ({vr1}, {}), on the right side is the graph Gj = ({v1, v2, v3}, {(v1, v2), (v2, v1), (v2, v3)}) and on the bottom is the embedding information ψout.

Mentions: Therefore, the graph of Figure 2(b) is obtained. In addition, the rewrite rules are created. The graph Gi of the rewrite rule is Gi = ({vr1},{}) (see left of Figure 3), the graph Gj is created with the vertices of the class of Pi, represented by vri, and edges among them on G, as is presented on the right side of Figure 3. Once we created graphs Gi and Gj, the embedding information (ψin and ψout) must be specified, as is described in the specification of the reduction algorithm.Figure 3


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

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

Rewrite rule example. On the left side is the graph Gi = ({vr1}, {}), on the right side is the graph Gj = ({v1, v2, v3}, {(v1, v2), (v2, v1), (v2, v3)}) and on the bottom is the embedding information ψout.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig3: Rewrite rule example. On the left side is the graph Gi = ({vr1}, {}), on the right side is the graph Gj = ({v1, v2, v3}, {(v1, v2), (v2, v1), (v2, v3)}) and on the bottom is the embedding information ψout.
Mentions: Therefore, the graph of Figure 2(b) is obtained. In addition, the rewrite rules are created. The graph Gi of the rewrite rule is Gi = ({vr1},{}) (see left of Figure 3), the graph Gj is created with the vertices of the class of Pi, represented by vri, and edges among them on G, as is presented on the right side of Figure 3. Once we created graphs Gi and Gj, the embedding information (ψin and ψout) must be specified, as is described in the specification of the reduction algorithm.Figure 3

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