Djojo, Michael Alexander and Karyono, Kanisius (2014) Computational load analysis of Dijkstra, A*, and Floyd-Warshall algorithms in mesh network. In: International Conference on Robotics, Biomimetics, Intelligent Computational Systems, 25-27 Nov. 2013, Jogjakarta, Indonesia.
Full text not available from this repository.Abstract
The exchange of information requires the shortest path route to optimize data transmission process. The complexity of the shortest path algorithm becomes important because of the device processing power and memory limitation. This study compared Dijkstra algorithm, A* algorithm and Floyd-Warshall algorithm in term of the time, the computational load and memory usage. OMNeT++ network simulator is used to map the vertices and edge into a collection of nodes and channels that are interconnected. Mesh topology is used in this study to represent a real network conditions. Each edge in the mesh network has a value so as to form a weighted graph. The complexity of the route will be proportional to the scale of the mesh network. Based on the simulation, the value of computational load and simulation time are proportional to the square of the number of nodes for all simulated algorithms. The results show that A* algorithm has smaller computational load and simulation time than the other algorithms without affecting the shortest route results. Dijkstra algorithm performs better in term of memory usage. The Floyd-Warshall algorithm is the worst of all simulated algorithm, because all data channel weights needs to be processed using a multi level loop operation.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Keywords: | shortest path , dijkstra , a* , floyd-warshall , computional load |
| Subjects: | 500 Science and Mathematic > 530 Physics > 537 Electricity and Electronics |
| Divisions: | Faculty of Engineering & Informatics > Electrical Engineering |
| Depositing User: | Administrator UMN Library |
| Date Deposited: | 08 Dec 2021 08:13 |
| Last Modified: | 02 May 2023 02:25 |
| URI: | https://kc.umn.ac.id/id/eprint/19388 |
Actions (login required)
 |
View Item |
