Dalam teori graf, masalah jalur terpendek merupakan suatu masalah pencarian jalur antara dua verteks sedemikian sehingga jumlah bobot dari busur penyusunnya adalah minimum. Masalah jalur terpendek ini salah satunya dapat ditemui pada jaringan data, yakni proses routing pada saat pengiriman data dari node sumber ke node tujuan. Terdapat beberapa algoritma atau metode yang dapat memecahkan masalah jalur terpendek ini, pada skripsi ini akan dibahas penerapan algoritma genetika yang didasarkan prinsip evolusi biologi dalam penyelesaian jalur terpendek. Operator dasar yang digunakan pada skripsi ini adalah roda roulette untuk reproduksi, order crossover untuk crossover, dan insertion mutation untuk mutasi. Kinerja algoritma genetika akan diuji dengan menggunakan data dari OR-Library. Berdasarkan hasil percobaan diperoleh bahwa algoritma genetika cukup baik untuk digunakan dalam penyelesaian masalah jalur terpendek. Selain itu, ditunjukkan bahwa perubahan nilai parameter algoritma genetika ternyata mempengaruhi kinerja algoritma genetika dalam memperoleh solusi.

---

In graph theory, shortest path problem is a problem of finding a path between two vertices such that the total cost of the constituent edges is minimum. Shortest path problem can be found in data networks, namely routing process, when transmitting data from a source node to a destination node. There are several algorithms or methods that can solve this problem. In this final project, genetic algorithm based on principles of evolutionary biology is used to solve it. The basic operator for the genetic algorithm that used are the roulette-wheel for reproduction, order crossover, and insertion mutation. The performance of the genetic algorithm will be applied by using data from OR-Library. Based on the experiment result, the genetic algorithm is good enough to solve the shortest path problem. In addition, changes in values of parameters will affect the performance of the genetic algorithm in obtaining a solution.