A comparative study of greedy algorithms and dynamic programming in road network / Nuralya Sofea Hairulanuar
This study provides an in-depth analysis of four well-known algorithms which are Dijkstra's algorithm, A* algorithm, Floyd Warshall, and Bellman Ford in the context of optimizing road networks. The research assesses the efficiency, accuracy, and appropriateness of these algorithms for different...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://ir.uitm.edu.my/id/eprint/106015/1/106015.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | This study provides an in-depth analysis of four well-known algorithms which are Dijkstra's algorithm, A* algorithm, Floyd Warshall, and Bellman Ford in the context of optimizing road networks. The research assesses the efficiency, accuracy, and appropriateness of these algorithms for different kinds of networks, with a specific focus on their use in optimizing travel routes within the road network of Terengganu, Malaysia. Dijkstra's algorithm and A* algorithm have been shown to be very efficient for solving single-source shortest route problems. A* Algorithm, in particular, excels in situations when quick response times are needed, due to its heuristic-based approach. The Floyd Warshall Algorithm, despite its high computing complexity, has shown its benefits in solving all-pairs shortest route problems in smaller networks. The Bellman Ford algorithm is notable for its capability to manage graphs with negative weights, however it is less efficient than Dijkstra's algorithm for graphs with non-negative weights. In addition, the research examined the efficiency of travel time and found that travelling in the early morning typically results in more efficient routes compared to travelling in the midday and afternoon. |
|---|