The Algebraic Algorithm for Solving the Path Planning Problem of a Weighted Directed Graph

Yan Ping Li; Kun Wei; Dan Wang

doi:10.4028/www.scientific.net/AMM.644-650.1648

Paper Titles

Research on Knowledge Resource Clustering Based on K-MEAN Algorithm
p.1629

Study on Model for Structural Reliability Based on Dynamic Interfering Theory
p.1633

A Novel Twin Support Vector Machines with Manifold Regularization
p.1640

The Special Form of Second Order Accuracy N-S Equations for Incompressible Fluid
p.1644

The Algebraic Algorithm for Solving the Path Planning Problem of a Weighted Directed Graph
p.1648

Approximation Analysis for a New Kind of Neural Network Using Rational Spline Weight Functions
p.1654

Complexity Analysis of Neural Network Based on Rational Spline Weight Functions
p.1658

A Clutter Suppression Algorithm for GPR Data Based on PCA Combining with Gradient Magnitude
p.1662

Construction of Asymmetric Quantum Product Codes Based Repeated-Root Cyclic Codes
p.1668

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 644-650The Algebraic Algorithm for Solving the Path...

The Algebraic Algorithm for Solving the Path Planning Problem of a Weighted Directed Graph

Abstract:

In this paper, an algebraic algorithm is developed with Min-algebra for the path planning problem of a simple weighted directed graph. According to the algebraic algorithm, the shortest path and its minimum steps will be concluded through the direct distance matrix A. Experimental results show that the algebraic algorithm is suitable for the path planning problem. The shortest path and its length can be gotten rapidly based on the proposed algorithm. Finally, the results are compared to those obtained by the conventional Dijkstra algorithm.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 644-650)

Pages:

1648-1653

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.644-650.1648

Citation:

Cite this paper

Online since:

September 2014

Authors:

Yan Ping Li*, Kun Wei, Dan Wang

Keywords:

Distance Matrix, Min-Algebra, Path Planning, Shortest Path, Weighted Directed Graph

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] G. Ying. Ai, T. Feng, Q. Song. Di: Operations Research. Beijing: Tsinghua University Press, pp.251-255. (2011).

Google Scholar

[2] Boris V. Cherkassky, Andrew V. Goldberg, Tomasz Radzik: Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming. 3: P. 129-174. (1996).

DOI: 10.1007/bf02592101

Google Scholar

[3] L. Feng, Zh. Cheng. hu, W. Qing: An Optimum Vehicular Path Algorithm for Traffic Network Based on Hierarchical Spatial Reasoning. Geo - spatial Information Science. 3(4): pp.36-42. (2000).

DOI: 10.1007/bf02829394

Google Scholar

[4] L. Feng: Shortest Path Algorithms: Taxonomy and Advance in Research. Journal of Geomatics Science and Technology. 3(30): pp.269-275. (2001).

Google Scholar

[5] G.E. Chao, L.L. Qun: The Optimal Path Algorithm Design Based on Bellman-Ford Algorithm. Bulletin of Surveying and Mapping. 8: pp.26-28. (2011).

Google Scholar

[6] B.P. Ming: A Optimization Algorithm Based on Dijkstra's Algorithm in Search of Shortcut. Computer Research and Development. 3(38): pp.307-311. (2001).

Google Scholar

[7] P. Hofner, B. Moller: Dijkstra, Floyd and Warshall meet Kleene. Formal Aspects of Computing. 24(4-6): pp.459-476. (2012).

DOI: 10.1007/s00165-012-0245-4

Google Scholar

[8] W.Y. Yan, Y.Z. Wei, C.H. Hu, P. Yun: Algorithm for Two-metric Unicast Shortest Path. Computer engineering. 3(33): pp.89-90. (2007).

Google Scholar

[9] W.Z. He, L. Yun: The Optimization and Implementation of the Shortest Path Dijkstra Algorithm. Software Time. 23(11-3): pp.275-277. (2007).

Google Scholar

[10] L.X. Qing, L.H. An, K.B. Sheng, Z.Z. Lian: Research on Parallelization of Shortest Path for Graph and its Application. Computer engineering and Applications. 48(14): pp.38-43. (2012).

Google Scholar

[11] L.Y. Chen, L.W. Qun: Analysis of the Shortest Route in Net Work on Dijkstra Algorithm. Microcomputer Applications. 3(25): pp.295-298. (2004).

Google Scholar