Electronic Theses and Dissertation

Graf lengkap merupakan graf sederhana yang setiap vertexnya mempunyai sisi ke semua vertex lainnya, sedangkan graf lengkap bebobot adalah graf lengkap yang setiap sisinya memiliki bobot. skripsi ini membahas tentang penentuan lintasan terpendek pada suatu graf lengkap berbobot dengan tujub vertex (k7) menggunakan program dinamis. lintasan terpendek pada graf adalah sebuah lintasan yang memiliki jumjah bobot sisi yang paling minimum. dalam hal ini bobot merupakan jarak antara setiap pasang vertex. program dinamis merupakan salah satu metode pemecahan masalah penentuan lintasan terpendek suatu graf yaitu dengan cara menguraikan solusi menjadi sekumpulan langkah atau tahapan sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. program dinamis menghitung bobot terkecil dari semua sisi yang menghubungkan sebuah pasangan vertex, dilakukan sekaligus untuk semua pasangan vertex. penentuan lintasan terpendek menggunakan program dinamis menghasilkan suatu matriks hubung. matriks bubung digunakan untuk menyatakan graf yang sisinya menghubungkan setiap vertex. kata kunci : lintasan terpendek, graf, vertex, program dinamis, matriks hubung.