A Review of Prim and Genetic Algorithms in Finding and Determining Routes on Connected Weighted Graphs
Andysah Putera Utama Siahaan, Mhd. Furqan · 2018
Searching for the shortest route when traveling is something that needs to be done in addition to finding the destination city. The reason for finding the shortest route is to summarize the trip and save travel costs. Another issue in making a useful trip is city tracing done by a salesperson, where a salesperson must visit several places to distribute goods, so he will only stop at that place once until the last place to be reached is reached until returning to his place of origin. The Prim algorithm is used to find the minimum generator tree from a weighted connected graph by taking the side/segment that has the smallest weight of the graph, where the line segment is side by side with the stretched tree that has been created, and that does not form a cycle. Genetic algorithms are also a method used to solve an optimal solution search problem in an optimization problem. This algorithm follows the genetic process of biological organisms based on Charles Darwin's theory of evolution. The implementation of genetic algorithms can be tested in finding the optimal route solution on a graph. Based on the results of genetic testing algorithms have different results on each test. It is because genetic algorithms use random numbers to generate probabilities for each generation. The results of the research describe Prim's algorithm better than Genetics because it has consistent results. It is not seen in the Genetic algorithm that expects opportunities from random numbers to appear. However, Genetic algorithms are excellent algorithms when applied to extensive cases because this algorithm will determine the optimal route of all possible routes.