1
I PENDAHULUAN 1.1
Latar Belakang
Permasalahan seperti jaringan komunikasi, transportasi, penjadwalan, dan pencarian rute kini semakin banyak ditemui di tengah-tengah masyarakat. Masalah tersebut dimulai dari menemukan jarak yang paling optimal, hingga mencari biaya minimum perjalanan. Dengan menggunakan metode dan teori yang berkembang saat ini, berbagai masalah tersebut bisa dicari solusinya. Salah satu teori yang terkenal adalah teori graf. Aplikasi dalam teori graf sangat luas karena dalam teori graf banyak sekali metode yang bisa digunakan dengan kondisi yang bermacammacam. Salah satu permasalahan graf yang terkenal adalah Chinese Postman Problem (CPP). Masalah CPP pertama kali dikemukakan oleh Meigu Guan, seorang pakar matematika dari Universitas Shangtun, Cina, yang sehariharinya menggunakan sebagian dari waktu luangnya untuk bekerja di kantor pos pada waktu revolusi kebudayaan Cina. “Tukang pos harus melewati semua sektor yang ditugaskan kepadanya sebelum kembali ke kantor pos. Permasalahannya adalah bagaimana menentukan jarak terpendek untuk tukang pos tersebut” Guan (1962) di dalam Eiselt et al. (1995). Dalam kasus ini, permasalahan yang muncul adalah bagaimana menentukan jarak minimum dengan kondisi setiap ruas jalan harus dilewati paling tidak satu kali. Pada dasarnya CPP memiliki banyak jenis yaitu undirected CPP (CPP yang tidak berarah), directed CPP (CPP yang berarah), dan mixed CPP (CPP gabungan antara tidak berarah dan berarah). Dalam perkembangannya ternyata masalah CPP ini bisa diaplikasikan tidak hanya dalam pengiriman pos saja, tetapi dalam hal lainnya seperti pengumpulan sampah berdasarkan rute
terpendeknya, pemindahan salju dengan biaya yang minimum, penentuan rute tercepat untuk bis sekolah, dll. CPP dapat dipandang sebagai masalah penentuan sirkuit Euler pada digraf yang balance. Sirkuit Euler dijamin ada jika digrafnya adalah digraf balance. Dalam karya ilmiah ini akan dibahas prosedur untuk mencari sirkuit Euler pada digraf yang tidak balance, dengan terlebih dahulu menjadikan digraf tersebut menjadi digraf balance dan kemudian menyelesaikannya dengan menggunakan dua macam algoritme. 1.2 Tujuan Penulisan Tujuan dari penulisan karya ilmiah ini meliputi: 1. mempelajari penyelesaian masalah penentuan sirkuit Euler pada graf berarah dengan menggunakan algoritme Fleury dan algoritme van Aardenne-Ehrenfest de Bruijn. 2. mengaplikasikan masalah pencarian sirkuit Euler ke dalam masalah penentuan rute pengambilan sampah. 1.3 Metode Penulisan Metode yang digunakan dalam penulisan karya ilmiah ini adalah studi literatur. Materi dari karya ilmiah ini diambil dari jurnal yang berjudul Arc Routing Problem, part I: The Chinese Postman Problem yang disusun oleh H. A. Eiselt, G. Michel dan L. Gilbert pada tahun 1995. Di samping itu dalam pembuatan karya ilmiah ini, penulis menggunakan beberapa bahan penunjang dari buku dan situs internet yang terkait dengan topik karya ilmiah ini.
II LANDASAN TEORI Dalam bab ini akan dibahas tentang teoriteori yang berkaitan dengan bahasan karya ilmiah ini.
tentang teori graf. Dalam periode yang sangat singkat, teori graf kini mengalami perkembangan yang sangat pesat.
2.1 Graf dan Digraf
Definisi 1 (Graf) Suatu graf G adalah pasangan terurut (V,E) dengan V atau biasa disebut V(G) adalah himpunan berhingga dan takkosong dari elemen graf yang disebut verteks (node, point), sedangkan E atau biasa disebut E(G)
Teori graf pertama kali dikenal sejak Euler (1736) meneliti tentang masalah jembatan Königsberg. Dua abad kemudian 1900-an, baru untuk pertama kalinya dibuat buku
2
adalah himpunan pasangan yang menghubungkan dua elemen subset dari V yang disebut sisi (edge, line). Setiap sisi {u,v} pada V biasanya dinotasikan dengan uv atau vu. Banyaknya verteks dari suatu graf disebut order dan banyaknya sisi pada suatu graf disebut size. (Chartrand & Zhang 2009) G:
w x v y u Gambar 1 Graf G = (V, E). Pada Gambar 1 diperlihatkan bahwa V = {u, v, w, x, y} dan E = {{u,v},{v,w},{v,x},{x,y}}. Definisi 2 (Graf berarah/digraf) Graf berarah (digraph) D adalah pasangan terurut (V,A) dengan V himpunan takkosong yang hingga, dan A himpunan pasangan terurut yang menghubungkan elemen-elemen di V. Elemen-elemen dari A disebut sisi berarah (arc). Sisi berarah (u,v) dinyatakan dengan garis berarah dari u ke v. (Chartrand & Zhang 2009)
D: u
v w
G:
z u
7
29
x
89
12
v Gambar 3 Graf berbobot. Bobot tiap sisi untuk graf pada Gambar 3 adalah: wuv=12, wvz=29, wzx=7, wvx=89. Definisi 4 (Multigraf/multidigraf) Suatu graf (digraf) dikatakan multigraf (multidigraf) bila graf (digraf) tersebut memiliki lebih dari satu sisi (sisi berarah) yang incident dengan satu pasang verteks. (Foulds 1992)
Ilustrasi multigraf dapat dilihat pada Gambar 4 berikut. G: u
v w
x
Gambar 4 Multigraf. Gambar 4 merupakan contoh multigraf karena verteks u dan w dihubungkan oleh lebih dari satu sisi. Ilustrasi multidigraf bisa dilihat pada Gambar 5 berikut. D:
z
x
Gambar 2 Graf berarah D = (V, A). Pada Gambar 2 diperlihatkan bahwa V = {u, v, w, x} dan A = {(u,w),(v,w),(w,x)}. Definisi 3 (Graf/digraf berbobot) Suatu graf G = (V,E) atau digraf D = (V,A) dikatakan berbobot jika terdapat sebuah fungsi w : E → R atau A : A → R (dengan R adalah himpunan bilangan real) yang memberikan sebuah bilangan real pada setiap sisi di E atau sisi berarah di A, disebut bobot. Setiap bobot w(uv) dengan uv ∈ E atau uv ∈ A dinotasikan dengan wuv. (Foulds 1992)
v
t
w
u x
y
Gambar 5 Multidigraf.
Definisi 5 (Adjacent dan incident) Misalkan u dan v verteks pada graf G. Verteks v dikatakan tetangga (adjacent) dari u jika ada sisi e yang menghubungkan verteks u dan v, yaitu e = uv. Himpunan semua tetangga dari verteks v dinotasikan dengan N(v). Jika e = uv adalah sisi pada graf G maka e dikatakan incident dengan verteks u dan v. (Chartrand & Zhang 2009)
3
G:
u
e1 e3
e2
e4
e5
x
Definisi 9 (Unicursal) Suatu graf tidak berarah dikatakan unicursal jika setiap verteks pada graf tersebut memiliki derajat yang genap. (Diestel 1997) G:
v
w
Gambar 6 Adjacent dan incident. Ilustrasi adjacent dan incident diperlihatkan pada Gambar 6. Verteks u adjacent dengan verteks v dan x tetapi verteks u tidak adjacent dengan verteks w. Verteks u incident dengan sisi e1, tetapi verteks w tidak incident dengan sisi e1. Definisi 6 (Derajat /degree) Derajat suatu verteks v adalah banyaknya sisi yang incident dengan verteks v, dan dinotasikan dengan degG(v) atau deg v atau d(v). (Vasudev 2006) y G:
w u
x
Gambar 8 Ilustrasi graf unicursal. Pada Gambar 8 diperlihatkan grafnya unicursal karena tiap verteks memiliki derajat yang genap. Definisi 10 (Balance) Suatu digraf D dikatakan balance jika digraf tersebut pada setiap verteksnya memiliki δ(vi) = 0, dengan δ(vi) adalah selisih dari derajat masuk dengan derajat keluar dari verteks i. (Diestel 1997) D:
z
v Gambar 9 Ilustrasi digraf balance.
Gambar 7 Ilustrasi derajat pada graf. Pada Gambar 7 terlihat bahwa d(u) = 1 = d(z), d(w) = 2 =d(x), d(v) = 3=d(y). Definisi 7 (Derajat masuk/in-degree) Pada graf berarah, in-degree suatu verteks vi , yang dinotasikan dengan d–(vi), adalah banyaknya sisi berarah yang berakhir di verteks vi. (Vasudev 2006)
Pada Gambar 2 diperlihatkan derajat masuk tiap verteksnya d–(u) = 0, d–(v) = 0, d–(x) = 1, d–(w) = 2 Definisi 8 (Derajat keluar/out-degree) Pada graf berarah, out-degree suatu verteks vi, yang dinotasikan dengan d+(vi), adalah banyaknya sisi berarah yang dimulai dari verteks vi. (Vasudev 2006)
Pada Gambar 2 diperlihatkan derajat keluar tiap verteksnya d+(x) = 0, d+(u) = 1 = d+(v) = d+(w).
Pada Gambar 9 diperlihatkan grafnya balance karena setiap verteks vi memiliki δ(vi) = 0. Definisi 11 (Underlying graph) Jika suatu graf G didapat dengan cara menghapus semua arah dari sisi berarah pada digraf D, maka graf G tersebut adalah underlying graph dari digraf D. (Vasudev 2006)
Ilustrasi underlying graph bisa dilihat dari Gambar 8 dan Gambar 9. Graf pada Gambar 8 merupakan underlying graph dari digraf pada Gambar 9. Definisi 12 (Jalan /walk) Walk W pada suatu graf G adalah barisan berhingga, W = viejvi+1ej+1...ekvm atau W = vi vi+1 - ... - vm yang dimulai dari suatu verteks dan berakhir pada suatu verteks juga, sehingga setiap sisi di dalam barisan harus incident dengan verteks sebelum dan sesudahnya. (Chartrand & Zhang 2009)
4
Ilustrasi walk pada suatu graf bisa dilihat pada Gambar 6, W = u e2 x e5 w e4 v e3 x adalah walk pada graf G.
Ilustrasi path berarah bisa dilihat pada Gambar 10, P = u e1 v e4 w e5 x adalah path berarah.
Definisi 13 (Walk berarah) Walk berarah pada suatu digraf D adalah walk yang sesuai dengan arah sisinya atau tidak berlawanan arah. (Vasudev 2006) D: u v e1
Definisi 18 (Tertutup) Walk pada suatu graf G dikatakan tertutup (closed) jika walk tersebut dimulai dan diakhiri pada verteks yang sama. (Chartrand & Zhang 2009)
e2
e3
e4
e5 x w Gambar 10 Graf berarah. Ilustrasi walk berarah pada suatu digraf D bisa dilihat pada Gambar 10. W = u e1 v e4 w adalah walk berarah. Definisi 14 (Lintasan) Lintasan (trail) pada suatu graf adalah walk dengan semua sisi dalam barisannya tidak berulang. (Chartrand & Zhang 2009)
Ilustrasi trail bisa dilihat pada Gambar 6, T = u e2 x e5 w e4 v adalah trail. Definisi 15 (Trail berarah) Trail berarah pada suatu digraf adalah walk berarah dengan semua sisi dalam barisannya tidak berulang. (Vasudev 2006)
Ilustrasi trail berarah bisa dilihat pada Gambar 10, T = u e1 v e4 w e5 x adalah trail berarah. Definisi 16 (Jalur) Jalur (path) pada suatu graf adalah walk yang setiap verteks pada barisannya, hanya muncul satu kali. (Vasudev 2006)
Ilustrasi path bisa dilihat pada Gambar 6, P = u e1 v e4 w e5 x adalah path pada graf G. Definisi 17 (Path berarah) Path berarah pada suatu digraf adalah walk berarah dengan semua verteks dalam barisannya tidak berulang. (Vasudev 2006)
Definisi 19 (Sirkuit) Pada graf tidak berarah, sirkuit (circuit) adalah trail tertutup yang takkosong. (Chartrand & Oellermann 1993)
Ilustrasi sirkuit bisa dilihat pada Gambar 6. C = u e1 v e3 x e2 u merupakan sirkuit pada graf G. Definisi 20 (Sirkuit berarah) Pada suatu digraf, sirkuit berarah adalah walk berarah yang tertutup di mana barisannya dimulai dan diakhiri pada verteks yang sama dengan tidak ada sisi yang diulang. (Vasudev 2006)
Ilustrasi sirkuit berarah bisa dilihat pada Gambar 10. C = v e3 x e2 u e1 v merupakan sirkuit berarah pada digraf D. Definisi 21 (Semi-sirkuit) Pada suatu digraf, semi-sirkuit adalah sirkuit pada underlying graph D, tetapi bukan merupakan sirkuit berarah pada digraf D tersebut. (Vasudev 2006)
Ilustrasi semi-sirkuit bisa dilihat pada Gambar 10. C = u e2 x e3 v e1 u merupakan semi-sirkuit pada digraf D. Definisi 22 (Cycle) Pada graf tidak berarah, cycle adalah path tertutup yang takkosong. (Chartrand & Oellermann 1993)
Ilustrasi cycle bisa dilihat pada Gambar 7. Graf pada Gambar 7 memiliki cycle C = v-wy-x-v. Definisi 23 (Cycle berarah) Pada graf berarah, cycle adalah path berarah yang tertutup dan takkosong. (Chartrand & Oellermann 1993)
5
Ilustrasi cycle berarah bisa dilihat pada Gambar 10. Digraf pada Gambar 10 memiliki cycle C = u e1 v e3 x e2 u. Definisi 24 (Terhubung/connected) Suatu graf G disebut terhubung (connected) jika untuk setiap verteks dari G terhubung. Verteks u dengan v dikatakan terhubung jika ada setidaknya satu path dari verteks u ke v. (Vasudev 2006) Definisi 25 (Bridge) Suatu sisi e di graf G yang terhubung disebut bridge jika sisi e tersebut menyebabkan graf menjadi tidak terhubung pada saat sisi e dihilangkan. (Vasudev 2006)
Pada Gambar 1 sisi e={u,v} merupakan bridge, karena jika sisi tersebut dihilangkan maka graf G menjadi tidak terhubung. Definisi 26 (Subgraf) Suatu graf H dikatakan subgraf dari graf G jika V(H) V(G) dan E(H) E(G). (Chartrand & Oellermann 1993)
Graf pada Gambar 1 merupakan subgraf dari graf pada Gambar 7. Definisi 27 (Spanning subgraph) Suatu subgraf G dikatakan spanning subgraph jika subgraf tersebut mengandung semua verteks pada graf G. (Vasudev 2006)
Graf pada Gambar 7 merupakan spanning subgraph dari graf pada Gambar 8. Definisi 28 (Tree pada graf) Suatu graf terhubung yang tidak memiliki cycle disebut tree. (Chartrand & Zhang 2009)
Graf pada Gambar 1 merupakan tree karena tidak memiliki cycle. Definisi 29 (Tree pada digraf) Suatu digraf terhubung yang tidak memiliki cycle disebut tree pada digraf. (Chartrand & Zhang 2009)
Ilustrasi tree untuk digraf dapat dilihat pada Gambar 2.
Definisi 30 (Spanning tree) Suatu spanning tree adalah spanning subgraph yang merupakan tree. (Vasudev 2006)
D:
u
v
e1
e4 e5
x
w
Gambar 11 Spanning tree. Digraf pada Gambar 11 adalah spanning tree dari digraf pada Gambar 10. Definisi 31 (Arborescence) Graf berarah D disebut arborescence jika i. D tidak memiliki sirkuit maupun semisirkuit, ii. pada D terdapat tepat satu verteks vr yang memiliki d–(vr) = 0. Verteks vr disebut akar arborescence. (Vasudev 2006) D: y z u
x Gambar 12 Arborescence. Digraf pada Gambar 12 adalah suatu arborescence dengan verteks x sebagai akar arborescence. Definisi 32 (Spanning arborescence) Spanning arborescence pada digraf D adalah spanning tree yang bersifat arborescence. (Vasudev 2006) D:
v
t
w
z
u x
y
Gambar 13 Spanning arborescence. Ilustrasi spanning arborescence bisa dilihat pada Gambar 13. Digraf pada Gambar 13 merupakan spanning arborescence dari digraf pada Gambar 5, dengan akar arborescencenya di x.
6
2.2 Graf Euler
Leonhard Euler (1707-1783) adalah seorang peneliti yang lahir di Swiss. Ia dipandang sebagai salah satu matematikawan terbesar sepanjang masa. Euler menyumbangkan berbagai penemuan penting di bidang yang beragam seperti kalkulus dan teori graf. Dalam penelitiannya di bidang teori graf, Euler mengenalkan penemuan yang paling terkenal yaitu graf Euler. Berikut ini akan dijelaskan beberapa definisi yang berkaitan dengan graf Euler yang digunakan dalam karya ilmiah ini. Definisi 33 (Lintasan Euler) Lintasan (trail) Euler adalah lintasan yang melewati semua sisi pada graf G tepat satu kali. (Vasudev 2006)
Pada Gambar 6 T = x e5 w e4 v e3 x e2 u e1 v merupakan lintasan Euler. Definisi 34 (Sirkuit Euler) Sirkuit Euler adalah lintasan Euler yang tertutup. (Vasudev 2006)
Ilustrasi sirkuit Euler bisa dilihat pada Gambar 14. Sirkuit Euler dari graf G salah satunya adalah C = v e1 u e2 w e3 v e4 x e5 z e6 v. G: u x e1 e2 e3
w
v
e4
e5 e6
z
Gambar 14 Graf Euler. Definisi 35 (Graf/digraf Euler) Graf atau digraf yang memiliki sirkuit Euler disebut graf atau digraf Euler. (Vasudev 2006)
Ilustrasi graf Euler bisa dilihat pada Gambar 14. Graf G pada Gambar 14 merupakan graf Euler, karena graf tersebut memiliki sirkuit Euler.
Selanjutnya akan diberikan teoremateorema yang digunakan sebagai dasar pengerjaan karya ilmiah ini. Teorema 1 Suatu graf G merupakan graf Euler jika dan hanya jika setiap verteks pada graf G berderajat genap. (Chartrand & Zhang 2009)
Pembuktian Teorema 1 bisa dilihat pada Lampiran 1. Teorema 2 Misalkan D suatu digraf terhubung yang takkosong, maka D adalah digraf Euler jika dan hanya jika d+(vi) = d–(vi) untuk setiap verteks pada digraf D (digraf balance). (Chartrand & Zhang 2009) 2.3 Undirected Chinese Postman Problem (UCPP)
Masalah CPP pertama kali dikemukakan oleh Meigu Guan atau Kwan Meiko, seorang pakar matematika dari Universitas Shangtun, Cina, maka tidak heran bahwa permasalahan ini dinamakan Chinese Postman Problem karena memang berasal dari Cina. Permasalahan CPP adalah masalah mencari lintasan pada suatu graf berbobot yang terhubung dan melewati semua sisi minimal satu kali dengan jumlah bobot minimum di mana verteks awal dan akhirnya harus sama (tertutup). Pada graf yang memiliki sirkuit Euler, maka lintasan manapun yang diambil hasilnya akan sama, karena tiap sisi pasti dilewati satu kali sehingga bobot minimum adalah jumlah bobot dari semua sisi yang ada, sedangkan untuk graf yang tidak memiliki sirkuit Euler, perlu dilewati suatu sisi sebanyak dua kali bahkan lebih (Thimbleby 2003). Berdasarkan jenis grafnya masalah CPP dibagi menjadi dua jenis yaitu berarah (directed) yang dikenal sebagai DCPP dan tidak berarah (undirected) yang dikenal sebagai UCPP. UCPP adalah sebuah masalah yang tujuannya adalah mencari rute terpendek pada sebuah graf yang tidak berarah. Masalah UCPP dapat diselesaikan antara lain dengan menggunakan algoritme Fleury.
7
2.4 Algoritme Fleury
Misalkan G = (V, E) adalah graf terhubung yang semua verteksnya berderajat genap. LANGKAH 1. Inisialisasikan i = 0. Dimulai dari verteks v0 dan didefinisikan trail T0 : v0. LANGKAH 2. Kemudian dimisalkan Ti = v0 e1 v1 e2 v2 e3 ... ei vi sebagai trail di antara v0 dan vi pada iterasi ke-i, lalu dipilih sebuah sisi ei+1 yang menghubungkan vi dengan vi+1 yang bukan merupakan bridge dari himpunan sisi Ei = E – {e1,e2,..,ei}. Jika ei+1 adalah bridge pada subgraf yang didapat dari G setelah menghapus sisi yang dimiliki Ei dari E, dan tidak ada pilihan lain yang bisa diambil, maka sisi tersebut dimasukkan ke dalam trail Ti = v0 e1 v1 e2 v2 e3 ... ei vi ei+1. Jika tidak ada sisi lagi yang bisa dipilih maka proses berhenti. LANGKAH 3. Kemudian i diganti menjadi i+1, lalu kembali ke Langkah 2.
G: 2
v0 1
4 6
5
Gambar 16 Iterasi pertama : inisialisasi v0. 2. dipilih sisi yang incident dengan v0 dan bukan merupakan bridge pada graf. Misalkan sisi {1,2} dipilih, lalu sisi tersebut dihapus dan didefinisikan verteks 2 sebagai verteks v1, sehingga graf menjadi seperti pada Gambar 17. G:
Trail yang terbentuk dari urutan sisi yang diambil merupakan sirkuit Euler pada graf G. (Balakrishnan 1997)
3
v1 2
v0
3
1
4
Aplikasi Algoritme Fleury Misalkan diberikan graf seperti pada Gambar 15.
6
5
Gambar 17 Iterasi kedua : sisi {1,2} dihapus.
G: 2
3. dipilih sisi {2,4} yang bukan bridge pada subgraf G, sehingga graf menjadi seperti pada Gambar 18.
3
1
4 6
G:
5
v1 v0
Gambar 15 Graf Euler balance untuk contoh algoritme Fleury. Untuk mencari sirkuit Euler pada graf tersebut dengan algoritme Fleury, dilakukan prosedur sebagai berikut: 1. dipilih sembarang verteks, misalkan verteks (1) yang dilabeli sebagai v0,
2
3
v2
1
4 6
5
Gambar 18 Iterasi ketiga : sisi {2,4} dihapus. Iterasi selanjutnya diberikan secara lengkap pada Lampiran 2. Setelah semua sisi dihapus, sehingga dihasilkan graf seperti pada Gambar 19, maka sirkuit Euler sudah bisa ditemukan.
8
yang belum dilabeli. Iterasi juga berhenti jika P = V. Arc (i,k) dilabeli dengan i, yaitu verteks yang memiliki L’(k) yang minimum.
G: v1 v9 v0 v11
2
3
v6 v8
1
4 6
LANGKAH 2. L’(j) diganti oleh nilai terkecil antara L’(j) dan L(k) + a(k,j) untuk setiap j pada T, kembali ke Langkah 1.
5
v3 v10
(Balakrishnan 1997)
v2 v5
v4 v7
Gambar 19 Solusi sirkuit Euler dengan algoritme Fleury. Dari urutan verteks yang dipilih dan sisi yang dihapus akan diperoleh solusi sirkuit Eulernya, yaitu C = v0 v1 v2 ..... v10 v11 atau bisa dituliskan dengan C = 1-2-4-6-5-4-3-5-32-6-1. Meskipun dimulai dari verteks yang sama, sirkuit Euler yang dihasilkan tidak selalu sama, bergantung pada urutan pengambilan atau penghapusan sisi. Contohnya C = 1-6-4-5-3-5-6-2-3-4-2-1. Selain digunakan untuk mencari sirkuit Euler pada graf yang tidak berarah, algoritme ini juga bisa digunakan untuk mencari sirkuit Euler pada graf berarah. 2.5 Algoritme Dijkstra Algoritme ini bisa digunakan untuk mencari path terpendek atau jarak terpendek pada graf atau digraf yang tidak berbobot maupun yang berbobot. Misalkan diberikan D = (V,E) dengan V = {1,2,...,n} adalah digraf berbobot dengan bobot pada tiap verteksnya taknegatif. Misalkan a(i,j) adalah bobot pada arc dari i ke j. Jika tidak ada arc dari i ke j maka a(i,j) bernilai +∞. Setiap verteks i dilabeli dengan L(i) yang menyatakan jarak terpendek dari verteks awal ke verteks i yang sifatnya permanen artinya pasti dipilih, sedangkan label L’(i) memiliki makna sama dengan L(i) namun sifatnya masih sementara artinya mungkin dipilih atupun tidak. Di setiap iterasi dibuat P yang menyatakan himpunan verteks dengan label L(i) dan T yang menyatakan himpunan verteks dengan label L’(i). Misalkan verteks awalnya di 1, maka diinisialisasikan, P = {1} dengan L(1) = 0 dan L’(j) = a(1, j) untuk semua j. Prosedur selesai ketika P = V. Setiap iterasi mempunyai dua langkah yaitu:
LANGKAH 1. Dicari verteks k pada T dengan L’(k) berhingga dan minimum. Kemudian k dijadikan anggota P, Jika tidak ada k yang dimaksud maka proses berhenti, karena tidak ada path dari 1 ke verteks lain
Contoh Algoritme Dijkstra Diberikan digraf berbobot berikut: D:
2
4
6
1 2
3 1
2
4
3
7 7
3 6
3
4
3
3
5
Gambar 20 Digraf contoh algoritme Dijkstra. Akan ditentukan jarak terpendek dari verteks 1 ke verteks lainnya. Maka dengan mengaplikasikan algoritme Dijkstra akan diperoleh path terpendek dari verteks 1 menuju verteks lain seperti pada Gambar 21 (detail penghitungannya dapat dilihat pada Lampiran 3). D: 2
6
1
3 1
2
7 6
7
3 3
4
5 Gambar 21 Solusi path terpendek algoritme Dijkstra dengan verteks awal 1. Misalkan dicari jarak terdekat dari verteks 1 ke verteks 4 pada digraf Gambar 21, maka pathnya adalah P = 1-7-4 dengan jarak 9. Contoh lainnya misalkan dicari jarak terdekat dari verteks 1 ke verteks 6, maka path-nya adalah P = 1-7-6 dengan jarak 5.