Pada tahun 1959 sebuah tulisan sepanjang tiga halaman yang berjudul A Note on Two Problems in Connexion with Graphs diterbitkan padajurnalNumerische Mathematik. Padatulisanini, Edsger W. Dijkstra - seorangilmuwan computer berumur duapuluh sembilantahun mengusulkan algoritma-algoritma untuk solusi dari dua masalah teoritis graf dasar: the minimum weight Algoritma Dijkstra untuk masalah jalan terpendek adalah satu dari algoritma - algoritma paling ternama pada ilmu komputer dan sebuah algoritma paling popular pada oparasi pencarian (OR).
Implementasi algoritma dijkstra. Algoritma ini termasuk algoritma pencarian graf yang digunakan untuk menyelesaikan masalah lintasan terpendek dengan satu sumber pada sebuah graf yang tidak memiliki cost sisi negatif, dan menghasilkan sebuah pohon lintasan. Algoritma ini menggunakan prinsip greedy yang digunakan untuk menyatakan bahwa pada setiap langkah kita memilih sisi yang berbobot minimum dan memasukannya ke dalam himpunan solusi. Akan tetapi bobot dari graf tersebut harus bernilai bilangan positif (bobot >= 0). Algoritma ini untuk menggambarkan jarak kedua tempat dengan jarak yang digambarkan secara singkat .
 |
| contoh skema algoritma dijsktra |
0 comments:
Post a Comment