Weighted dan Unweighted Graph

Pada peta jalan, hubungan “Jakarta terhubung dengan Bandung” saja tidak cukup — kita juga perlu tahu berapa jaraknya. Inilah kegunaan weighted graph: setiap edge memiliki nilai numerik yang menyatakan biaya, jarak, waktu, atau kapasitas. Unweighted graph memperlakukan semua edge sama (seolah berbobot 1) sehingga algoritma seperti BFS bisa mencari shortest path dengan sekadar menghitung jumlah edge. Pada Chapter ini kita akan melihat kapan bobot diperlukan, bagaimana menyimpannya, dan implikasinya pada pilihan algoritma. Pemahaman ini menentukan apakah kita cukup memakai BFS atau harus naik ke Dijkstra / Bellman-Ford di Section berikutnya.

Definisi Weighted Graph #

Pada weighted graph, function w: E → ℝ memberikan bobot untuk setiap edge. Bobot dapat menyatakan:

Jarak fisik (km) pada peta jalan.
Waktu tempuh (menit) — berbeda dengan jarak bila ada jalan tol lebih cepat.
Biaya (rupiah) — tarif tiket pesawat, tarif tol.
Kapasitas (bandwidth, ampere) untuk graph aliran.
Probabilitas — untuk graph Markov chain (bobot antara 0 dan 1).

Pada unweighted graph, semua edge implisit berbobot 1. Sebuah path (A, B, C, D) dianggap memiliki cost 3 (jumlah edge). Path terpendek = path dengan jumlah edge minimum, yang bisa dicari BFS dalam O(V+E).

flowchart LR A -- 5 --- B B -- 2 --- C A -- 9 --- C C -- 7 --- D B -- 12 --- D

Pada weighted graph di atas, path A → B → C → D memiliki cost 5 + 2 + 7 = 14, sedangkan path A → B → D (hanya 2 edge) memiliki cost 5 + 12 = 17. Jumlah edge minimum (2) tidak sama dengan cost minimum (14). Inilah mengapa BFS tidak dapat menyelesaikan shortest path pada weighted graph — kita butuh algoritma seperti Dijkstra.

Implikasi Penyimpanan Bobot #

Pada adjacency list, kita perlu menyimpan bobot bersama vertex tujuan. Tiga pendekatan umum:

vector<vector<pair<int,int>>> — adj[u] berisi daftar (v, weight). Paling umum, paling ringkas.
vector<vector<Edge>> dengan struct Edge { int to; int w; } — lebih deskriptif, extensible untuk field tambahan.
Two parallel arrays — adj_v[u] berisi vertex, adj_w[u] berisi bobot paralel. Jarang dipakai.

Pada adjacency matrix, bobot disimpan langsung pada sel matriks: mat[u][v] = weight, dengan konvensi mat[u][v] = ∞ bila tidak ada edge.

Kode: Weighted Graph dengan `vector<pair>` #

cpp
#include <iostream>
#include <vector>
#include <queue>

class WeightedGraph {
public:
    explicit WeightedGraph(int n) : adj_(n) {}
    void add_edge(int u, int v, int w) {
        adj_[u].push_back({v, w});   // directed; untuk undirected, tambahkan {u, w} ke adj_[v]
    }
    const std::vector<std::pair<int,int>>& neighbors(int u) const { return adj_[u]; }
    int v_count() const { return adj_.size(); }
private:
    std::vector<std::vector<std::pair<int,int>>> adj_;  // (vertex, weight)
};

// BFS tidak valid untuk weighted graph; kita pakai Dijkstra sebagai contoh konsumsi bobot.
std::vector<long long> dijkstra(const WeightedGraph& g, int src) {
    const long long INF = 1e18;
    std::vector<long long> dist(g.v_count(), INF);
    // priority_queue menyimpan (jarak negatif, vertex) agar min-heap
    std::priority_queue<std::pair<long long,int>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        d = -d;                                  // balik ke positif
        if (d > dist[u]) continue;               // pasangan usang, skip
        for (auto [v, w] : g.neighbors(u)) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({-dist[v], v});          // simpan negatif untuk min-heap
            }
        }
    }
    return dist;
}

