Electronic Theses and Dissertation

Skripsi ini membahas tentang penentuan lintasan terpendek pada suatu graf berbobot. lintasan terpendek merupakan lintasan minimum dari suatu vertex asal ke vertex tujuan. dalam hal ini, algoritma yang digunakan adalah algoritma dijsktra dan floyd-warshall. untuk algoritma dijsktra metode yang dipakai adalah metode greedy, sementara itu, untuk floyd-warshall menggunakan pemograman dinamis. dengan menggunakan dijskira diperoleh sebuah lintasan dalam bentuk spanning tree sedangkan dengan menggunakan floyd-warshall diperoleh lintasan dalam bentuk matriks hubung. kata kunci : lintasan terpendek, sisi, simpul, bobot, algoritma dijskira, algoritma floyd- warshall.