• Proposal
Our proposal for the final project is to define the cheapest way of travelling to a destination. Using one of the programming languages, we analyse which algorithm is suitable for finding the destination.
• Introduction
– Background
The final project of analysis of algorithm the choices we choose is finding a cheapest way or shortest path of finding a destination by using minimum spanning tree algorithms. Prim’s and Kruskal’s algorithm work different although it works the same In Kruskal’s algorithm it begins with an edge, select an edge in increasing order and works in connected and disconnected graph. While Prim’s algorithm starts with a node, edge moves from one node to another and restricted on connected graph
– Problem Description
Find the minimum spanning tree of the cheapest way of finding a destination from the dataset. The dataset we use a TV network route to find the shortest way of finding it.
• Related Work
The MST of Prim’s and Kruskal’s Algorithm that we use to solve the problem is similar to the shortest path by using Dijkstra’s and Bellman’s Ford algorithm.
• Implementation
− Formal description of the problem
We will use two algorithm’s: Prim’s and Kruskal’s to find out the minimum spanning tree using a dataset to connect every tv in the city so that once the network get interrupted the program could cut the connection a problem and get a minimum cost weighted perfect matching.
− Design of Algorithm
− Proof of Correctness
The algorithm can’t check when the result is out of range or when the file is not found while running the program.
– Complexity analysis
Vertices: 25
Edges: 600
Time Complexity by using large data:
Undirected GraphsΘ(E Log V) : 69.45 seconds
Prim’s AlgorithmΘ(V log E) : 838.76 seconds
Kruskal’s Algorithm(E log E) : 1666.89 seconds
Space Complexity by using large data:
Undirected GraphsΘ(E Log V) : 625 seconds
Prim’s AlgorithmΘ(V log E) : 625 seconds
Kruskal’s Algorithm(E log E) : 625 seconds
• Evaluation
− Theoretical analysis of the algorithms
While running the program, the result from the theoretical algorithm differs from the complexity analysis. Because the theoretical algorithm uses the real life time of finding a large data compare to running it in a program.
− Implementation Details
Finding the MST of Prim’s and Kruskal’s Algorithm.
− Data Sets
The Data Sets is using all the possible TV network route(KM) of all the city in Indonesia.
− Experimental Analysis
It runs well without an error and shows the complete algorithm of Kruskal’s and Prim’s.
− Results
There are two option you can choose between Kruskal’s or Prim’s. There will be two different results which both of them have their own unique results. The results is graph which find the lowest minimum cost for the chosen option.The third option shows the undirected graph which shows the default graph of the datasets.
• Discussion
We choose Transjakarta as the first choice by using the shortest path but then, we get to choose MST because many people experiencing a trouble for their TV that wont connect to the network.
• Conclusion and Recommendation
In conclusion, we know how to solve the MST and how we get the idea of implementing the algorithm. It’s based on TV network route cable that shows MST to find the best route.
• Program execution:
Code of the main file
Code of the MST Algorithms
CSV of the TV network route cable
Choose between the four choices to solve the problem: Undirected graph, Prim’s, Kruskal’s or Exit to end the program
By Choosing Undirected Graph
By Choosing Prim’s Algorithm
By Choosing Kruskal’s Algorithm
• Demo application:
• Git Website:
https://github.com/FarizGaharu/Analysis_of_Algorithm_FP
• References:
Siva, Vivek. “Minimum Spanning Tree Tutorials & Notes | Algorithms.” HackerEarth Blog, 2012, www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/.
Alinds Transport. “Informasi / Table Jarak antar Kota di Jawa”.Sewamobiljogja,2002,
www.sewamobiljogja.info/informasi-table-jarak-antar-kota-di-jawa.
Members
- Jason Erniody(2101693510)
- Fariz Ihsan Yasid(2101677091)
- Alfi Mohamed Redzwan(2101693574)
Recent Comments