int main() {
    WeightedGraph g(4);   // A=0, B=1, C=2, D=3
    g.add_edge(0, 1, 5);
    g.add_edge(1, 2, 2);
    g.add_edge(0, 2, 9);
    g.add_edge(2, 3, 7);
    g.add_edge(1, 3, 12);

    std::cout << "Adjacency list (vertex, weight):\n";
    for (int u = 0; u < g.v_count(); ++u) {
        std::cout << "  " << (char)('A' + u) << " ->";
        for (auto [v, w] : g.neighbors(u)) {
            std::cout << " (" << (char)('A' + v) << ", w=" << w << ")";
        }
        std::cout << '\n';
    }

    auto dist = dijkstra(g, 0);
    std::cout << "\nShortest distance dari A:\n";
    for (int u = 0; u < g.v_count(); ++u) {
        std::cout << "  A -> " << (char)('A' + u) << " = " << dist[u] << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
Adjacency list (vertex, weight):
  A -> (B, w=5) (C, w=9)
  B -> (C, w=2) (D, w=12)
  C -> (D, w=7)
  D ->

Shortest distance dari A:
  A -> A = 0
  A -> B = 5
  A -> C = 7
  A -> D = 14

Baris std::vector<std::pair<int,int>> pada adj_: setiap elemen adalah pasangan (vertex, weight). Bila nanti kita butuh field lain (kapasitas, label), kita upgrade ke struct Edge.
Baris pq.push({0, src});: Dijkstra memakai priority queue berbasis std::pair<long long, int> (jarak, vertex). Karena STL priority_queue defaultnya max-heap, kita simpan jarak sebagai negatif untuk mendapat efek min-heap.
Baris if (d > dist[u]) continue;: lazy deletion — bila pasangan yang di-pop memiliki jarak lebih besar dari dist[u] yang sudah lebih kecil (dari jalur lain), skip. Tanpa ini Dijkstra tetap benar tetapi lambat.
Baris if (dist[u] + w < dist[v]): relax edge u → v bila menemukan jalur lebih pendek. Update dist[v] dan push pasangan baru ke queue.
Hasil A → C = 7: jalur A → B → C (cost 5+2=7) lebih murah dari edge langsung A → C (cost 9). Inilah yang tidak bisa ditemukan BFS — bobot tidak uniform.
Hasil A → D = 14: jalur A → B → C → D (5+2+7=14) lebih murah dari A → B → D (5+12=17).

Perbandingan Unweighted vs Weighted #

Tabel berikut merangkum perbedaan penting kedua jenis graph:

Aspek	Unweighted	Weighted
Bobot edge	Implisit 1	Numerik (`int`, `long long`, `double`)
Shortest path	BFS, O(V+E)	Dijkstra O((V+E) log V) / Bellman-Ford O(VE)
Penyimpanan adjacency list	`vector<vector<int>>`	`vector<vector<pair<int,int>>>`
Penyimpanan adjacency matrix	`bool mat[V][V]`	`int mat[V][V]` (∞ = tidak ada edge)
Konsep “cost path”	Jumlah edge	Jumlah weight
Negative edge	Tidak ada konsep	Mungkin; butuh Bellman-Ford

Konvensi Simbol “Tak Hingga” #

Pada adjacency matrix weighted graph, kita perlu menandai “tidak ada edge”. Konvensi umum:

int mat[V][V], isi INF (misal 1e9) untuk tidak ada edge. Pastikan INF cukup besar sehingga INF + w tidak overflow.
mat[u][u] = 0 untuk semua vertex (jarak ke diri sendiri).
Untuk algoritma Floyd-Warshall, gunakan long long INF = 1e18 agar penjumlahan tetap aman.

Kode: Weighted Adjacency Matrix #

cpp
#include <iostream>
#include <vector>
#include <iomanip>

int main() {
    const int V = 4;
    const long long INF = 1e18;
    // mat[u][v] = weight, atau INF bila tidak ada edge
    std::vector<std::vector<long long>> mat(V, std::vector<long long>(V, INF));

    // Jarak ke diri sendiri = 0
    for (int i = 0; i < V; ++i) mat[i][i] = 0;

    // Edge
    mat[0][1] = 5;
    mat[1][2] = 2;
    mat[0][2] = 9;
    mat[2][3] = 7;
    mat[1][3] = 12;

    std::cout << "Weighted adjacency matrix:\n";
    std::cout << "      ";
    for (int j = 0; j < V; ++j) std::cout << std::setw(4) << (char)('A' + j);
    std::cout << '\n';
    for (int i = 0; i < V; ++i) {
        std::cout << "  " << (char)('A' + i) << " ->";
        for (int j = 0; j < V; ++j) {
            if (mat[i][j] == INF) std::cout << "   .";
            else                  std::cout << std::setw(4) << mat[i][j];
        }
        std::cout << '\n';
    }

    // Edge count: jumlah sel non-INF non-diagonal
    int e_count = 0;
    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j)
            if (i != j && mat[i][j] != INF) e_count++;
    std::cout << "\nJumlah edge = " << e_count << '\n';
    return 0;
}

Output yang Dihasilkan:

text
Weighted adjacency matrix:
         A   B   C   D
  A ->   0   5   9   .
  B ->   .   0   2  12
  C ->   .   .   0   7
  D ->   .   .   .   0

Jumlah edge = 5

Baris std::vector<std::vector<long long>> mat(V, ...): matriks V×V bertipe long long agar INF = 1e18 aman. Bila memakai int, 1e18 akan overflow.
Baris mat[i][i] = 0: jarak dari vertex ke dirinya sendiri = 0. Penting untuk Floyd-Warshall.
Baris if (mat[i][j] == INF) std::cout << " .";: cetak . untuk sel tak terdefinisi agar matriks tetap mudah dibaca manusia.
Baris if (i != j && mat[i][j] != INF) e_count++;: hitung edge sebagai sel non-INF non-diagonal. Untuk directed graph, edge (A,B) dan (B,A) dihitung terpisah bila keduanya non-INF.

Bobot Negatif dan Dampaknya #

Beberapa algoritma tidak bekerja bila terdapat bobot negatif:

Dijkstra mengasumsikan bobot non-negatif. Bobot negatif menyebabkan algoritma melewatkan jalur lebih murah karena vertex yang sudah diproses tidak akan di-visit ulang.
Bellman-Ford dapat menangani bobot negatif, dan mendeteksi negative cycle (cycle yang total weight-nya negatif → dapat diulang tak hingga untuk mengurangi jarak).
Negative cycle membuat shortest path tidak terdefinisi (-∞).

Contoh domain dengan bobot negatif:

Arbitrage currency: nilai tukar mata uang, log-rate negatif = untung.
Game state: langkah yang memberi poin (negatif = biaya energi).
Network flow residual: bobot negatif pada residual edge untuk algoritma augmenting path.

Ringkasan #

Unweighted graph memperlakukan semua edge sama; BFS mencari shortest path dalam O(V+E).
Weighted graph memberi nilai numerik pada edge; shortest path memerlukan Dijkstra atau Bellman-Ford.
Penyimpanan bobot pada adjacency list: vector<vector<pair<int,int>>> (vertex, weight) adalah konvensi standar.
Pada adjacency matrix, bobot disimpan pada sel; gunakan INF untuk menandai ketiadaan edge dengan tipe long long agar aman dari overflow.
Dijkstra valid untuk bobot non-negatif; Bellman-Ford untuk bobot negatif dan mendeteksi negative cycle.
Pilihan weighted/unweighted menentukan algoritma — salah memilih menyebabkan jawaban salah atau kompleksitas berlebihan.