ANALISIS ALGORITMA DIJKSTRA DAN GREEDY PADA PENCARIAN JALUR TERPENDEK DI GRAF BERBOBOT

Abstrak

Penentuan jalur terpendek pada graf berbobot merupakan masalah penting dalam ilmu komputer, khususnya pada bidang jaringan dan sistem navigasi. Dua algoritma yang sering digunakan untuk menyelesaikan masalah ini adalah algoritma Dijkstra dan algoritma Greedy. Penelitian ini bertujuan untuk menganalisis kinerja kedua algoritma dalam menentukan jalur terpendek, berdasarkan studi literatur. Metode yang digunakan adalah pendekatan kualitatif melalui tinjauan pustaka dari jurnal, artikel ilmiah, dan buku referensi yang relevan. Hasil analisis menunjukkan bahwa algoritma Dijkstra memberikan hasil yang lebih optimal pada graf berbobot positif, sedangkan algoritma Greedy memiliki keunggulan dalam efisiensi waktu, meskipun tidak selalu memberikan solusi terbaik. Perbandingan ini disajikan dalam bentuk tabel untuk menunjukkan kelebihan dan kekurangan masing-masing algoritma. Kesimpulan dari penelitian ini menegaskan pentingnya pemilihan algoritma berdasarkan konteks aplikasi dan karakteristik graf yang digunakan.

Finding the shortest path in a weighted graph is a fundamental problem in computer science, especially in fields such as networking and navigation systems. Two widely used algorithms for solving this problem are Dijkstra's algorithm and the Greedy algorithm. This study aims to analyze the performance of both algorithms in determining the shortest path, based on a literature review. The method used is a qualitative approach through the analysis of journals, scientific articles, and relevant reference books. The analysis shows that Dijkstra's algorithm provides a more optimal result in positively weighted graphs, while the Greedy algorithm excels in execution speed, although it does not always yield the best solution. A comparison is presented in a table to illustrate the strengths and weaknesses of each algorithm. The conclusion emphasizes the importance of algorithm selection based on application context and graph characteristics.