Teori Graf: Lintasan Terpendek, Jarak Terdekat

1. Permasalahan Awal

Masalah pencarian lintasan terpendek dalam graf merupakan salah satu bentuk optimasi. Graf yang digunakan adalah graf berbobot (weighted graph), yaitu graf yang setiap sisinya memiliki bobot positif. Bobot ini bisa merepresentasikan jarak, waktu, biaya, atau nilai lain tergantung konteks. Istilah "terpendek" di sini berarti meminimalkan total bobot lintasan, bukan selalu dalam arti panjang fisik.

Contoh penerapannya adalah:

• Jaringan transportasi antar kota: Titik mewakili kota, sisi mewakili jalan antar kota, dan bobot menyatakan jarak atau waktu tempuh. Jika terdapat beberapa lintasan antara dua kota, pencarian lintasan terpendek bertujuan menemukan jalur dengan waktu atau jarak minimum dari kota A ke kota B.

• Jaringan komunikasi komputer: Titik mewakili terminal komputer, sisi menyatakan saluran komunikasi antar terminal, dan bobot bisa berupa biaya komunikasi, waktu pengiriman pesan, atau jarak. Pencarian lintasan terpendek bertujuan mencari jalur komunikasi yang paling efisien dari segi waktu dan biaya antar dua terminal.

Secara umum, bentuk permasalahannya adalah mencari lintasan terpendek dari suatu titik ke titik lainnya.

2. Algoritma Dijkstra untuk Lintasan Terpendek (Shortest Path)

Dalam Algoritma Dijkstra, tujuannya adalah untuk menemukan jarak terpendek dari sebuah titik asal ke semua titik lain dalam graf. Karena titik asal adalah titik awal, jaraknya diinisialisasi menjadi nol. Dari sana, kita secara iteratif memilih titik yang belum diproses dengan jarak minimum dari asal. Untuk setiap titik u yang dipilih, kita memperbarui jarak ke tetangganya v menggunakan rumus: dist[v] = dist[u] + bobot[u][v], tetapi hanya jika jalur baru ini menawarkan jarak yang lebih pendek dari yang sudah diketahui saat ini. Proses ini terus berlanjut hingga semua titik selesai diproses.

Berikut ini algoritma Dijkstra

a. Pada awalnya belum ada titik masuk, beri bobot 0 untuk titik asal dan ∞ untuk titik lainnya.

b. Masukkan titik asal, update jarak untuk titik yang adjacent dengan titik asal, lalu masukkan titik dengan jarak terdekat.

c. Setiap kali setelah memasukkan titik u, jarak tempuh dari titik asal menuju v yang adjacent dengan u diupdate dengan memilih yang terdekat antara jarak sebelumnya dan jarak melalui u, dimana jarak melalui u adalah jarak dari titik asal menuju u ditambah bobot sisi (u, v).

d. Ulangi langkah (c) sampai semua titik masuk.

Sebagai contoh, perhatikan graf berikut:

akan ditentukan lintasan terpendek dari titik A ke titik lain menggunakan algoritma Dijkstra.

Mula-mula belum ada titik masuk, sehingga jarak untuk titik A yang merupakan titik asal adalah 0 dan titik-titik lainnya ∞.

Titik	A	B	C	D	E	F	G	H	I	J
Jarak	0	∞	∞	∞	∞	∞	∞	∞	∞	∞
Rute	A

Masukkan titik A, update jarak untuk titik yang adjacent dengan A

B = min(∞, 0 + 2) = 2, C = min(∞, 0 + 3) = 3

Titik	A	B	C	D	E	F	G	H	I	J
Jarak	0	2	3	∞	∞	∞	∞	∞	∞	∞
Rute	A	AB	AC

Titik A sudah masuk. Diantara titik-titik yang belum masuk, titik B memiliki jarak terdekat, yaitu 2. Masukkan titik B, update jarak untuk titik yang adjacent dengan B

D = min(∞, 2 + 4) = 6, E = min(∞, 2 + 5) = 7

Titik	A	B	C	D	E	F	G	H	I	J
Jarak	0	2	3	6	7	∞	∞	∞	∞	∞
Rute	A	AB	AC	ABD	ABE

