Algoritma Dijkstra di C++
Algoritma Dijkstra adalah algoritma grafis yang digunakan untuk menemukan jalur terpendek dari satu titik awal ke semua titik lain dalam graf berbobot. Algoritma ini bekerja dengan menandai titik-titik yang telah dikunjungi dan memperbarui jarak terpendek ke titik-titik yang belum dikunjungi.
Cara Kerja Algoritma Dijkstra
-
Inisialisasi:
- Tentukan titik awal sebagai sumber (source).
- Atur jarak dari sumber ke semua titik lain menjadi tak terhingga (infinity).
- Atur jarak dari sumber ke dirinya sendiri menjadi 0.
- Buat set kosong yang berisi titik-titik yang belum dikunjungi.
-
Iterasi:
- Pilih titik dengan jarak terpendek dari sumber yang belum dikunjungi.
- Tandai titik tersebut sebagai dikunjungi.
- Perbarui jarak terpendek ke titik-titik yang bertetangga dengan titik yang baru dikunjungi.
-
Ulangi langkah 2:
- Ulangi langkah 2 sampai semua titik telah dikunjungi.
Implementasi Algoritma Dijkstra di C++
Berikut adalah contoh implementasi algoritma Dijkstra di C++:
#include
#include
#include
#include
using namespace std;
#define INF numeric_limits::max()
// Struktur untuk menyimpan informasi tentang graf
struct Edge {
int to;
int weight;
};
// Fungsi untuk menerapkan algoritma Dijkstra
vector dijkstra(vector>& graph, int source) {
int n = graph.size();
vector distance(n, INF);
distance[source] = 0;
priority_queue, vector>, greater>> pq;
pq.push({0, source});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto& edge : graph[u]) {
int v = edge.to;
int weight = edge.weight;
if (distance[u] + weight < distance[v]) {
distance[v] = distance[u] + weight;
pq.push({distance[v], v});
}
}
}
return distance;
}
int main() {
// Contoh graf
vector> graph = {
{{1, 2}, {2, 5}},
{{0, 2}, {2, 1}, {3, 4}},
{{0, 5}, {1, 1}, {3, 3}},
{{1, 4}, {2, 3}}
};
int source = 0;
// Menjalankan algoritma Dijkstra
vector shortestDistances = dijkstra(graph, source);
// Menampilkan jarak terpendek dari sumber ke semua titik lain
cout << "Jarak terpendek dari titik " << source << ": " << endl;
for (int i = 0; i < shortestDistances.size(); i++) {
cout << "Ke titik " << i << ": " << shortestDistances[i] << endl;
}
return 0;
}
Penggunaan Algoritma Dijkstra
Algoritma Dijkstra memiliki banyak aplikasi dalam berbagai bidang, seperti:
- Sistem navigasi: Menemukan jalur terpendek antara dua titik.
- Jaringan komputer: Menentukan jalur tercepat untuk mengirimkan data.
- Perencanaan rute: Mencari rute terpendek antara dua lokasi.
- Analisis jaringan: Menilai kinerja jaringan.
Kesimpulan
Algoritma Dijkstra merupakan algoritma yang powerful dan mudah diimplementasikan untuk menemukan jalur terpendek dalam graf. Algoritma ini memiliki banyak aplikasi dalam berbagai bidang dan merupakan alat yang penting dalam banyak bidang ilmu komputer dan teknik.