Mencari Jalur Tersingkat Menggunakan Algoritma Dijkstra
Algoritma Dijkstra, yang merupakan salah satu algoritma terkenal dalam teori graf untuk mencari jalur terpendek dari satu titik (node) ke semua titik lain dalam graf berbobot positif.
Graf berbobot (weighted graph), adalah graf yang memiliki bobot (nilai numerik) pada setiap sisi (edge) antar-node. Algoritma ini mencari jalur terpendek dari satu titik awal (source node) ke semua titik lain (destination nodes) dalam graf tersebut.
Algoritma
-
Mulai dari titik awal (source node) dan inisialisasi jaraknya menjadi 0, sedangkan jarak semua titik lainnya diinisialisasi dengan nilai tak terhingga (atau nilai yang cukup besar sebagai representasi tak terhingga).
-
Pilih titik dengan jarak terpendek dari titik awal yang belum termasuk dalam himpunan titik-titik yang sudah diproses.
-
Perbarui jarak dari titik-titik tetangga yang terhubung langsung dengan titik yang dipilih. Jika jarak baru yang dihitung lebih kecil dari jarak sebelumnya, maka perbarui jaraknya.
-
Tandai titik yang sudah diproses dan lanjutkan ke langkah 2 sampai semua titik telah diproses.
Setelah algoritma Dijkstra selesai dijalankan, hasil yang diperoleh adalah jarak terpendek dari titik awal ke semua titik lain dalam graf. Algoritma ini berguna dalam berbagai aplikasi, seperti perencanaan rute, jaringan komputer, dan optimasi logistik.
Biografi
Algoritma Dijkstra dinamai setelah seorang ilmuwan komputer bernama Edsger W. Dijkstra. Edsger Dijkstra adalah seorang matematikawan, ilmuwan komputer, dan penerima Penghargaan Turing (Turing Award) 1972 atas kontribusinya pada bidang ilmu komputer.
Ia mengembangkan algoritma Dijkstra pada 1956 saat bekerja di Technological University of Eindhoven (sekarang dikenal sebagai Eindhoven University of Technology) di Belanda. Algoritma Dijkstra \ diterbitkan dalam artikel berjudul "A Note on Two Problems in Connexion with Graphs."
Berkat kontribusinya dalam algoritma dan teori graf lain, Edsger Dijkstra diakui sebagai salah seorang tokoh paling berpengaruh dalam ilmu komputer. Algoritma Dijkstra menjadi salah satu algoritma terpenting dan paling sering digunakan dalam mencari jalur terpendek pada graf berbobot positif.
Contoh penerapan
# include
# define INFINITY 999
using namespace std;
class Dijkstra{
private:
int adjMatrix[15][15];
int predecessor[15],distance[15];
bool mark[15]; //keep track of visited node
int source;
int numOfVertices;
public:
/*
* Fungsi read() membaca jumlah verteks, Matriks Ketetanggaan, dan sumber
* Matriks dari pengguna. Jumlah verteks harus lebih besar dari nol,
* semua anggota Matriks Ketetanggaan harus positif karena jarak selalu positif.
* Verteks sumber juga harus positif dari 0 hingga noOfVertices - 1
*/
void read();
/*
* Fungsi initialize menginisialisasi semua anggota data pada awal eksekusi.
* Jarak antara sumber ke sumber adalah nol, dan semua jarak lain antara sumber
* dan verteks-verteksnya diatur menjadi tak terhingga. Tanda (mark) diinisialisasi
* menjadi false dan pendahulu (predecessor) diinisialisasi menjadi -1.
*/
void initialize();
/*
* Fungsi getClosestUnmarkedNode mengembalikan simpul yang paling dekat dari simpul
* yang telah ditandai sebelumnya (Predecessor). Jika simpul tersebut sudah ditandai sebagai
* dikunjungi, maka fungsi ini mencari simpul lain yang belum ditandai.
*/
int getClosestUnmarkedNode();
/*
* Fungsi calculateDistance menghitung jarak minimum dari node sumber ke
* node lainnya.
*/
void calculateDistance();
/*
* Fungsi output mencetak hasil-hasil
*/
void output();
void printPath(int);
};
void Dijkstra::read(){
cout < < "Jumlah vertices: \n";
cin >>numOfVertices;
while(numOfVertices < = 0) {
cout < < "Jumlah vertices: \n";
cin>>numOfVertices;
}
cout < < "Enter the adjacency matrix for the graph\n";
cout < < "To enter infinity enter " < >adjMatrix[i][j];
while(adjMatrix[i][j] < 0) {
cout < < "Weights should be +ve. Enter the weight again\n";
cin>>adjMatrix[i][j];
}
}
}
cout < < "Enter the source vertex\n";
cin>>source;
while((source < 0) && (source>numOfVertices-1)) {
cout < < "Source vertex should be between 0 and" < >source;
}
}
voidpre Dijkstra::initialize(){
for(int i=0;i= distance[i])) {
minDistance = distance[i];
closestUnmarkedNode = i;
}
}
return closestUnmarkedNode;
}
void Dijkstra::calculateDistance(){
initialize();
int minDistance = INFINITY;
int closestUnmarkedNode;
int count = 0;
while(count < numOfVertices) {
closestUnmarkedNode = getClosestUnmarkedNode();
mark[closestUnmarkedNode] = true;
for(int i=0;i0) ) {
if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) {
distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i];
predecessor[i] = closestUnmarkedNode;
}
}
}
count++;
}
}
void Dijkstra::printPath(int node){
if(node == source)
cout < < (char)(node + 97) < < "..";
else if(predecessor[node] == -1)
cout < < "No path from “ < " <