Algoritma Dijkstra dan Floyd-Warshall (PHP)


Lumayan, nie ilmu buat nambah Logika yang bakalan berguna di pemprograman, tipe analis. dimana berfungsi dalam penentuan keputusan, simak dulu deh tentan algoritma berikut.

Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.

Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graphG dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.

Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v.

Algoritma Floyd-Warshal

Algoritma Floyd-Warshall memiliki input graf berarah dan berbobot (V,E), yang berupa daftar titik (node/vertex V) dan daftar sisi (edge E). Jumlah bobot sisi-sisi pada sebuah jalur adalah bobot jalur tersebut. Sisi pada E diperbolehkan memiliki bobot negatif, akan tetapi tidak diperbolehkan bagi graf ini untuk memiliki siklus dengan bobot negatif. Algoritma ini menghitung bobot terkecil dari semua jalur yang menghubungkan sebuah pasangan titik, dan melakukannya sekaligus untuk semua pasangan titik.

Contoh :

Dari Titik F Menuju Titik  C ada berapa cara :

(|F|A|B|C) —>91Km

(|F|A|D|C) —>107Km

(|F|A|F|E|D|C) —>114Km

(|F|A|F|E|D|C) —>114Km

(|F|E|D|C) —>80Km

(|F|E|D|C) —>80Km

Nah, dengan algoritma Flody ini , kita dapat mendapatkan informasi yang sedemikian rupa untuk kita timbang dan menentukan jalur yang paling efisien.

PERBEDAAN

1. Algoritma Dijkstra yang menerapkan prinsip greedytidak selalu berhasil memberikan solusi optimumuntuk kasus penentuan lintasan terpendek (single pairshortest path).

2. Algoritma Floyd-Warshall yang menerapkanpemrograman dinamis lebih menjamin keberhasilanpenemuan solusi optimum untuk kasus penentuanlintasan terpendek (single pair shortest path).

Nah.. Kemudian apa sie kegunaan kedua algoritma tersebut ? ya.. mereka digunaka untuk memabntu dalam menetukan keputusan, manakah yang paling cepat dan mana yang paling efisien, dengan demikian algoritma tersebtu dapat kita gunakan dalam salah satu contoh PPC. dimana kita dapat menentukan waktu, titik kritis dan macam sebagainya.

contoh contoh pengaplikasiannya
1. Himpunan kandidat, C
Himpunan ini berisi elemen-elemen yang memiliki peluang untuk membentuk solusi. Pada persoalan lintasan terpendek dalam graf, himpunan kandidat ini  adalah himpunan simpul pada graf tersebut.
2.Himpunan solusi, SHimpunan ini berisi solusi dari permasalahan yangdiselesaikan dan elemennya terdiri dari elemendalam himpunan kandidat namun tidak semuanyaatau dengan kata lain himpunan solusi ini adalahupabagian dari himpunan kandidat.
3. Fungsi seleksiFungsi seleksi adalah fungsi yang akan memilihsetiap kandidat yang yang memungkinkan untukmenghasilkan solusi optimal pada setiap langkahnya.
4. Fungsi kelayakanFungsi kelayakan akan memeriksa apakah suatukandidat yang telah terpilih (terseleksi) melanggarconstraint atau tidak. Apabila kandidat melanggarconstraint maka kandidat tidak akan dimasukkan kedalam himpunan solusi.
5. Fungsi objektifFungsi objektif akan memaksimalkan ataumeminimalkan nilai solusi. Tujuannya adalahmemilih satu saja solusi terbaik dari masing-masinganggota himpunan solusi.
Seperti biasa :: Contoh source algoritma floyd-Warshall dalam Bentuk PHP dapat di minta dengan kirim email ke vendiaz_cossin@yahoo.com.
atau download di SINI
HARAP ILMU INI DAPAT BERGUNA :: diaz ::
Algoritma Dijkstra dan Floyd-Warshall (PHP)

16 thoughts on “Algoritma Dijkstra dan Floyd-Warshall (PHP)

  1. charisma says:

    wi wi wi wi ….
    kalo,
    saya baca2 kok hampir sama ya…
    n kenapa harus dikasih nama yang berbeda
    perbedaan paling mendasar selain waktu running apa yah… dalam pencarian jalur terpendek nya

    1. diazscript says:

      ya.. pada intinya sama. hanya nanti pada penyeleksiannya berbeda. kalo udah paham yang warshal. otomatis pasti udah paham yang djikstra

  2. kalo floyd buat graf berarah gmn gan? trus tu napa berulang2 ya gan nemu solusinya? macem contoh tu yg dr F ke C, F|E|D|C –> 80 knapa ke baca 2x?
    kalo buat graf yg vertexnya dikit mungkin ga mslh, tp ntar klo udah ke kasus dengan vertex yg lbh bnyk lgi bkl jdi mslh besar tuh..

      1. haha.. maaf jg, kmrn ntu ane lgi rada stres bikin program pke dijkstra ma floyd. 2-2nya hasilnya error.. skrng c uda nemu solusi bwt yg dijkstra. tp yg floyd masih belom.. kbr2in ya gan kalo nemu solusi ^^

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s