Modul 3 (Shortest Path)
Shortest Path adalah sebuah permasalahan untuk mencari path terdekat (memiliki weight minimal) antara 2 vertex dalam satu graf. Terdapat beberapa algoritma untuk menyelesaikan permasalahan tersebut. Di bawah ini adalah tabel yang berisi algoritma yang digunakan untuk menyelesaikan permasalahan Single Source Shortest Path:
| Algoritma | Kompleksitas Waktu |
|---|---|
| Breadth First Search | O( |
| Dijkstra (dengan list) | O( |
| Dijkstra (dengan pqueue) | O( |
| Bellman-Ford | O( |
Pada unweighted graph, permasalahan shortest path dapat dilakukan menggunakan BFS (Breadth First Search) seperti biasa.
Karena terdapat weight pada tiap-tiap edge, menggunakan BFS saja tidak akan mendapatkan hasil yang optimal, dan perlu menggunakan algoritma lain seperti Dijkstra atau Bellman-Ford. Modul ini hanya akan membahas Algoritma Dijkstra.
Algoritma Dijkstra sendiri mempunyai banyak variasi, tapi yang paling umum adalah untuk mencari shortest path dari source vertex ke semua vertex lainnya.
-
Set semua jarak vertex dengan infinity (dapat digantikan dengan nilai yang sangat besar atau nilai yang tidak akan terpakai) kecuali jarak dari source yang akan di-set 0.
-
Push vertex source ke min-priority queue (priority queue dengan pengurutan dari kecil ke besar) dengan format (distance, vertex), untuk pembanding dari min-priority queue akan menggunakan distance dari vertex.
-
Pop vertex dengan distance yang paling minimum dari priority queue
-
Update distance dari vertex yang terhubung ke vertex yang telah di-pop (vertex dari hasil langkah ke-3) dengan case “distance vertex yang sekarang + edge weight < next vertex distance”, lalu push vertex tersebut.
-
Apabila hasil dari pop vertex tersebut telah di visit sebelumnya, maka lakukan continue.
-
Lakukan langkah ke-3 sampai ke-5 hingga priority queue kosong.
Cari shortest path dari vertex A ke semua vertex lainnya.
Inisial:
Step 1:
Step 2:
Step 3:
Step 4:
Step 5:
void dijkstra(vector<long> &result, long start){
vector<bool> visited(vertexCount, false);
priority_queue <pair<long, long>,
vector <pair<long, long>>,
greater <pair<long, long>> > pq;
result = vector<long>(vertexCount, LONG_MAX);
pq.push(make_pair(0, start));
result[start] = 0;
/*
weight dari sebuah edge diletakkan pada element pertama dari pair, sehingga priority queue akan memprioritaskan edge berdasarkan weight dari edge
*/
while(!pq.empty()){
auto temp = pq.top();
pq.pop();
if(visited[temp.second]) continue;
visited[temp.second] = true;
for(auto vertex:adjList[temp.second]){
long nextVertex = vertex.first;
long weight = vertex.second;
if(temp.first + weight < result[nextVertex]) {
result[nextVertex] = temp.first + weight;
pq.push(make_pair(result[nextVertex], nextVertex));
}
}
}
}