Algoritma penentuan lintasan terpendek untuk semua pasangan simpul

Abstract

Graf merupakan pasangan terurut (V,E), dimana V adalah himpunan tak kosong dan terbatas yang anggotanya disebut simpul (vertex) dan E adalah himpunan sisi (edge). Hubungan antara simpul dan sisi tersebut membentuk suatu jaringan (network). Selanjutnya, dari jaringan tersebut dapat ditentukan lintasan(path) yang dilalui untuk suatu pasangan simpul, tetapi masalah yang penting dalam hal ini adalah menentukan Iintasan terpendek (shortest path) di antara Iintasan-Iintasan yang mungkin dari pasangan simpuI tersebut. Hal ini menarik, karena berkaitan dengan masalah pengoptimuman, antara lain meminimumkan biaya dan efisiensi waktu yang digunakan.