PEDIA: Dynamic Programming |

<p><br />
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<b><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">F. Shortest Path</span></b><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<br /></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Pencarian
shortest path (lintasan terpendek) adalah masalah umum dalam suatu weighted,
connected graph. Misal : Pencarian jaringan jalan raya yang menghubungkan
kota-kota disuatu wilayah.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<br /></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">1.</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">    </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Lintasan terpendek yag menghubungkan antara dua kota
berlainan tertentu (Single-source Single-destination Shortest Path
Problems)</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">2.</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">    </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Semua lintasan terpendek masing-masing dari suatu kota ke
setiap kota lainnya (Single-source Shortest Path problems)</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">3.</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">    </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Semua lintasan terpendek masing-masing antara tiap
kemungkinan pasang kota yang berbeda (All-pairs Shortest Path Problems)</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Untuk memecahkan
masing-masing dari masalah-masalah tersebut terdapat sejumlah solusi.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<br /></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Dalam
beberapa masalah graph lain, suatu graph dapat memiliki bobot negatif dan kasus
ini dipecahkan oleh algoritma Bellman-Ford. Yang akan dibahas di sini adalah
algoritma Dijkstra yaitu mencari lintasan terpendek dari suatu verteks
asal tertentu vs ke setiap verteks lainnya.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: .5in;">
<br /></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<b><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">a. </span></b><b><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Graph
berbobot (weighted graph)</span></b><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<br /></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Apabila
sisi-sisi pada graph disertai juga dengan suatu (atau beberapa) harga yang
menyatakan secara unik kondisi keterhubungan tersebut maka graph tersebut
disebut graph berbobot. Biasanya dalam masalah-masalah graph bobot tersebut
merupakan "</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">harga</span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">" dari
keterhubungan </span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">antar vertex</span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">.
Pengertian "</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">harga</span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">" ini
menggeneralisasikan banyak aspek</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">,</span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"> biaya ekonomis dari proses/aktifitas, jarak
geografis/tempuh, waktu tempuh, tingkat kesulitan, dan lain sebagainya.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: .0001pt; margin-bottom: 0in;">
<span lang="IN" style="color: #262626; font-family: "Arial","sans-serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";"> </span><span class="Apple-style-span" style="color: #262626; font-family: Cambria, serif; font-size: 16px;">Dalam beberapa masalah lain bisa juga bobot tersebut
memiliki pengertian "laba" yang berarti kebalikan dari
"biaya" di atas. Dalam pembahasan algoritma-algoritma graph nanti
pengertian bobot akan menggunakan pengertian biaya sehingga apabila
diaplikasikan pada masalah yang berpengertian laba maka kuantitas-kuantitas
terkait adalah kebalikannnya. Misalnya mencari jarak tempuh minimum digantikan
dengan mencari laba maksimum. </span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEial5jkFrtH6u-kwCZmPgg2PY4oUI48wMqjOHQ_9XfD0dSLxmwuweIf2NtdKvGypBZs6ArEZXpum45MoTAblaLSnA6qfnM8PVFPLUg6bOiy1YDPYpg21UGzCoypfuV4YLtnPqW5n9VzIudd/s1600/l.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="152" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEial5jkFrtH6u-kwCZmPgg2PY4oUI48wMqjOHQ_9XfD0dSLxmwuweIf2NtdKvGypBZs6ArEZXpum45MoTAblaLSnA6qfnM8PVFPLUg6bOiy1YDPYpg21UGzCoypfuV4YLtnPqW5n9VzIudd/s1600/l.jpg" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0.0001pt; text-align: left;">
<b><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">b. Algoritma Dijkstra’s</span></b><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Algoritma Dijkstra's :</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left; text-indent: -0.25in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">1.</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">    </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Menyelesaikan problem single-source shortest-path ketika
semua edge memiliki bobot tidak negatif.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left; text-indent: -0.25in;">
<span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">2.</span><span style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-fareast-font-family: "Times New Roman";">    </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Algoritma greedy mirip ke algoritma Prim's.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left; text-indent: -0.25in;">
<span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">3.</span><span style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-fareast-font-family: "Times New Roman";">    </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Algoritma di awali pada vertex sumber s, kemudian
berkembang membentuk sebuah tree T, pada akhirnya periode semua vertex dijangkau
dari S. Vertex di tambah ke T sesuai urutan</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Misalnya :</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Pertama S, kemudian
vertex yang tepat ke S, kemudian yang tepat berikutnya dan seterusnya.</span><br />
<div style="text-align: center;">
<span lang="IN"><span class="Apple-style-span" style="font-family: 'Times New Roman', serif; font-size: large;"><span class="Apple-style-span" style="font-size: 18px;">

