Soal 12.13.
Untuk setiap simpul \(x\text{,}\) carilah jarak dari \(r\) ke \(x\text{.}\) Carilah pula lintasan terpendek dari \(r\) ke \(x\text{.}\)
Subbab 12.3 Algoritma Dijkstra untuk Lintasan Terpendek
Seperti pada graf, pemberian bobot pada sisi-sisi berarah suatu digraf juga berguna. Secara khusus, dalam bagian ini kita meninjau pasangan \((\bfG,w)\text{,}\) dengan \(\GVE\) suatu digraf dan \(w\colon E\rightarrow\nonnegints\) suatu fungsi yang memberikan kepada setiap sisi berarah \((x,y)\) bobot nonnegatif \(w(x,y)\text{.}\) Namun, dalam bagian ini kita menafsirkan bobot sebagai jarak, sehingga \(w(x,y)\) disebut panjang sisi \((x,y)\text{.}\) Jika \(P=(r=u_0,u_1,\dots,u_t=x)\) adalah lintasan berarah dari \(r\) ke \(x\text{,}\) maka panjang lintasan \(P\) adalah jumlah panjang sisi-sisi pada lintasan itu, yaitu \(\sum_{i=0}^{t-1} w(u_i,u_{i+1})\text{.}\) Jarak dari \(r\) ke \(x\) kemudian didefinisikan sebagai panjang minimum suatu lintasan berarah dari \(r\) ke \(x\text{.}\) Tujuan kita dalam bagian ini adalah menyelesaikan masalah alami berikut, yang mempunyai banyak penerapan:
Subbagian 12.3.1 Deskripsi Algoritma
Agar algoritma Dijkstra dapat dijelaskan secara ringkas, kita perlu memperluas definisi fungsi \(w\text{.}\) Kita menetapkan \(w(x,y)=\infty\) apabila \(x\neq y\) dan \((x,y)\) bukan sisi berarah dari \(\bfG\text{.}\) Dengan cara ini, kita akan memperlakukan \(\infty\) seolah-olah merupakan bilangan (padahal bukan!).
1
Hal ini tidak menimbulkan masalah dalam implementasi komputer. Alih-alih menggunakan \(\infty\text{,}\) kita dapat menyimulasikan tak hingga dengan nilai berupa hasil kali banyaknya simpul dan bobot sisi maksimum.
Sekarang kita siap menjelaskan Algoritma Dijkstra.
Algoritma 12.14. Algoritma Dijkstra.
Misalkan \(n=|V|\text{.}\) Pada Langkah \(i\text{,}\) dengan \(1\le i\le n\text{,}\) kita telah menentukan:
-
Suatu barisan simpul berbeda \(\sigma=(v_1,v_2,v_3,\dots,v_i)\) dari \(\bfG\text{,}\) dengan \(r=v_1\text{.}\) Simpul-simpul ini disebut simpul permanen, sedangkan simpul-simpul yang tersisa disebut simpul sementara.
-
Untuk setiap simpul \(x\in V\text{,}\) kita telah menentukan bilangan \(\delta(x)\) dan lintasan \(P(x)\) dari \(r\) ke \(x\) yang panjangnya \(\delta(x)\text{.}\)
- Inisialisasi (Langkah 1)
-
Tetapkan \(i=1\text{.}\) Tetapkan \(\delta(r)=0\) dan misalkan \(P(r)=(r)\) lintasan trivial yang hanya terdiri atas satu titik. Tetapkan pula \(\sigma= (r)\text{.}\) Untuk setiap \(x\neq r\text{,}\) tetapkan \(\delta(x)= w(r,x)\) dan \(P(x)=(r,x)\text{.}\) Misalkan \(x\) suatu simpul sementara yang meminimumkan \(\delta(x)\text{.}\) Tetapkan \(v_2 = x\text{,}\) lalu perbarui \(\sigma\) dengan menambahkan \(v_2\) di ujungnya. Naikkan \(i\) sebesar satu.
- Langkah Induktif (Langkah \(i\text{,}\) \(i>1\))
-
Jika \(i\lt n\text{,}\) maka untuk setiap simpul sementara \(x\text{,}\) tetapkan\begin{equation*} \delta(x) = \min\{\delta(x), \delta(v_i)+w(v_i,x)\}. \end{equation*}Jika penetapan ini menurunkan nilai \(\delta(x)\text{,}\) misalkan \(P(x)\) lintasan yang diperoleh dengan menambahkan \(x\) ke ujung \(P(v_i)\text{.}\)Misalkan \(x\) suatu simpul sementara yang meminimumkan \(\delta(x)\text{.}\) Tetapkan \(v_{i+1}=x\text{,}\) lalu perbarui \(\sigma\) dengan menambahkan \(v_{i+1}\) di ujungnya. Naikkan \(i\) sebesar satu.
Subbagian 12.3.2 Contoh Algoritma Dijkstra
Sebelum membuktikan mengapa algoritma Dijkstra bekerja, ada baiknya kita melihat sebuah contoh. Tinjau digraf \(\bfG\) pada Gambar 12.15. Agar gambarnya jelas, kita memilih digraf yang merupakan graf berorientasi, i.e., untuk setiap pasangan simpul berbeda \(x,y\text{,}\) graf memuat paling banyak satu dari dua kemungkinan sisi berarah \((x,y)\) dan \((y,x)\text{.}\)
Digraf dengan panjang sisi
Misalkan simpul akar \(r\) adalah simpul berlabel \(a\text{.}\) Langkah inisialisasi algoritma Dijkstra kemudian menghasilkan nilai-nilai \(\delta\) dan \(P\) berikut:
Langkah 1. Inisialisasi.
\begin{align*}
\sigma\amp=(a)\amp\amp\\
\delta(a)\amp=0; \amp P(a)\amp=(a)\\
\delta(b) \amp=\infty; \amp P(b)\amp=(a,b)\\
\delta(c) \amp=47; \amp P(c)\amp=(a,c)\\
\delta(d) \amp=\infty; \amp P(d)\amp=(a,d)\\
\delta(e) \amp=70; \amp P(e)\amp=(a,e)\\
\delta(f) \amp=24; \amp P(f)\amp=(a,f)\\
\delta(g) \amp=\infty; \amp P(g)\amp=(a,g)\\
\delta(h) \amp=\infty; \amp P(h)\amp=(a,h)
\end{align*}
Sebelum menyelesaikan Langkah 1, algoritma mengenali simpul \(f\) sebagai simpul terdekat dengan \(a\) dan menambahkannya ke \(\sigma\text{,}\) sehingga \(f\) menjadi permanen. Ketika memasuki Langkah 2, algoritma Dijkstra berusaha mencari lintasan yang lebih pendek dari \(a\) ke setiap simpul sementara dengan melewati \(f\text{.}\) Proses ini kita sebut “pemindaian dari simpul \(f\text{.}\)” Dalam pemindaian ini, lintasan menuju simpul \(d\) diperbarui karena \(\delta(f) + w(f,d)=24+120=144\lt \infty=w(a,d)\text{.}\)
Langkah 2. Pemindaian dari simpul \(f\).
\begin{align*}
\sigma\amp=(a,f)\amp\amp\\
\delta(a)\amp=0; \amp P(a)\amp=(a)\\
\delta(b)\amp=\infty; \amp P(b)\amp=(a,b)\\
\delta(c)\amp=47; \amp P(c)\amp=(a,c)\\
\delta(d)\amp=144 = 24 + 120 = \delta(f)+w(f,d); \amp P(d)\amp=(a,f,d)\quad\text{diperbarui} \\
\delta(e)\amp=70; \amp P(e)\amp=(a,e)\\
\delta(f)\amp=24; \amp P(f)\amp=(a,f)\\
\delta(g)\amp=\infty; \amp P(g)\amp=(a,g)\\
\delta(h)\amp=\infty; \amp P(h)\amp=(a,h)
\end{align*}
Sebelum beralih ke langkah berikutnya, simpul \(c\) dijadikan permanen dengan menetapkannya sebagai \(v_3\text{.}\) Karena itu, pada Langkah 3 pemindaian dilakukan dari simpul \(c\text{.}\) Lintasan menuju simpul \(b\text{,}\) \(d\text{,}\) dan \(g\) diperbarui. Akan tetapi, meskipun \(\delta(c) + w(c,e) = 47+23=70=\delta(e)\text{,}\) kita tidak mengubah \(P(e)\) karena \(\delta(e)\) tidak menurun ketika \(P(e)\) dirutekan melalui \(c\text{.}\)
Langkah 3. Pemindaian dari simpul \(c\).
\begin{align*}
\sigma\amp=(a,f,c)\\
\delta(a)\amp=0; \amp P(a)\amp=(a)\\
\delta(b)\amp=102=47+55= \delta(c)+w(c,b); \amp P(b)\amp=(a,c,b)\quad\text{diperbarui}\\
\delta(c)\amp=47; \amp P(c)\amp=(a,c)\\
\delta(d)\amp=135=47+88 = \delta(c)+w(c,d); \amp P(d)\amp=(a,c,d)\quad\text{diperbarui} \\
\delta(e)\amp=70; \amp P(e)\amp=(a,e)\\
\delta(f)\amp=24; \amp P(f)\amp=(a,f)\\
\delta(g)\amp=113=47+66= \delta(c)+w(c,g); \amp P(g)\amp=(a,c,g)\quad\text{diperbarui} \\
\delta(h)\amp=\infty; \amp P(h)\amp=(a,h)
\end{align*}
Sekarang simpul \(e\) dijadikan permanen.
Langkah 4. Pemindaian dari simpul \(e\).
\begin{align*}
\sigma\amp=(a,f,c,e)\\
\delta(a)\amp=0; \amp P(a)\amp=(a)\\
\delta(b)\amp=101=70+31= \delta(e)+w(e,b); \amp P(b)\amp=(a,e,b)\quad\text{diperbarui}\\
\delta(c)\amp=47; \amp P(c)\amp=(a,c)\\
\delta(d)\amp=135; \amp P(d)\amp=(a,c,d)\\
\delta(e)\amp=70; \amp P(e)\amp=(a,e)\\
\delta(f)\amp=24; \amp P(f)\amp=(a,f)\\
\delta(g)\amp=112=70+42= \delta(e)+w(e,g); \amp P(g)\amp=(a,e,g)\quad\text{diperbarui}\\
\delta(h)\amp=\infty; \amp P(h)\amp=(a,h)
\end{align*}
Sekarang simpul \(b\) dijadikan permanen.
Langkah 5. Pemindaian dari simpul \(b\).
\begin{align*}
\sigma\amp=(a,f,c,e,b)\\
\delta(a)\amp=0; \amp P(a)\amp=(a)\\
\delta(b)\amp=101; \amp P(b)\amp=(a,e,b)\\
\delta(c)\amp=47; \amp P(c)\amp=(a,c)\\
\delta(d)\amp= 132 = 101+ 31= \delta(b)+w(b,d); \amp P(d)\amp=(a,e,b,d)\quad\text{diperbarui} \\
\delta(e)\amp= 70; \amp P(e)\amp=(a,e)\\
\delta(f)\amp= 24; \amp P(f)\amp=(a,f)\\
\delta(g)\amp=112; \amp P(g)\amp=(a,e,g)\\
\delta(h)\amp=180 = 101+79=\delta(b)+w(b,h); \amp P(h)\amp=(a,e,b,h)\quad\text{diperbarui}
\end{align*}
Sekarang simpul \(g\) dijadikan permanen.
Langkah 6. Pemindaian dari simpul \(g\).
\begin{align*}
\sigma\amp=(a,f,c,e,b,g)\\
\delta(a)\amp=0; \amp P(a)\amp=(a)\\
\delta(b)\amp=101; \amp P(b)\amp=(a,e,b)\\
\delta(c)\amp=47; \amp P(c)\amp=(a,c)\\
\delta(d)\amp= 132; \amp P(d)\amp=(a,e,b,d)\\
\delta(e)\amp=70; \amp P(e)\amp=(a,e)\\
\delta(f)\amp=24; \amp P(f)\amp=(a,f)\\
\delta(g)\amp=112; \amp P(g)\amp=(a,e,g)\\
\delta(h)\amp=178 = 112+66=\delta(g)+w(g,h); \amp P(h)\amp=(a,e,g,h)\quad\text{diperbarui}
\end{align*}
Sekarang simpul \(d\) dijadikan permanen.
Langkah 7. Pemindaian dari simpul \(d\).
\begin{align*}
\sigma\amp=(a,f,c,e,b,g,d)\\
\delta(a)\amp=0; \amp P(a)\amp=(a)\\
\delta(b)\amp=101; \amp P(b)\amp=(a,e,b)\\
\delta(c)\amp=47; \amp P(c)\amp=(a,c)\\
\delta(d)\amp= 132; \amp P(d)\amp=(a,e,b,d)\\
\delta(e)\amp=70; \amp P(e)\amp=(a,e)\\
\delta(f)\amp=24; \amp P(f)\amp=(a,f)\\
\delta(g)\amp=112; \amp P(g)\amp=(a,e,g)\\
\delta(h)\amp=161 = 132+29=\delta(d)+w(d,h); \amp P(h)\amp=(a,e,b,d,h)\quad\text{diperbarui}
\end{align*}
Sekarang simpul \(h\) dijadikan permanen. Karena ini adalah simpul terakhir, algoritma berhenti dan memberikan hasil berikut:
Hasil Akhir Algoritma Dijkstra.
\begin{align*}
\sigma\amp=(a,f,c,e,b,g,d,h)\\
\delta(a)\amp=0; \amp P(a)\amp=(a)\\
\delta(b)\amp=101; \amp P(b)\amp=(a,e,b)\\
\delta(c)\amp=47; \amp P(c)\amp=(a,c)\\
\delta(d)\amp= 132; \amp P(d)\amp=(a,e,b,d)\\
\delta(e)\amp=70; \amp P(e)\amp=(a,e)\\
\delta(f)\amp=24; \amp P(f)\amp=(a,f)\\
\delta(g)\amp=112; \amp P(g)\amp=(a,e,g)\\
\delta(h)\amp=161; \amp P(h)\amp=(a,e,b,d,h)
\end{align*}
Subbagian 12.3.3 Kebenaran Algoritma Dijkstra
Setelah melihat ilustrasi algoritma Dijkstra, kini saatnya membuktikan bahwa algoritma ini benar-benar melakukan apa yang kita nyatakan: mencari jarak dari simpul akar ke setiap simpul lainnya beserta lintasan yang memiliki panjang tersebut. Untuk itu, mula-mula kita nyatakan dua proposisi dasar. Proposisi pertama membahas lintasan terpendek secara umum, sedangkan proposisi kedua khusus mengenai barisan simpul permanen yang dihasilkan oleh algoritma Dijkstra.
Proposisi 12.16.
Misalkan \(x\) suatu simpul dan \(P=(r=u_0,u_1,\dots,u_t=x)\) suatu lintasan terpendek dari \(r\) ke \(x\text{.}\) Maka, untuk setiap bilangan bulat \(j\) dengan \(0\lt j\lt t\text{,}\) \((u_0,u_1,\dots,u_j)\) merupakan lintasan terpendek dari \(r\) ke \(u_j\text{,}\) dan \((u_j,u_{j+1},\dots,u_t)\) merupakan lintasan terpendek dari \(u_j\) ke \(u_t\text{.}\)
Proposisi 12.17.
Ketika algoritma berhenti, misalkan \(\sigma=(v_1,v_2,v_3,\dots,v_n)\text{.}\) Maka
\begin{equation*}
\delta(v_1)\le \delta(v_2)\le\dots \le \delta(v_n).
\end{equation*}
Sekarang kita siap membuktikan kebenaran algoritma. Bukti yang kita berikan bersifat induktif, tetapi induksinya tidak berkaitan dengan jumlah seluruh simpul dalam digraf ataupun nomor langkah yang sedang dijalankan algoritma.
Teorema 12.18.
Algoritma Dijkstra menghasilkan lintasan terpendek bagi setiap simpul \(x\) dalam \(\bfG\text{.}\) Artinya, ketika algoritma Dijkstra berhenti, untuk setiap \(x\in V\text{,}\) nilai \(\delta(x)\) merupakan jarak dari \(r\) ke \(x\) dan \(P(x)\) merupakan lintasan terpendek dari \(r\) ke \(x\text{.}\)
Bukti.
Teorema ini berlaku secara trivial ketika \(x=r\text{.}\) Jadi, kita meninjau kasus \(x\neq r\text{.}\) Kita membuktikan bahwa \(\delta(x)\) merupakan jarak dari \(r\) ke \(x\) dan bahwa \(P(x)\) merupakan lintasan terpendek dari \(r\) ke \(x\) melalui induksi pada banyaknya sisi minimum \(k\) dalam lintasan terpendek dari \(r\) ke \(x\text{.}\) Ketika \(k=1\text{,}\) sisi \((r,x)\) merupakan lintasan terpendek dari \(r\) ke \(x\text{.}\) Karena \(v_1=r\text{,}\) kita menetapkan \(\delta(x)=w(r,x)\) dan \(P(x)=(r,x)\) pada Langkah 1.
Sekarang tetapkan suatu bilangan bulat positif \(k\text{.}\) Andaikan bahwa jika banyaknya sisi minimum dalam suatu lintasan terpendek dari \(r\) ke \(x\) paling banyak \(k\text{,}\) maka \(\delta(x)\) merupakan jarak dari \(r\) ke \(x\) dan \(P(x)\) merupakan lintasan terpendek dari \(r\) ke \(x\text{.}\) Misalkan \(x\) suatu simpul yang banyaknya sisi minimum dalam lintasan terpendek dari \(r\) ke \(x\) adalah \(k+1\text{.}\) Tetapkan suatu lintasan terpendek \(P=(u_0,u_1,u_2,\dots,u_{k+1})\) dari \(r=u_0\) ke \(x=u_{k+1}\text{.}\) Maka \(Q=(u_0,u_1,\dots,u_k)\) merupakan lintasan terpendek dari \(r\) ke \(u_k\text{.}\) (Lihat Gambar 12.19.)
Lintasan-lintasan terpendek
Menurut hipotesis induksi, \(\delta(u_k)\) adalah jarak dari \(r\) ke \(u_k\text{,}\) dan \(P(u_k)\) merupakan lintasan terpendek dari \(r\) ke \(u_k\text{.}\) Perhatikan bahwa \(P(u_k)\) tidak harus sama dengan lintasan \(Q\text{,}\) seperti yang ditunjukkan dalam Gambar 12.19. Namun, jika berbeda, kedua lintasan itu mempunyai panjang yang sama, yaitu \(\delta(u_k)\text{.}\) Selain itu, jarak dari \(r\) ke \(x\) adalah \(\delta(u_k)+w(u_k,x)\ge \delta(u_k)\) karena \(P\) merupakan lintasan terpendek dari \(r\) ke \(x\) dan \(w(u_k,x)\geq 0\text{.}\)
Misalkan \(i\) dan \(j\) bilangan bulat tunggal yang memenuhi \(u_k=v_i\) dan \(x=v_j\text{.}\) Jika \(j \lt i\text{,}\) maka
\begin{equation*}
\delta(x)= \delta(v_j)\le \delta(v_i)= \delta(u_k)\le
\delta(u_k)+w(u_k,x).
\end{equation*}
Jadi, algoritma telah menemukan lintasan \(P(x)\) dari \(r\) ke \(x\) yang panjangnya \(\delta(x)\text{,}\) yang paling besar sama dengan jarak dari \(r\) ke \(x\text{.}\) Jelas bahwa ini menyiratkan \(\delta(x)\) merupakan jarak dari \(r\) ke \(x\) dan \(P(x)\) merupakan lintasan terpendek.
Di sisi lain, jika \(j>i\text{,}\) maka langkah induktif pada Langkah \(i\) menghasilkan
\begin{equation*}
\delta(x)\le \delta(v_i)+w(v_i,x)=\delta(u_k)+w(u_k,x).
\end{equation*}
Seperti sebelumnya, ini menyiratkan bahwa \(\delta(x)\) merupakan jarak dari \(r\) ke \(x\) dan \(P(x)\) merupakan lintasan terpendek.
