A comparative analysis of Prim, Kruskal, and Reverse-Delete algorithms in optimizing routes within Terengganu’s and Pahang’s attraction road network / Munashahira Mohammad Zahid
This paper presents a detailed comparison of three greedy algorithms—Prim, Kruskal, and Reverse-Delete—in optimizing the routes within Terengganu’s and Pahang’s attraction road network. The goal is to determine the most effective algorithm for constructing the minimum spanning tree (MST) that minimi...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://ir.uitm.edu.my/id/eprint/106184/1/106184.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | This paper presents a detailed comparison of three greedy algorithms—Prim, Kruskal, and Reverse-Delete—in optimizing the routes within Terengganu’s and Pahang’s attraction road network. The goal is to determine the most effective algorithm for constructing the minimum spanning tree (MST) that minimizes total travel distance. Prim’s algorithm builds the MST by starting from an arbitrary node and continually adding the smallest edge that connects a vertex in the tree to a vertex outside the tree. Kruskal’s algorithm, on the other hand, constructs the MST by sorting all the edges and adding the smallest edge to the tree, as long as it doesn’t form a cycle. The Reverse-Delete algorithm works in reverse; it starts with the full graph and iteratively removes the largest edges, ensuring that the graph remains connected. This study meticulously evaluates each algorithm’s computational efficiency, implementation complexity, and performance in generating optimal routes. |
|---|