Dijkstra Visualizer

Implementasi interaktif algoritma pencarian jalur terpendek (Shortest Path) menggunakan React Flow untuk manipulasi graf dinamis.

Tech Stack

• Next.js 14
• TypeScript
• React Flow
• Tailwind CSS
• Shadcn UI

1. Konsep Utama

Algoritma Dijkstra adalah algoritma greedy yang digunakan untuk memecahkan masalah jalur terpendek dari satu sumber (single-source shortest path) pada graf dengan bobot sisi non-negatif.

Dalam visualizer ini, tantangan utamanya bukan hanya menjalankan algoritma, tetapi memvisualisasikan setiap langkahnya (state snapshotting) sehingga pengguna bisa melihat bagaimana algoritma "berpikir" node demi node.

2. Implementasi Teknis

A. Manajemen Graf dengan React Flow

Saya menggunakan library reactflow untuk menangani rendering node dan edge. State dikelola menggunakan hooks useNodesState dan useEdgesState.

const [nodes, setNodes, onNodesChange] = useNodesState(initialNodes);
const [edges, setEdges, onEdgesChange] = useEdgesState(initialEdges);

// Menambah node baru secara dinamis
const addNode = useCallback(() => {
  const newNode = {
    id: Date.now().toString(),
    position: { x: Math.random() * 500, y: Math.random() * 400 },
    data: { label: `Node ${nodes.length + 1}` },
  };
  setNodes((nds) => [...nds, newNode]);
}, [nodes]);

B. Algoritma Dijkstra dengan Snapshotting

Alih-alih hanya mengembalikan hasil akhir, fungsi dijkstra dimodifikasi untuk merekam history langkah (steps). Setiap kali algoritma mengunjungi node atau memperbarui jarak, state tersebut disimpan dalam array steps.

• Initialization: Set jarak awal ke Infinity, jarak sumber ke 0.
• Priority Queue: Memilih node dengan jarak terpendek yang belum dikunjungi.
• Relaxation: Jika ditemukan jalur yang lebih pendek ke tetangga, update jarak dan simpan "parent" node untuk rekonstruksi jalur.
• Snapshot: Simpan state (current node, visited set, distances) ke array steps.

C. Playback Control

Fitur "Step-by-step" diimplementasikan dengan state currentStepIndex. useEffect mendengarkan perubahan indeks ini dan memperbarui warna node di React Flow sesuai state pada langkah tersebut (misal: oranye untuk node yang sedang diproses, biru untuk visited).

3. Tantangan & Solusi

Tantangan: Sinkronisasi antara state logis algoritma dan state visual React Flow.

Solusi: Memisahkan data graf (logical) dan data visual (UI). Saat algoritma berjalan, ia tidak memutasi state UI secara langsung, tetapi menghasilkan "resep" perubahan yang kemudian diaplikasikan oleh React component melalui setInterval untuk animasi.