Titik A dan B sudah masuk. Diantara titik-titik yang belum masuk, titik C memiliki jarak terdekat, yaitu 3. Masukkan titik C, update jarak untuk titik yang adjacent dengan C

D = min(6, 3 + 1) = 4, G = min(∞, 3 + 3) = 6

Titik	A	B	C	D	E	F	G	H	I	J
Jarak	0	2	3	4	7	∞	6	∞	∞	∞
Rute	A	AB	AC	ACD	ABE		ACG

Titik A, B, C sudah masuk. Diantara titik-titik yang belum masuk, titik D memiliki jarak terdekat, yaitu 4. Masukkan titik D, update jarak untuk titik yang adjacent dengan D

E = min(7, 4 + 7) = 7, F = min(∞, 4 + 6) = 10, G = min(6, 4 + 8) = 6

Titik	A	B	C	D	E	F	G	H	I	J
Jarak	0	2	3	4	7	10	6	∞	∞	∞
Rute	A	AB	AC	ACD	ABE	ACDF	ACG

Titik A, B, C, D sudah masuk. Diantara titik-titik yang belum masuk, titik G memiliki jarak terdekat, yaitu 6. Masukkan titik G, update jarak untuk titik yang adjacent dengan G

I = min(∞, 6 + 4) = 10

Titik	A	B	C	D	E	F	G	H	I	J
Jarak	0	2	3	4	7	10	6	∞	10	∞
Rute	A	AB	AC	ACD	ABE	ACDF	ACG		ACGI

Titik A, B, C, D, G sudah masuk. Diantara titik-titik yang belum masuk, titik E memiliki jarak terdekat, yaitu 7. Masukkan titik E, update jarak untuk titik yang adjacent dengan E

H = min(∞, 7 + 2) = 9

Titik	A	B	C	D	E	F	G	H	I	J
Jarak	0	2	3	4	7	10	6	9	10	∞
Rute	A	AB	AC	ACD	ABE	ACDF	ACG	ABEH	ACGI

Titik A, B, C, D, E, G sudah masuk. Diantara titik-titik yang belum masuk, titik H memiliki jarak terdekat, yaitu 9. Masukkan titik H, update jarak untuk titik yang adjacent dengan H

F = min(10, 9 + 1) = 10, J = min(∞, 9 + 6) = 15

Titik	A	B	C	D	E	F	G	H	I	J
Jarak	0	2	3	4	7	10	6	9	10	15
Rute	A	AB	AC	ACD	ABE	ACDF	ACG	ABEH	ACGI	ABEHJ

Titik A, B, C, D, E, G, H sudah masuk. Diantara titik-titik yang belum masuk, titik F dan I memiliki jarak terdekat, yaitu 10. Kita bisa memilih untuk memasukkan F atau I, misal Minfor memilih memasukkan titik F, update jarak untuk titik yang adjacent dengan F

I = min(10, 10 + 3) = 10

Titik	A	B	C	D	E	F	G	H	I	J
Jarak	0	2	3	4	7	10	6	9	10	15
Rute	A	AB	AC	ACD	ABE	ACDF	ACG	ABEH	ACGI	ABEHJ

Titik A, B, C, D, E, F, G, H sudah masuk. Diantara titik-titik yang belum masuk, titik I memiliki jarak terdekat, yaitu 10. Masukkan titik I, update jarak untuk titik yang adjacent dengan I

J = min(15, 10 + 5) = 15

Titik	A	B	C	D	E	F	G	H	I	J
Jarak	0	2	3	4	7	10	6	9	10	15
Rute	A	AB	AC	ACD	ABE	ACDF	ACG	ABEH	ACGI	ABEHJ

Titik A, B, C, D, E, F, G, H, I sudah masuk. Tersisa titik J yang belum masuk, masukkan titik J.

Titik	A	B	C	D	E	F	G	H	I	J
Jarak	0	2	3	4	7	10	6	9	10	15
Rute	A	AB	AC	ACD	ABE	ACDF	ACG	ABEH	ACGI	ABEHJ

Tabel terakhir ini menyatakan rute dan jarak terdekat dari A ke masing-masing titik.