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:

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.

1. 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.

2. 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.

3. Pop vertex dengan distance yang paling minimum dari priority queue

4. 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.

5. Apabila hasil dari pop vertex tersebut telah di visit sebelumnya, maka lakukan continue.

6. 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));
            }
        }
    }
}

Lanjut ke Minimum Spanning Tree >