LAPORAN PRAKTIKUM

“STRATEGI DAN SIMULASI ALGORITMA”

OLEH

NAMA : AHMAD RIYADI

NIM : 1058411101824
KELAS : 3A INFORMATIKA

PROGRAM STUDI INFORMATIKA

FAKULTAS TEKNIK
UNIVERSITAS MUHAMMADIYAH MAKASSAR
2025
 PRAKTIKUM 5
“DJIKSTRA”
1. Materi Ringkas
A. Definisi
Algoritma Dijkstra adalah sebuah algoritma dalam ilmu komputer yang
digunakan untuk mencari jalur terpendek (shortest path) dari satu simpul
sumber ke simpul-simpul lain dalam suatu graf berbobot, dengan
ketentuan bahwa semua bobot sisi bernilai tidak negatif. Algoritma ini
bekerja secara bertahap dengan cara memilih simpul yang memiliki jarak
paling kecil dan belum diproses, kemudian memperbarui (relaksasi) jarak
ke simpul-simpul tetangganya jika ditemukan jalur yang lebih pendek.
Proses ini diulang sampai semua simpul telah dikunjungi atau jarak
terpendek ke simpul tujuan ditemukan. Algoritma Dijkstra banyak
digunakan dalam berbagai aplikasi, seperti sistem navigasi, pemetaan rute
jaringan komputer, dan perencanaan jalur transportasi, karena mampu
memberikan hasil yang efisien dan akurat untuk graf dengan bobot
positif.
B. Cara Kerja Dijkstra
Cara kerja algoritma Dijkstra dimulai dengan memilih satu simpul sebagai
sumber dan memberi jarak 0, sementara simpul lainnya diberi jarak tak
hingga. Algoritma kemudian memilih simpul dengan jarak terkecil yang
belum dikunjungi, menandainya sebagai telah diproses, lalu memperbarui
jarak simpul tetangganya jika ditemukan jalur yang lebih pendek.
Langkah ini diulang hingga semua simpul diproses atau tujuan tercapai,
sehingga diperoleh jarak dan jalur terpendek dari simpul sumber.
2. Langkah Pembuatan Program
A. Program 1
 Source Code

Gambar 5. 1 Source Code Dijkstra

 Program ini menggunakan algoritma Dijkstra untuk menentukan jarak
terpendek dari satu titik asal ke semua titik lain pada graf yang
direpresentasikan dalam bentuk matriks ketetanggaan, di mana nilai 0
menandakan tidak adanya jalur langsung dan nilai selain 0
menunjukkan bobot jarak. Awalnya, semua jarak diinisialisasi dengan
nilai sangat besar dan semua titik ditandai belum dikunjungi,
kemudian jarak titik asal diatur menjadi 0. Pada setiap iterasi,
algoritma memilih titik yang belum dikunjungi dengan jarak paling
kecil, menandainya sebagai sudah diproses, lalu mengevaluasi semua
titik tetangganya untuk memperbarui jarak jika ditemukan jalur yang
lebih pendek. Proses ini diulang hingga seluruh titik diproses, dan
hasil akhirnya ditampilkan sebagai jarak terpendek dari titik asal ke
setiap titik lainnya.

 Output

Gambar 5. 2 Output Dijkstra

Output tersebut menunjukkan hasil penerapan algoritma Dijkstra
untuk menghitung jarak terpendek dari satu titik asal (titik 0) ke
semua titik lainnya pada sebuah graf. Titik 0 memiliki jarak 0 karena
menjadi titik awal, sedangkan titik-titik lain memiliki jarak minimum
masing-masing, misalnya titik 1 berjarak 4, titik 7 berjarak 8, dan titik
4 berjarak 21. Nilai-nilai ini menandakan jarak terpendek yang
berhasil ditemukan algoritma setelah semua simpul diproses, sehingga
dapat disimpulkan bahwa program Dijkstra berjalan dengan benar
dalam menentukan jalur terpendek dari asal ke setiap tujuan.
3. Penjelasan
A. Tujuan Program
 Program 1
Tujuan algoritma Dijkstra adalah untuk menentukan jalur terpendek
yang paling optimal dari satu titik asal menuju satu atau seluruh titik
tujuan dalam suatu graf yang memiliki bobot sisi bernilai positif,
dengan cara meminimalkan total jarak, biaya, atau waktu tempuh.
Algoritma ini digunakan untuk membantu pengambilan keputusan
rute terbaik, seperti dalam pencarian jalur pada peta, perencanaan
jaringan komputer, sistem navigasi GPS, serta optimasi distribusi dan
logistik, sehingga perjalanan atau proses yang dilakukan menjadi lebih
efisien, cepat, dan hemat sumber daya.
B. Perhitunagn Manual