</span></span></span></div>
</div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<b><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">c. </span></b><b><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Dynamic
Programming</span></b><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left; text-indent: 0.5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Terdiri
dari sederetan tahapan keputusan. Pada setiap tahapan berlaku prinsip optimality
(apapun keadaan awal dan keputusan yang diambil, keputusan berikutnya harus
memberikan hasil yang optimal dengan melihat hasil keputusan sebelumnya.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Misalnya  : </span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">    </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Multistage Graph</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Dimana</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">    </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">: </span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">    </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Cost (i,j) = Min(C(j,l) + Cost(i+1,l)}</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Dengan</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">   </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"> :</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">    </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">C(j,l) = Bobot edge j dan l</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left; text-indent: 0.5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">l = Elemen Vi+1 Dan
<j,l> eemen E</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left; text-indent: 0.5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">i=stage ke-I dan j = node
dalam V</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Proses dimulai dari k-2, dimana k adalah
banyak stage</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<br /></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Perhatikan contoh untuk menentukan biaya
termurah dari 1 hingga 12.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Diketahui graph dengan stage sebagai
berikut :</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgR2TteiVsiQybj2hJi5ESCUeq58f6fkQv5CvzqYm3HdqnSoS-3MsV54_RLZWRQri8irOF2wCRBS22JigGZ3ZMx_gUvNGzoZXbZEBd71SfQCELIG1IT5ytufJnkWrCoWSCKl3sTnASTaIst/s1600/m.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="248" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgR2TteiVsiQybj2hJi5ESCUeq58f6fkQv5CvzqYm3HdqnSoS-3MsV54_RLZWRQri8irOF2wCRBS22JigGZ3ZMx_gUvNGzoZXbZEBd71SfQCELIG1IT5ytufJnkWrCoWSCKl3sTnASTaIst/s1600/m.jpg" width="320" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0.0001pt; text-align: left;">
<span style="color: #262626; font-family: "Arial","sans-serif"; font-size: 12.0pt; mso-fareast-font-family: "Times New Roman";">Maka langkah-langkah
yang dilakukan adalah :</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: normal; margin-bottom: 0.0001pt; text-align: left;">
<br /></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">K=5, sehingga dimulai dari S3</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Cost(3,6) = Min{6+Cost(4,9); 5+Cost(4,10)}
= Min{6+4;5+2} = 7</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Cost(3,7) = Min{4+Cost(4,9); 3+Cost(4,10)}
= Min{4+4;3+2} = 5</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Cost(3,8) = Min{5+Cost(4,10); 6+Cost(4,11)}
= Min(5+2;6+5} = 7</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Cost(2,2) =
Min{4+Cost(3,6);2+Cost(3,7);1+Cost(3,8)}</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">= Min{4+7;2+5;1+7} = 7</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Cost(2,3) = Min{2+Cost(3,6); 7+Cost(3,7)} =
Min(2+7; 7+5) = 9</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Cost(2,4) = Min{11+Cost(3,8)} = 18</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Cost(2,5) = Min{11+Cost(3,7); 8+Cost(3,8)}
= Min(11+5;8+7} = 15</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Cost(1,1) =
Min{9+Cost(2,2);7+Cost(2,3);3+Cost(2,4),2+Cost(2,5)}</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">= Min{9+7;7+9;3+18;2+15} = 16</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<br /></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Shorthest Path menjadi :</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">1 </span><span style="color: #262626; font-family: "Times New Roman","serif"; font-size: 12.0pt; mso-fareast-font-family: "Times New Roman";">-> </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">3</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"> -> </span><span lang="IN" style="color: #262626; font-family: Symbol; font-size: 12.0pt; mso-ansi-language: IN; mso-ascii-font-family: "\0022sans-serif\0022"; mso-bidi-font-family: "Times New Roman"; mso-char-type: symbol; mso-fareast-font-family: "Times New Roman"; mso-hansi-font-family: "\0022sans-serif\0022"; mso-symbol-font-family: Symbol;"><span style="mso-char-type: symbol; mso-symbol-font-family: Symbol;"> </span></span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">6 </span><span style="color: #262626; font-family: "Times New Roman","serif"; font-size: 12.0pt; mso-fareast-font-family: "Times New Roman";">-> </span><span lang="IN" style="color: #262626; font-family: Symbol; font-size: 12.0pt; mso-ansi-language: IN; mso-ascii-font-family: "\0022sans-serif\0022"; mso-bidi-font-family: "Times New Roman"; mso-char-type: symbol; mso-fareast-font-family: "Times New Roman"; mso-hansi-font-family: "\0022sans-serif\0022"; mso-symbol-font-family: Symbol;"><span style="mso-char-type: symbol; mso-symbol-font-family: Symbol;"> </span></span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">10 </span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">-> </span><span lang="IN" style="color: #262626; font-family: Symbol; font-size: 12.0pt; mso-ansi-language: IN; mso-ascii-font-family: "\0022sans-serif\0022"; mso-bidi-font-family: "Times New Roman"; mso-char-type: symbol; mso-fareast-font-family: "Times New Roman"; mso-hansi-font-family: "\0022sans-serif\0022"; mso-symbol-font-family: Symbol;"><span style="mso-char-type: symbol; mso-symbol-font-family: Symbol;"> </span></span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">12 Atau  1 </span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">-> </span><span lang="IN" style="color: #262626; font-family: Symbol; font-size: 12.0pt; mso-ansi-language: IN; mso-ascii-font-family: "\0022sans-serif\0022"; mso-bidi-font-family: "Times New Roman"; mso-char-type: symbol; mso-fareast-font-family: "Times New Roman"; mso-hansi-font-family: "\0022sans-serif\0022"; mso-symbol-font-family: Symbol;"><span style="mso-char-type: symbol; mso-symbol-font-family: Symbol;"> </span></span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">2</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"> -> </span><span lang="IN" style="color: #262626; font-family: Symbol; font-size: 12.0pt; mso-ansi-language: IN; mso-ascii-font-family: "\0022sans-serif\0022"; mso-bidi-font-family: "Times New Roman"; mso-char-type: symbol; mso-fareast-font-family: "Times New Roman"; mso-hansi-font-family: "\0022sans-serif\0022"; mso-symbol-font-family: Symbol;"><span style="mso-char-type: symbol; mso-symbol-font-family: Symbol;"> </span></span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">7 </span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">-> </span><span lang="IN" style="color: #262626; font-family: Symbol; font-size: 12.0pt; mso-ansi-language: IN; mso-ascii-font-family: "\0022sans-serif\0022"; mso-bidi-font-family: "Times New Roman"; mso-char-type: symbol; mso-fareast-font-family: "Times New Roman"; mso-hansi-font-family: "\0022sans-serif\0022"; mso-symbol-font-family: Symbol;"><span style="mso-char-type: symbol; mso-symbol-font-family: Symbol;"> </span></span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">10</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">-> </span><span lang="IN" style="color: #262626; font-family: Symbol; font-size: 12.0pt; mso-ansi-language: IN; mso-ascii-font-family: "\0022sans-serif\0022"; mso-bidi-font-family: "Times New Roman"; mso-char-type: symbol; mso-fareast-font-family: "Times New Roman"; mso-hansi-font-family: "\0022sans-serif\0022"; mso-symbol-font-family: Symbol;"><span style="mso-char-type: symbol; mso-symbol-font-family: Symbol;"> </span></span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">12</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Jika ada dua atau lebih shorthest path maka
total biaya harus sama.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Shortest Path Pertama adalah :</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"><br /></span></div>
<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhFsf8yrvzacF77rCWMRrtOz13RoJ6dPoi5YWRoK2kLruaK0mxqkGjhB1_IxFkTiXLy75McRTK2OgCZUw_gO1qvdJ1gnDZcgdBw4pYX3meAkg58s_CiWniXqc-cvIV_LenHsFv1Oj8Z3D-5/s1600/n.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhFsf8yrvzacF77rCWMRrtOz13RoJ6dPoi5YWRoK2kLruaK0mxqkGjhB1_IxFkTiXLy75McRTK2OgCZUw_gO1qvdJ1gnDZcgdBw4pYX3meAkg58s_CiWniXqc-cvIV_LenHsFv1Oj8Z3D-5/s1600/n.jpg" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Shortest Path Kedua adalah :</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhw3v0_Ni1giCO4dCkFLexJ6Gus8QBsLy4a0XeKfoLNkz3ZiKMHAdgeKhog3Q7HhC16HrmH-XA-qGXH4Ba-OHgr-jhGiuKajujpjQ5skq8CSIZyh5GxhYkdmC8WoJ9tEqr9HVRLwzFudoOA/s1600/o.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhw3v0_Ni1giCO4dCkFLexJ6Gus8QBsLy4a0XeKfoLNkz3ZiKMHAdgeKhog3Q7HhC16HrmH-XA-qGXH4Ba-OHgr-jhGiuKajujpjQ5skq8CSIZyh5GxhYkdmC8WoJ9tEqr9HVRLwzFudoOA/s1600/o.jpg" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<br />
<br />
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<span style="color: black; font-family: "Cambria","serif"; font-size: 13.5pt; mso-ascii-theme-font: major-latin; mso-bidi-font-family: Arial; mso-fareast-font-family: "Times New Roman"; mso-hansi-theme-font: major-latin;"><o:p><br /></o:p></span></div>
<div class="MsoNormal" style="line-height: 18pt; margin-bottom: 0.0001pt; text-align: left;">
<br /></div>
</p>

F. Shortest Path Pencarian shortest path (lintasan terpendek) adalah masalah umum dalam suatu weighted, connected graph. Misal : Penca...