Lintasan Terpendek dengan Algoritma Dijkstra

Lintasan Terpendek dengan Algoritma Dijkstra

A.      Lintasan Terpendek (Shortest Path)

Persoalan dalam mencari lintasan terpendek ini sering terjadi dalam kehidupan sehari hari. Graft yang digunakan dalam pencarian lintasan terpendek adalah graft berbobot (weight graph), yaitu graft yang setiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graft dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos pembangunan, dan sebagainya.asumsi yang digunakan adalah bahwa semua bobot bernilai positif. Kata “terpendek” berarti meminimisasi bobot pada suatu lintasan di dalam graft.

Sampai saat ini, sudah banyak algoritma mencari lintasan terpendek yang pernah ditulis. Akan tetapi algoritma lintasan terpendek yang paling terkenal adalah algoritma dijkstra. Algoritma dijkstra pertama kali dikembangkan oleh E.W.Dijkstra yaitu seorang ilmuan computer berkebangsaan belanda yang pada perkembangannya menggunakan struktur data yang berbeda-beda, serta memakai strategi greedy, dimana pada setiap langkah dipilih sisi-sisi dengan bobot terkecil yang menghubungkan setiap simpul yang sudah terpilih dengan simpul lainnya.

Terdapat beberapa jenis persoalan lintasan terpendek, anatara lain:

1.      Lintasan terpendek antara dua simpul tertentu.

2.      Lintasan terpendek antara semua passangan simpul.

3.      Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.

4.      Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.

  B.  Persoalan tukang Pos Cina (Chinese Postman problem)

Permasalahan ini dikemukakan oleh Mei Gan (berasal dari China) pada tahun 1962.

Persoalannya adalah sebagai berikut: seorang tukang pos akan mengantarkan surat ke alamat-alamat sepanjang jalan di suatu daerah. Bagaimana ia merencanakan rute perjalanannya supaya ia melewati setiap jalan tepat sekali dan kembali lagi ke tempat awal keberangkatan.

Cara menentukan sirkuit Euler di dalam graf.

Lintasan yang dilalui tukang pos : A, B, C, D, E, F, C, E, B, F, A.