A B C D E F G H I
A A A4 A8
0

B B12 B15

C C19 C16 C14

D D28 E33

E E38

F F18

G G1 G24
9

H H15

Tabel 5.1 Tabel Perhitungan Manual

A B C I=4+8+2=14
C. Graff

Gambar 5.3 Graff

D. Iterasi

Node Jalur Hasil

0/A A 0
1/B A→B 4
2/C A→B→C 12
3/D A→B→C→D 19
4/E A→B→C→D→E 28
5/F A→B→C→F 16
6/G A→H→G 9
7/H A→H 8
8/I A→H→I 15

Tabel 5.2 Jalur Terpendek

 Iterasi 1
1) Pada simpul asal A dengan tujuan B bernilai 4 karena jarak antara A
ke B adalah 4.
 2) Pada simpul asal A dengan tujuan H bernilai 8 karena jarak antara
A ke H adalah 8

 Iterasi 2
1) Pada simpul asal B dengan tujuan C bernilai 12 karena jarak dari A
ke B adalah 4 ditambah jarak B ke C sebesar 8 sehingga total jarak
menjadi 12
2) Pada simpul asal B dengan tujuan H bernilai 15 karena jarak dari A
ke B adalah 4 ditambah jarak B ke H sebesar 11 sehingga total
jarak menjadi 15
 Iterasi 3
1) Pada simpul asal C dengan tujuan D bernilai 19 karena jarak dari A
ke C adalah 12 ditambah jarak C ke D sebesar 7 sehingga total
jarak menjadi 19
2) Pada simpul asal C dengan tujuan D bernilai 19 karena jarak dari A
ke C adalah 12 ditambah jarak C ke D sebesar 7 sehingga total
jarak menjadi 19
3) Pada simpul asal C dengan tujuan I bernilai 14 karena jarak dari A
ke C adalah 12 ditambah jarak C ke I sebesar 2 sehingga total jarak
menjadi 14
 Iterasi 4
1) Pada simpul asal D dengan tujuan E bernilai 28 karena jarak dari A
ke D adalah 19 ditambah jarak D ke E sebesar 9 sehingga total
jarak menjadi 28
2) Pada simpul asal D dengan tujuan F bernilai 33 karena jarak dari A
ke D adalah 19 ditambah jarak D ke F sebesar 14 sehingga total
jarak menjadi 33
 Iterasi 5
1) Pada simpul asal E dengan tujuan F bernilai 38 karena jarak dari
A ke E adalah 28 ditambah jarak E ke F sebesar 10 sehingga total
jarak menjadi 38
  Iterasi 6
1) Pada simpul asal F dengan tujuan G bernilai 18 karena jarak dari
A ke F adalah 16 ditambah jarak F ke G sebesar 2 sehingga total
jarak menjadi 18
 Iterasi 7
1) Pada simpul asal G dengan tujuan H bernilai 19 karena jarak dari
A ke G adalah 18 ditambah jarak G ke H sebesar 1 sehingga total
jarak menjadi 19
2) Pada simpul asal G dengan tujuan I bernilai 24 karena jarak dari
A ke G adalah 18 ditambah jarak G ke I sebesar 6 sehingga total
jarak menjadi 24
 Iterasi 8
1) Pada simpul asal H dengan tujuan I bernilai 15 karena jarak dari A
ke H adalah 8 ditambah jarak H ke I sebesar 7 sehingga total jarak
menjadi 15

E. Perbandingan Program Dan Perbandingan Manual

Node Program Manual Perbandingan
0/A 0 0 Sama
1/B 4 4 Sama
2/C 12 12 Sama
3/D 19 19 Sama
4/E 21 28 Beda
5/F 11 16 Beda
6/G 9 18 Beda
7/H 8 8 Sama
8/I 14 14 Sama

Tabel 5.2 Tabel Perbandingan

4. Kesimpulan
Dapat saya simpulkan bahwa algoritma Dijkstra terbukti mampu menentukan
jarak terpendek dari satu titik asal ke seluruh titik tujuan pada graf berbobot
positif secara sistematis dan efisien. Melalui implementasi program dan
perhitungan manual, dapat dipahami bahwa proses pemilihan simpul dengan
jarak minimum serta relaksasi jarak ke simpul tetangga menjadi kunci utama
dalam memperoleh hasil jalur terpendek. Hasil keluaran program menunjukkan
jarak minimum yang sesuai dengan konsep dasar algoritma Dijkstra, sehingga
praktikum ini membantu meningkatkan pemahaman mahasiswa terhadap cara
kerja, tujuan, serta penerapan algoritma Dijkstra dalam menyelesaikan
permasalahan pencarian rute terpendek pada berbagai bidang seperti navigasi
dan jaringan komputer