implementasi algoritma pencarian k jalur...

IMPLEMENTASI ALGORITMA PENCARIAN K JALUR SEDERHANA TERPENDEK

DALAM GRAF

(Kata kunci: Algoritma deviasi, algoritma Dijkstra, jalur sederhana, jalur terpendek)

PRESENTASI TUGAS AKHIR – KI091391

Penyusun Tugas Akhir : Anggakara Hendra Nandana

(NRP: 5108.100.075)

Dosen Pembimbing : Yudhi Purwananto, S.Kom., M.Kom.

Rully Soelaiman, S.Kom., M.Kom.

10 Juli 2013 Tugas Akhir - KI091391 1

10 Juli 2013 Tugas Akhir - KI091391 2

KERANGKA PRESENTASI

Ilustrasi Permasalahan

Latar Belakang

Batasan Masalah

Tujuan

Pendahuluan

Rangkaian Proses

Uji Coba

Kesimpulan

ILUSTRASI PERMASALAHAN

3 10 Juli 2013 Tugas Akhir - KI091391

Problem dari situs Sphere Online Judge (SPOJ) berjudul “Kth Shortest Path” (http://www.spoj.com/problems/MKTHPATH/)

DESKRIPSI SOAL SPOJ “Kth Shortest Path”

4 10 Juli 2013 Tugas Akhir - KI091391

1. Seseorang bernama Isaac merasa bosan karena setiap hari melalui jalur yang sama untuk melakukan perjalanan dari rumah menuju kantor.

2. Jalur yang diambil Isaac selalu merupakan jalur terpendek, yaitu jalur dengan biaya terkecil, dan selalu merupakan jalur sederhana.

3. Biaya pada sebuah jalur merupakan total waktu yang dibutuhkan untuk melewati jalan-jalan yang menghubungkan dua buah tempat yang menyusun jalur tersebut.

4. Waktu yang dibutuhkan untuk melewati sebuah jalan bisa bernilai sama atau berbeda dengan jalan-jalan yang lain.

5. Pada hari-hari berikutnya, Isaac ingin melewati jalur terpendek yang belum pernah dilewatinya.

6. Dengan kata lain, pada hari ke-k, Isaac ingin melewati jalur terpendek ke-k.

7. Permasalahan Isaac dapat dimodelkan menjadi graf dengan masing-masing verteks merepresentasikan tempat dan masing-masing edge merepresentasikan jalan.

BATASAN SOAL SPOJ “Kth Shortest Path”

5 10 Juli 2013 Tugas Akhir - KI091391

1. Jumlah verteks maksimum 50 buah, jumlah edge maksimum 2450 buah, dan banyak jalur yang dicari (k) maksimum 200 buah.

2. Jalur yang dicari harus merupakan jalur sederhana, yaitu jalur yang tidak memiliki pengulangan verteks penyusun.

3. Jika terdapat dua kandidat jalur terpendek dengan bobot yang sama, maka jalur yang dipilih adalah jalur yang lebih dahulu memiliki verteks penyusun dengan nomor yang lebih kecil. (Contoh: Jika memiliki bobot yang sama, maka jalur 1-2-3-4 muncul lebih dahulu daripada jalur 1-3-4.)

FORMAT DATA MASUKAN

6 10 Juli 2013 Tugas Akhir - KI091391

• Data masukan merupakan sebuah berkas teks yang hanya berisi bilangan bulat

• Masing-masing bilangan bulat merepresentasikan detail graf dengan format seperti pada Gambar 1 n m k a b

x1 y1 z1 x2 y2 z2 … xm ym zm

jumlah verteks jumlah edge jumlah jalur yang dicari

verteks sumber jalur verteks tujuan jalur

detail edge-edge

Gambar 1

FORMAT DATA MASUKAN

7 10 Juli 2013 Tugas Akhir - KI091391

n m k a b x1 y1 z1 x2 y2 z2 … xm ym zm

verteks sumber verteks tujuan bobot edge

• Data masukan merupakan sebuah berkas teks yang hanya berisi bilangan bulat

• Masing-masing bilangan bulat merepresentasikan detail graf dengan format seperti pada Gambar 1

Gambar 1

CONTOH DATA MASUKAN

8 10 Juli 2013 Tugas Akhir - KI091391

4 6 2 1 4 2 3 1 1 3 2 1 2 1 1 4 3 2 4 2 3 4 1

1 2

4 3

1 2

1

3

2

1

1

4

Data Masukan Gambar Graf

FORMAT DATA KELUARAN

9 10 Juli 2013 Tugas Akhir - KI091391

• Data keluaran merupakan sebuah berkas teks yang hanya berisi bilangan bulat.

• Masing-masing bilangan bulat merepresentasikan verteks-verteks penyusun jalur yang ditemukan

• Urutan penulisan verteks-verteks penyusun jalur dimulai dari verteks sumber hingga verteks tujuan.

• Pada tiap dua buah verteks dipisahkan sebuah tanda hubung (-). a-v2-…-vl-1-b

verteks sumber jalur verteks tujuan jalur

CONTOH DATA KELUARAN

10 10 Juli 2013 Tugas Akhir - KI091391

1-2-4

4 6 2 1 4 2 3 1 1 3 2 1 2 1 1 4 3 2 4 2 3 4 1

Data Masukan

2

3

1

2

1

3

2

1

1

4

Gambar Graf Data Keluaran

10 Juli 2013 Tugas Akhir - KI091391 11

ALGORITMA NAIF (1)

2

3

1

2

1

3

2

1

1

4

• Daftar kemungkinan jalur dari vertex 1 ke vertex 4: 1 : 1-2-3-4, bobot = 3 2 : 1-2-4, bobot = 3 3 : 1-3-4, bobot = 3 4 : 1-4, bobot = 3

• Pada k jalur terpendek pertama, masing-masing verteks dapat menjadi verteks penyusun jalur sebanyak maksimal k kali.

• Vertex sumber dan verteks tujuan jalur selalu muncul pada setiap k jalur terpendek.

• Pencarian jalur dapat dilakukan dengan mencari seluruh kemungkinan jalur yang menuju verteks tujuan, hingga ditemukan jalur yang berasal dari verteks sumber sebanyak k kali.

10 Juli 2013 Tugas Akhir - KI091391 12

ALGORITMA NAIF (2)

2

3

1

2

1

3

2

1

1

4

Daftar urutan jalur yang menuju ke verteks 4 : 1: 4 (bobot = 0) 2: 3-4 (bobot = 1) 3: 2-3-4 (bobot = 2) 4: 2-4 (bobot = 2) 5: 1-2-3-4 (bobot = 3) 6: 1-2-4 (bobot = 3) 7: 1-3-4 (bobot = 3)

10 Juli 2013 Tugas Akhir - KI091391 13

HASIL ALGORITMA NAIF

Kesimpulan: Algoritma naif kurang efisien untuk menyelesaikan permasalahan pencarian k jalur sederhana terpendek.

Hasil pengujian implementasi algoritma naif pada soal “Kth Shortest Path”

LATAR BELAKANG

14 10 Juli 2013 Tugas Akhir - KI091391

1. Problem berjudul “Kth Shortest Path” pada situs SPOJ merupakan contoh permasalahan yang dapat ditemukan dalam kehidupan sehari-hari, sehingga dibutuhkan sebuah algoritma untuk menyelesaikan permasalahan tersebut.

2. Algoritma naif kurang efisien dalam hal kecepatan dan memori yang dibutuhkan, sehingga dibutuhkan algoritma lain yang lebih cepat dan lebih hemat memori

BATASAN MASALAH

15 10 Juli 2013 Tugas Akhir - KI091391

1. Pustaka yang digunakan untuk membantu pengimplementasian algoritma merupakan C++ Standard Template Library (STL). Pustaka-pustaka tersebut antara lain: cstdio, iostream, algorithm, cstring, vector, queue, dan ctime.

2. Kebutuhan memori hasil implementasi mengacu pada hasil keluaran dari server situs SPOJ untuk problem “Kth Shortest Path”.

TUJUAN MASALAH

16 10 Juli 2013 Tugas Akhir - KI091391

1. Untuk melakukan studi dan mengimplementasi algoritma pencarian k jalur sederhana terpendek dalam graf yang lebih optimal dibandingkan dengan algoritma naif dengan bantuan pustaka dari C++ Standard Template Library.

2. Untuk menguji kebenaran hasil implementasi algoritma pencarian k jalur sederhana terpendek dalam graf.

3. Untuk menguji dan membandingkan kecepatan algoritma naif dengan algoritma baru yang dijelaskan pada tugas akhir ini.

10 Juli 2013 Tugas Akhir - KI091391 17

KERANGKA PRESENTASI

Pendahuluan

Rangkaian Proses

Uji Coba

Kesimpulan

Pencarian kandidat jalur terpendek pertama

Pengambilan jalur terpendek dari himpunan kandidat

jalur X

Penghapusan subjalur dan edge-edge dari graf

Pembentukan pohon jalur terpendek Tt

Pencarian kandidat-kandidat jalur terpendek berikutnya

Pengecekan jumlah jalur dan isi himpunan kandidat

jalur

1

2

3

4

5

6

10 Juli 2013 Tugas Akhir - KI091391 18

RANGKAIAN PROSES: LANGKAH 1

Pencarian kandidat jalur terpendek pertama

Pengambilan jalur terpendek dari himpunan kandidat

jalur X

Penghapusan subjalur dan edge-edge dari graf

Pembentukan pohon jalur terpendek Tt

Pencarian kandidat-kandidat jalur terpendek berikutnya

Pengecekan jumlah jalur dan isi himpunan kandidat

jalur

1 • Jalur terpendek pertama digunakan sebagai acuan

untuk menentukan kandidat-kandidat jalur terpendek berikutnya.

• Jalur terpendek pertama dicari menggunakan algoritma Dijkstra

2

3

1

2

1

3

2

1

1

4 Gambar 2

10 Juli 2013 Tugas Akhir - KI091391 19

RANGKAIAN PROSES: LANGKAH 1

Pencarian kandidat jalur terpendek pertama

Pengambilan jalur terpendek dari himpunan kandidat

jalur X

Penghapusan subjalur dan edge-edge dari graf

Pembentukan pohon jalur terpendek Tt

Pencarian kandidat-kandidat jalur terpendek berikutnya

Pengecekan jumlah jalur dan isi himpunan kandidat

jalur

1 • Jalur terpendek dari verteks 1 menuju verteks 4 pada

Gambar 2 adalah jalur 1-2-3-4

• Jalur terpendek yang didapat kemudian ditambahkan ke himpunan kandidat jalur X

• Inisialisasi verteks sumber sebagai verteks deviasi jalur

Gambar 2

2

3

1

2

1

3

2

1

1

4

10 Juli 2013 Tugas Akhir - KI091391 20

ALGORITMA DEVIASI

• Jalur-jalur terpendek yang didapat dari sebuah graf dapat membentuk pohon jalur terpendek seperti pada Gambar 3

• Sebuah jalur pk selalu memiliki rangkaian vertex yang sama dengan jalur p1, …, pk-1 dari verteks sumber sampai verteks tertentu.

• Verteks tersebut merupakan letak jalur pk menyimpang dari himpunan jalur {p1, …, pk-1} dan disebut verteks deviasi. Verteks deviasi pada jalur p dinotasikan sebagai d(p)

Gambar 3

2

1

4

3 3 5

5 5

p1

p2 p3

• d(p1) = 1 • d(p2) = 1 • d(p3) = 2

10 Juli 2013 Tugas Akhir - KI091391 21

RANGKAIAN PROSES: LANGKAH 2

Pencarian kandidat jalur terpendek pertama

Pengambilan jalur terpendek dari himpunan kandidat

jalur X

Penghapusan subjalur dan edge-edge dari graf

Pembentukan pohon jalur terpendek Tt

Pencarian kandidat-kandidat jalur terpendek berikutnya

Pengecekan jumlah jalur dan isi himpunan kandidat

jalur

2

• Himpunan kandidat jalur X berisi kandidat-kandidat jalur terpendek

• Jalur yang diambil adalah jalur dengan bobot minimum dari semua anggota X, dan dinotasikan sebagai jalur p.

• Panjang jalur p dinotasikan sebagai l, dan urutan verteks penyusunnya dinotasikan sebagai v1, v2, …, vl.

• Banyaknya jalur yang telah diambil dari X menunjukkan banyaknya jalur yang telah ditemukan

2 1 1 1

4

Contoh jalur terpendek dari X

(bobot = 3)

v1 v2 vl /v4

3

v3

1

10 Juli 2013 Tugas Akhir - KI091391 22

RANGKAIAN PROSES: LANGKAH 2

Pencarian kandidat jalur terpendek pertama

Pengambilan jalur terpendek dari himpunan kandidat

jalur X

Penghapusan subjalur dan edge-edge dari graf

Pembentukan pohon jalur terpendek Tt

Pencarian kandidat-kandidat jalur terpendek berikutnya

Pengecekan jumlah jalur dan isi himpunan kandidat

jalur

2

• Agar proses pemilihan jalur terpendek dapat lebih efisien, maka diperlukan struktur data yang tepat.

• Pada program, implementasi himpunan kandidat jalur menggunakan struktur data priority_queue yang mengaplikasikan struktur heap biner.

2 1 1 1

4

Contoh jalur terpendek dari X

(bobot = 3)

v1 v2 vl /v4

3

v3

1

10 Juli 2013 Tugas Akhir - KI091391 23

RANGKAIAN PROSES: LANGKAH 3

Pencarian kandidat jalur terpendek pertama

Pengambilan jalur terpendek dari himpunan kandidat

jalur X

Penghapusan subjalur dan edge-edge dari graf

Pembentukan pohon jalur terpendek Tt

Pencarian kandidat-kandidat jalur terpendek berikutnya

Pengecekan jumlah jalur dan isi himpunan kandidat

jalur

3

• Bertujuan agar jalur yang sudah ditemukan tidak dapat menjadi kandidat jalur terpendek berikutnya.

• Subjalur yang dihapus dimulai dari verteks sumber hingga verteks ke-(l -1) pada jalur p dan dinotasikan dengan subp(s, vl -1 )

• Hapus semua edge yang berasal dari verteks deviasi jalur-jalur yang ditemukan sebelum jalur p.

jalur p

2

3

1

2

1

3

2

1

1

4

1 2 3 4

10 Juli 2013 Tugas Akhir - KI091391 24

RANGKAIAN PROSES: LANGKAH 4

Pencarian kandidat jalur terpendek pertama

Pengambilan jalur terpendek dari himpunan kandidat

jalur X

Penghapusan subjalur dan edge-edge dari graf

Pembentukan pohon jalur terpendek Tt

Pencarian kandidat-kandidat jalur terpendek berikutnya

Pengecekan jumlah jalur dan isi himpunan kandidat

jalur

4

• Pohon jalur terpendek Tt adalah struktur pohon dari graf yang berakar pada verteks t, yaitu verteks tujuan jalur.

• Jarak antara sebuah verteks dengan verteks akar pada

pohon merupakan jarak minimum kedua verteks pada graf.

2

3

1

2

1

3

2

1

1

4

10 Juli 2013 Tugas Akhir - KI091391 25

RANGKAIAN PROSES: LANGKAH 4

Pencarian kandidat jalur terpendek pertama

Pengambilan jalur terpendek dari himpunan kandidat

jalur X

Penghapusan subjalur dan edge-edge dari graf

Pembentukan pohon jalur terpendek Tt

Pencarian kandidat-kandidat jalur terpendek berikutnya

Pengecekan jumlah jalur dan isi himpunan kandidat

jalur

4

• Pada proses algoritma, pohon jalur terpendek dibentuk dari graf setelah dilakukan penghapusan verteks dan edge pada graf

4

10 Juli 2013 Tugas Akhir - KI091391 26

RANGKAIAN PROSES: LANGKAH 5

Pencarian kandidat jalur terpendek pertama

Pengambilan jalur terpendek dari himpunan kandidat

jalur X

Penghapusan subjalur dan edge-edge dari graf

Pembentukan pohon jalur terpendek Tt

Pencarian kandidat-kandidat jalur terpendek berikutnya

Pengecekan jumlah jalur dan isi himpunan kandidat

jalur

5

Pengembalian verteks vi ke dalam graf

Penghitungan jarak antara vi dengan t

Penambahan kandidat jalur ke dalam X

Pengembalian edge (vi, vi+1) pada graf

5.1

Perbaikan struktur pohon Tt

5.2

5.3

5.4

5.5

diulang untuk setiap vi ∈ {vl -1, …, d(p) }

10 Juli 2013 Tugas Akhir - KI091391 27

RANGKAIAN PROSES: LANGKAH 5.1

Pencarian kandidat-kandidat jalur terpendek berikutnya 5

Pengembalian verteks vi ke dalam graf

Penghitungan jarak antara vi dengan t

Penambahan kandidat jalur ke dalam X

Pengembalian edge (vi, vi+1) pada graf

5.1

Perbaikan struktur pohon Tt

3 1

4

2

2

1 2 3 4

vi

1

2

1

3

1

10 Juli 2013 Tugas Akhir - KI091391 28

RANGKAIAN PROSES: LANGKAH 5.2

Pencarian kandidat-kandidat jalur terpendek berikutnya 5

Pengembalian verteks vi ke dalam graf

Penghitungan jarak antara vi dengan t

Penambahan kandidat jalur ke dalam X

Pengembalian edge (vi, vi+1) pada graf

5.2

Perbaikan struktur pohon Tt

Dilakukan penghitungan kembali jarak antara vi dengan t, yaitu dengan memperbaiki struktur pohon Tt

3 1

4

2

2

1 2 3 4

vi

10 Juli 2013 Tugas Akhir - KI091391 29

RANGKAIAN PROSES: LANGKAH 5.3

Pencarian kandidat-kandidat jalur terpendek berikutnya 5

Pengembalian verteks vi ke dalam graf

Penghitungan jarak antara vi dengan t

Penambahan kandidat jalur ke dalam X

Pengembalian edge (vi, vi+1) pada graf

5.3

Perbaikan struktur pohon Tt

• Jika jalur dari verteks vi ke verteks t dapat ditetapkan, maka dilakukan penambahan kandidat jalur baru.

• Kandidat jalur merupakan gabungan dari subp(s, vi) dengan jalur dari vi menuju t pada struktur pohon Tt.

• Kandidat jalur terpendek yang dapat terbentuk adalah jalur 1-2-4

3 1

4

2 2

1 2 3 4

vi

subp(s, vi)

10 Juli 2013 Tugas Akhir - KI091391 30

RANGKAIAN PROSES: LANGKAH 5.4

Pencarian kandidat-kandidat jalur terpendek berikutnya 5

Pengembalian verteks vi ke dalam graf

Penghitungan jarak antara vi dengan t

Penambahan kandidat jalur ke dalam X

Pengembalian edge (vi, vi+1) pada graf

5.4

Perbaikan struktur pohon Tt

1 2 3 4

vi vi+1

3 1

4

2

2 1

2

1

3

1

10 Juli 2013 Tugas Akhir - KI091391 31

RANGKAIAN PROSES: LANGKAH 5.5

Pencarian kandidat-kandidat jalur terpendek berikutnya 5

Pengembalian verteks vi ke dalam graf

Penghitungan jarak antara vi dengan t

Penambahan kandidat jalur ke dalam X

Pengembalian edge (vi, vi+1) pada graf

5.5 Perbaikan struktur pohon Tt

3 1

4

2

2 1

1 2 3 4

vi

3 1

4

2

2

Tt sebelum diperbaiki

Tt setelah diperbaiki

10 Juli 2013 Tugas Akhir - KI091391 32

RANGKAIAN PROSES: LANGKAH 6

Pencarian kandidat jalur terpendek pertama

Pengambilan jalur terpendek dari himpunan kandidat

jalur X

Penghapusan subjalur dan edge-edge dari graf

Pembentukan pohon jalur terpendek Tt

Pencarian kandidat-kandidat jalur terpendek berikutnya

Pengecekan jumlah jalur dan isi himpunan kandidat

jalur 6

• Rangkaian proses algoritma berhenti jika salah satu dari dua kondisi berikut tercapai:

1. jumlah jalur yang diambil dari X sudah sama dengan k

2. Himpunan jalur X merupakan himpunan kosong

10 Juli 2013 Tugas Akhir - KI091391 33

KERANGKA PRESENTASI

Uji Kebenaran

Uji Kecepatan

Uji Perbandingan Algoritma

Pendahuluan

Rangkaian Proses

Uji Coba

Kesimpulan

10 Juli 2013 Tugas Akhir - KI091391 34

UJI KEBENARAN

5 8 4 1 5 1 2 1 1 4 3 1 3 1 2 4 2 3 4 2 2 5 3 4 5 1 3 5 2

1-3-4-5

Data Masukan Data Keluaran Program

2

1 4

3

3

2

1

2

2

1

3

1

5

1

2 3

4 4 5 5

5 5

1 1

2 3 2 2

1 1 p1

p2

p3

p4 k = 4

10 Juli 2013 Tugas Akhir - KI091391 35

UJI KECEPATAN (1)

• Waktu minimal = 2,73 detik • Waktu maksimal = 2,83 detik • Rata-rata waktu yang dibutuhkan adalah 2,76 detik dengan standar deviasi sebesar 0,3

10 Juli 2013 Tugas Akhir - KI091391 36

UJI KECEPATAN (2)

k Judul Graf

Waktu (detik)

100

A 0.024 B 0.035 C 0.588 D 94.856

500

A 0.115 B 0.161 C 3.030 D 448.342

1000

A 0.227 B 0.328 C 6.165 D 888.671

5000

A 1.114 B 1.562 C 32.113 D 4486.230

Judul Graf Jumlah Verteks Jumlah Edge

Graf A 51 1.183 Graf B 50 2.450 Graf C 730 5.762 Graf D 6.551 47.322

Kompleksitas algoritma: Ο (kn (m + n log (n))

10 Juli 2013 Tugas Akhir - KI091391 37

UJI PERBANDINGAN ALGORITMA

k Judul Graf

Algoritma TA

Algoritma Naif

100 A 0.016 0.296 B 0.035 0.561

500 A 0.093 1.294 B 0.161 3.104

1000 A 0.187 2.62 B 0.328 6.24

5000 A 0.974 14.461 B 1.562 30.576

Judul Graf Jumlah Verteks Jumlah Edge

Graf A 51 1.183 Graf B 50 2.450 Graf C 730 5.762 Graf D 6.551 47.322

10 Juli 2013 Tugas Akhir - KI091391 38

KERANGKA PRESENTASI

Kesimpulan

Saran

Pendahuluan

Rangkaian Proses

Uji Coba

Penutup

10 Juli 2013 Tugas Akhir - KI091391 39

Kesimpulan

1. Hasil implementasi algoritma pencarian jalur sederhana terpendek yang dijelaskan pada tugas akhir ini dapat menghasilkan keluaran yang benar.

2. Kompleksitas waktu eksekusi program adalah Ο (kn (m + n log (n)) pada n buah edge, m buah verteks, dan k jalur yang dicari pada graf.

3. Algoritma pada tugas akhir ini lebih efisien daripada algoritma naif yang telah ditemukan sebelumnya.

10 Juli 2013 Tugas Akhir - KI091391 40

Saran

Pengembangan dengan melakukan studi mengenai struktur heap Fibonacci beserta implementasinya pada program untuk mempercepat pemrosesan kandidat jalur.

10 Juli 2013 Tugas Akhir - KI091391 41

10 Juli 2013 Tugas Akhir - KI091391 42

KERANGKA PRESENTASI

Struktur Pohon Jalur Terpendek

Struktur Percabangan Jalur

Struktur Pohon Tt

Pendahuluan

Metode

Uji Coba

Kesimpulan

Rangkaian Proses

10 Juli 2013 Tugas Akhir - KI091391 43

POHON JALUR TERPENDEK

Struktur Pohon Jalur Terpendek

Struktur Percabangan Jalur

Struktur Pohon Tt

Rangkaian Proses

2

1 3

4

0

2

0

2

0

0

3

1

5

Daftar tiga jalur terpendek dari verteks 1 ke verteks 5: P1: 1-2-5 P2: 1-4-3-5 P3: 1-2-3-5

10 Juli 2013 Tugas Akhir - KI091391 44

POHON JALUR TERPENDEK

Struktur Percabangan Jalur

Struktur Pohon Tt

Rangkaian Proses

2

1 3

4

0

2

0

2

0

0

3

1

5

1

4 2

5 3 3

5 5

P1: 1-2-5 P2: 1-4-3-5 P3: 1-2-3-5

P1

P3 P2

Struktur Pohon Jalur Terpendek

10 Juli 2013 Tugas Akhir - KI091391 45

PERCABANGAN JALUR

Struktur Percabangan Jalur

Struktur Pohon Tt

Rangkaian Proses

s a t Struktur Pohon Jalur Terpendek

Jalur ke-p :

Kandidat jalur-jalur ke-q (q > p):

s … t a

s a t …

10 Juli 2013 Tugas Akhir - KI091391 46

STRUKTUR POHON Tt

Struktur Percabangan Jalur

Struktur Pohon Tt

Rangkaian Proses

Struktur Pohon Jalur Terpendek

2

1 3

4

0

2

0

2

0

0

3

1

5

Struktur Pohon Tt

10 Juli 2013 Tugas Akhir - KI091391 47

STRUKTUR POHON Tt

Struktur Percabangan Jalur

Struktur Pohon Tt

Rangkaian Proses

Struktur Pohon Jalur Terpendek

2

3

4

2

0

2

0

5

Struktur Pohon Tt setelah dilakukan penghapusan edge-edge pada jalur 1-2-5

1 3

1

10 Juli 2013 Tugas Akhir - KI091391 48

PSEUDOCODE (1)

10 Juli 2013 Tugas Akhir - KI091391 49

PSEUDOCODE (2)

10 Juli 2013 Tugas Akhir - KI091391 50

KODE SUMBER (1)

10 Juli 2013 Tugas Akhir - KI091391 51

KODE SUMBER (2)