Modul 5 [Shortest Path] - lab-kcks/Modul-STRUKDAT GitHub Wiki

Shortest Path

Penjelasan

Pada permasalahan graph, Shortest Path Problem merupakan pencarian path dari 2 vertex pada suatu graph yang mempunyai penjumlahan weight yang paling minimum. Permasalahan ini dapat diselesaikan dengan mudah menggunakan BFS apabila semua edge mempunyai weight 1. Namun, pada permasalahan kali ini, weight dapat bernilai berapapun. Terdapat banyak sekali implementasi untuk penyelesaian Shortest Path Problem, tapi yang akan kita bahas saat ini adalah Dijkstra’s Algorithm.

Shortest Path adalah algoritma yang menemukan jalur minimum dari satu node ke node lainnya. Terdapat beberapa algoritma untuk mencari shortest path. Namun pada kali ini, kita akan membahas algoritma Dijkstra atau Dijkstra's Algorithm.

Misalkan kita diminta untuk mencari jalur tercepat dari sebuah graph. Jalur tersebut dari node satu ke ujungnya (misal). Mengapa menggunakan Shortest Path? Mengapa tidak menggunakan bfs untuk menyelesaikan masalah ini?

Semisal semua edge memiliki weight yang sama (misal 1), atau bentuk graphnya itu unweighted, maka masalah tersebut dapat diselesaikan menggunakan bfs. Namun jika weight dari tiap edge bervariasi, maka bfs tidak dapat digunakan. Oleh karena itu diperlukan algoritma shortest path untuk menangani masalah ini.

Dijkstra's Algorithm

Langkah algoritma :

  • Buat sebuah sptSet (shortest path tree set)
  • Tetapkan nilai jarak ke semua node dalam graph. Inisialisasi semua nilai sebagai INFINITE. Ubah nilai jarak untuk node awal menjadi 0
  • Ketika sptSet belum menyertakan semua node :
    • Ambil node (misal, u) yang belum disertakan kedalam sptSet dan memiliki nilai jarak yang minimum
    • Masukkan node u kedalam sptSet
    • Ubah jarak dari semua node terdekat. Untuk mengubah nilai jarak, iterasi semua node:
      (Untuk setiap node (misal v), jika jumlah dari nilai jarak dari sumber ke node u ditambah dengan weight dari edge node u dan v, jika kurang dari nilai jarak sumber ke node v, update nilai jarak v)

Berikut adalah ilustrasi dijkstra

Sumber gambar: researchgate.com

Ket : INF adalah infinite (tak hingga)

Implementasi SPT Dijkstra's Algorithm

fungsi minDistance

int minDistance(int dist[], bool sptSet[])
{
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;

    // return node yang belum dimasukkan ke SPT dan bernilai minimum
    return min_index;
}

fungsi utama

void dijkstra(int graph[V][V], int src)
{
    // array output, dist[i] akan mengandung
    // jarak dari src ke i
    int dist[V];

    // akan true jika node sudah masuk ke SPT atau jarak
    // minimum dari src ke i sudah final
    bool sptSet[V];

    // inisialisasi
    for (int i = 0; i < V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;

    // jarak dari node src ke src itu sendiri adalah 0
    dist[src] = 0;

    // shortest path utk tiap node
    for (int count = 0; count < V - 1; count++)
    {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        // ubah value jarak berdasarkan node u 
        for (int v = 0; v < V; v++)
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }

    printSolution(dist);
}

Referensi

⚠️ **GitHub.com Fallback** ⚠️