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...

Full description

Saved in:

Bibliographic Details
Main Author:	Hairulanuar, Nuralya Sofea
Format:	Thesis
Language:	English
Published:	2024
Subjects:	Algorithms
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!

id	my-uitm-ir.106015
record_format	uketd_dc
spelling	my-uitm-ir.1060152024-11-30T22:59:47Z A comparative study of greedy algorithms and dynamic programming in road network / Nuralya Sofea Hairulanuar 2024 Hairulanuar, Nuralya Sofea Algorithms 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. 2024 Thesis https://ir.uitm.edu.my/id/eprint/106015/ https://ir.uitm.edu.my/id/eprint/106015/1/106015.pdf text en public degree Universiti Teknologi MARA, Terengganu College of Computing, Informatics and Mathematics Salahudin, Nur Atikah
institution	Universiti Teknologi MARA
collection	UiTM Institutional Repository
language	English
advisor	Salahudin, Nur Atikah
topic	Algorithms
spellingShingle	Algorithms Hairulanuar, Nuralya Sofea A comparative study of greedy algorithms and dynamic programming in road network / Nuralya Sofea Hairulanuar
description	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.
format	Thesis
qualification_level	Bachelor degree
author	Hairulanuar, Nuralya Sofea
author_facet	Hairulanuar, Nuralya Sofea
author_sort	Hairulanuar, Nuralya Sofea
title	A comparative study of greedy algorithms and dynamic programming in road network / Nuralya Sofea Hairulanuar
title_short	A comparative study of greedy algorithms and dynamic programming in road network / Nuralya Sofea Hairulanuar
title_full	A comparative study of greedy algorithms and dynamic programming in road network / Nuralya Sofea Hairulanuar
title_fullStr	A comparative study of greedy algorithms and dynamic programming in road network / Nuralya Sofea Hairulanuar
title_full_unstemmed	A comparative study of greedy algorithms and dynamic programming in road network / Nuralya Sofea Hairulanuar
title_sort	comparative study of greedy algorithms and dynamic programming in road network / nuralya sofea hairulanuar
granting_institution	Universiti Teknologi MARA, Terengganu
granting_department	College of Computing, Informatics and Mathematics
publishDate	2024
url	https://ir.uitm.edu.my/id/eprint/106015/1/106015.pdf
_version_	1818588166650593280

A comparative study of greedy algorithms and dynamic programming in road network / Nuralya Sofea Hairulanuar

Similar Items