Improvement And Experimental Evaluation Bellman-Ford Algorithm

DOI

10.2991/icaicte.2013.29How to use a DOI?

Keywords

SPFA; Dijkstra; Bellman-Ford Algorithm

Abstract

The shortest path problem is the problem of finding a path between two vertices on a graph such that sum of the weights of its constituent edges is minimized.Simulations to compare the efficiencies for Dijkstra's algorithm, SPFA algorithm and improved Bellman-Ford were taken. The result shows that Dijkstra's algorithm, SPFA algorithm have almost same efficiency on the random graphs, the improved algorithm, although the improved algorithm is not desirable, on grid maps the proposed algorithm is very efficient. The proposed algorithm has reduced two-third times processing time than SPFA algorithm.

Copyright

© 2013, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Wei Zhang
AU  - Hao Chen
AU  - Chong Jiang
AU  - Lin Zhu
PY  - 2013/08
DA  - 2013/08
TI  - Improvement And Experimental Evaluation Bellman-Ford Algorithm
BT  - Proceedings of the 2013 International Conference on Advanced ICT and Education
PB  - Atlantis Press
SP  - 138
EP  - 141
SN  - 1951-6851
UR  - https://doi.org/10.2991/icaicte.2013.29
DO  - 10.2991/icaicte.2013.29
ID  - Zhang2013/08
ER  -