PTI Returns

24 03 2009

Another PTI task…
Kali ini tugasnya adalah mencari tahu mengenai dua algoritma untuk mencari jarak terpendek, Bellman-Ford dan Warshall (setelah dicari-cari ternyata nama aslinya Floyd-Warshall… penemuan algoritma-algoritma ini butuh dua orang tampaknya!)

Algoritma pertama, algoritma Bellman-Ford. Pada dasarnya cara kerjanya seperti ini.

Pertama node asal diberi nilai jarak 0, node lainnya diberi tanda tak hingga sebagai tanda jarak dari node asal.

Kedua, lakukan hal berikut hingga n-1 kali (di mana n adalah jumlah node):
Anggap uv adalah edge dari node u ke v. Apabila jarak v (dari node asal) lebih besar dari jarak u (dari node asal) ditambah dengan besar edge uv, maka jarak v menjadi jarak u ditambah besar edge uv. Proses ini disebut relax edges.

Ketiga, apabila ditemukan jarak sebuah node (dari node asal) lebih besar dari jarak node yang bertetanggaan dengannya ditambah jarak sisi ketetanggaannya, maka dalam graf itu terdapat lintasan bernilai negatif.

Graph Used for Bellman-Ford Example

Graph Used for Bellman-Ford Example

Contohnya adalah graf pada gambar di atas. Langkah awal adalah memberikan nilai 0 pada node asal (dalam hal ini adalah A) dan inf (infinite) pada node lain, sebagai tanda jarak dari node asal.

Penyelesaian langkah ke-2 adalah sebagai berikut:
A=0
B s/d D=inf
=============1
A=0
B=15
C=3
D=inf
E=5

=============2
A=0
B=14
C=3
D=9
E=5
=============3
A=0
B=13
C=3
D=9
E=5
=============4
A=0
B=13
C=3
D=9
E=5

Langkah ketiga dilakukan untuk mengecek ada tidaknya lintasan negatif, yakni pengecekan lintasan yang berhubungan dengan masing-masing node tujuan, apakah ada lintasan yang bernilai lebih sedikit dari nilai jarak (dari asal) node tersebut. Dalam graf di atas, tidak ditemukan lintasan negatif.

Pada dasarnya algoritma Bellman-Ford dan Djikstra punya kemiripan, namun secara teoritis algoritma Bellman-Ford dapat mendeteksi adanya lintasan bernilai negatif, sedangkan Djikstra tidak. Walau begitu, algoritma Djikstra memiliki waktu pengerjaan yang lebih sedikit [wiki].

Algoritma kedua: algoritma Floyd-Marshall.

Cara kerja algoritma ini terkesan lebih rumit dari dua algoritma sebelumnya. Misalkan tujuannya adalah mencari lintasan terkecil dari i ke j. Lintasan terkecil ini diasumsikan melalui sebuah node k. Maka kemungkinan lintasan terkecilnya ada dua: lintasan antara i dan j yang didapat sebelumnya; atau lintasan i sampai k ditambah lintasan k hingga j.

Algoritma ini dapat disingkat dalam rumus berikut:
shortestPath(i,j,k)=min(shortestPath(i,j,k),shortestPath(i,k,k-1)+shortestPath(k,j,k-1);

Perhatikan bahwa algoritma ini dapat dijadikan sebagai fungsi rekursif!

Memakai graf dalam contoh sebelumnya, dibuatlah sebuah matriks ketetanggaan:
mtx_bellmanPerhatikan bahwa terdapat node yang tidak dapat berhubungan, diberi tanda ‘x’. Tanda ‘i’ berarti berhubungan tapi tidak bertetangga (melalui node lain).

Sekarang, misalkan kita ingin mencari lintasan A~D terpendek. Maka rumusnya menjadi:
shortestPath(A,D,k)=min(shortestPath(A,D,k), shortestPath(A,k,k-1)+shortestPath(k,D,k-1));

Dalam penjelasan yang sederhana, dibandingkan antara nilai lintasan terpendek sebelumnya (i, jika melihat matriks di atas) dan nilai lintasan A~D dengan C atau A atau E sebagai k , tapi misalkan Cdirumuskan sebagai shortestPath(A,E,C-1)+shortestPath(C,D,C-1) di mana C-1 adalah node yang terhubung antara lintasan A~C.  Ternyata node C-1 terdapat tiga, yakni C sendiri, A, dan E.

Pengerjaan dengan k lain pada dasarnya dilakukan, namun dalam contoh ini cukup C sebagai k saja, pada akhirnya C sebagai k adalah yang terpendek dan tetap dijadikan sebagai nilai acuan.

Kemudian pada shortestPath(C,D,C-1), node C-1 yang memenuhi adalah C. Perhatikan bahwa shortestPath(C,D,C-1) adalah fungsi juga sehingga dalam fungsi shortestPath(A,D,k), terdapat fungsi lagi… fungsi yang seperti ini disebut rekursif.

Pada akhirnya shortestPath(A,D,k)=min(i,A~C+C~D)=min(i,9)=9.

Walau terkesan rumit, ternyata algoritma Floyd-Marshall sangat efesien karena dalam praktiknya, bila dimasukkan dalam pemrograman, algoritma ini berupa rekursif.

============

Hoahem…. Zzz…

Iklan

Aksi

Information

5 responses

17 04 2009
setuju-man

what’s your intention? inform all the readers that you have no interest in this topic? (refers to your Z’s at the end of post)

21 04 2009
wuhugm

Why must I stuff my head with these incomprehensible stuffs when I can just use the latest simulator programs to ease my jobs……… :swt:

21 04 2009
agpisfrick

What jobs?

30 04 2009
wuhugm

jobs as in gigolo’s jobs 😀

25 06 2009
Jaya

I think this is a good post..
actually i have a problem about bellman ford.. and your post describe me everything..
Thank you.. 😀

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s




%d blogger menyukai ini: