Aplikasi Pemilihan Rute Tercepat Menggunakan Algoritma Dijkstra

Posted on by Anisa Rahma Nasution
0

Aplikasi Pemilihan Rute Tercepat Dengan Algoritma Dijkstra

Aplikasi ini bertujuan mencari rute tercepat atau jalur terpendek dari satu titik ke titik lain dalam sebuah peta atau graf. Algoritma yang umum dipakai untuk masalah ini adalah Algoritma Dijkstra, karena efisien dan akurat untuk graf berbobot positif. Algoritma Dijkstra adalah algoritma greedy yang menghitung jarak minimum dari titik awal ke titik-titik lain dalam graf dengan bobot edge tidak negatif.

Hasil akhirnya adalah:

  • Jarak terpendek ke setiap node

  • Jalur terpendek (jika kita menyimpan parent / predecessor)

Syarat dan Ketentuan

Algoritma Dijkstra dapat dipakai jika:

  1. Graf berarah atau tak berarah

  2. Setiap edge memiliki bobot

  3. Bobot edge harus ≥ 0 (tidak negatif)
    → Jika ada bobot negatif, gunakan Bellman-Ford.

Konsep Dasar

Ide utama algoritma Dijkstra:

  1. Mulai dari simpul awal, beri jarak 0.

  2. Semua simpul lain diberi jarak awal ∞.

  3. Pilih node dengan jarak terkecil yang belum dikunjungi.

  4. Perbarui jarak tetangganya jika melalui node ini menjadi lebih pendek.

  5. Tandai node tersebut sebagai “selesai”.

  6. Ulangi sampai semua node selesai atau tujuan ditemukan.

Kelebihan

✔ Cepat untuk graf besar dengan bobot non-negatif
✔ Sangat efisien menggunakan priority queue
✔ Mudah diimplementasikan
✔ Banyak dipakai di sistem nyata (GPS, routing jaringan)

Kekurangan

✘ Tidak dapat dipakai jika ada bobot negatif
✘ Hanya untuk satu sumber (single-source shortest path)

Cara Kerja Dijkstra Secara Ringkas

  1. Pilih node awal (start).

  2. Set jarak awal = 0, dan lainnya = ∞.

  3. Tandai node awal sebagai “dikunjungi”.

  4. Perbarui jarak ke tetangga-tetangganya.

  5. Pilih node dengan jarak terkecil yang belum dikunjungi.

  6. Ulangi hingga semua node selesai.

Contoh Kasus

Misal kita punya graf seperti ini:

A –5– B –2– D
| |
2 4
| |
C –7– E

Jika kita ingin mencari jalur tercepat dari A ke D, Dijkstra akan menghasilkan:

👉 A → B → D dengan total jarak: 5 + 2 = 7

Contoh Implementasi Sederhana (Python)

Jika Anda butuh kode untuk aplikasi, berikut contoh dasar:

import heapq

def dijkstra(graf, start):
jarak = {node: float(‘inf’) for node in graf}
jarak[start] = 0
priority_queue = [(0, start)]

while priority_queue:
current_dist, current_node = heapq.heappop(priority_queue)

if current_dist > jarak[current_node]:
continue

for neighbor, weight in graf[current_node]:
distance = current_dist + weight
if distance < jarak[neighbor]:
jarak[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))

return jarak

graf = {
‘A’: [(‘B’, 5), (‘C’, 2)],
‘B’: [(‘A’, 5), (‘D’, 2), (‘E’, 4)],
‘C’: [(‘A’, 2), (‘E’, 7)],
‘D’: [(‘B’, 2)],
‘E’: [(‘B’, 4), (‘C’, 7)]
}

hasil = dijkstra(graf, ‘A’)
print(“Jarak terpendek dari A:”, hasil)

Contoh aplikasi dengan tampilan UI?

import { useState } from “react”;
import { Card, CardContent } from “@/components/ui/card”;
import { Button } from “@/components/ui/button”;
import { motion } from “framer-motion”;

export default function App() {
const graph = {
A: { B: 5, C: 2 },
B: { A: 5, D: 2, E: 4 },
C: { A: 2, E: 7 },
D: { B: 2 },
E: { B: 4, C: 7 },
};

const [start, setStart] = useState(“A”);
const [end, setEnd] = useState(“D”);
const [result, setResult] = useState(null);

const dijkstra = (graph, start, end) => {
const distances = {};
const visited = {};
const previous = {};

Object.keys(graph).forEach((node) => {
distances[node] = Infinity;
previous[node] = null;
});
distances[start] = 0;

while (true) {
let closest = null;
Object.keys(distances).forEach((node) => {
if (!visited[node] && (closest === null || distances[node] < distances[closest])) {
closest = node;
}
});

if (closest === null) break;
if (closest === end) break;

visited[closest] = true;
const neighbors = graph[closest];

Object.keys(neighbors).forEach((neighbor) => {
const newDist = distances[closest] + neighbors[neighbor];
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
previous[neighbor] = closest;
}
});
}

const path = [];
let current = end;
while (current) {
path.unshift(current);
current = previous[current];
}

return { distance: distances[end], path };
};

const handleCalculate = () => {
setResult(dijkstra(graph, start, end));
};

return (
<div className=”p-6 grid place-items-center min-h-screen bg-gray-100″>
<motion.div initial={{ opacity: 0, y: 20 }} animate={{ opacity: 1, y: 0 }}>
<Card className=”p-6 rounded-2xl shadow-xl max-w-lg w-full”>
<h1 className=”text-2xl font-bold mb-4 text-center”>Aplikasi Rute Tercepat (Dijkstra)</h1>

<CardContent className=”space-y-4″>
<div>
<label className=”block mb-1 font-medium”>Titik Awal</label>
<select value={start} onChange={(e) => setStart(e.target.value)} className=”w-full p-2 rounded-xl border”>
{Object.keys(graph).map((node) => (
<option key={node}>{node}</option>
))}
</select>
</div>

<div>
<label className=”block mb-1 font-medium”>Titik Tujuan</label>
<select value={end} onChange={(e) => setEnd(e.target.value)} className=”w-full p-2 rounded-xl border”>
{Object.keys(graph).map((node) => (
<option key={node}>{node}</option>
))}
</select>
</div>

<Button onClick={handleCalculate} className=”w-full rounded-2xl p-3″>Hitung Rute Tercepat</Button>

{result && (
<motion.div initial={{ opacity: 0 }} animate={{ opacity: 1 }} className=”mt-4 p-4 bg-white rounded-xl shadow”>
<h2 className=”text-lg font-semibold mb-2″>Hasil</h2>
<p><strong>Jarak Terpendek:</strong> {result.distance}</p>
<p><strong>Rute:</strong> {result.path.join(” → “)}</p>
</motion.div>
)}
</CardContent>
</Card>
</motion.div>
</div>
);
}

Berikut contoh aplikasi dengan UI dalam bentuk komponen React di canvas. Kode tersebut sudah lengkap dengan:

✅ Input titik awal & tujuan
✅ Perhitungan Dijkstra
✅ Tampilan hasil (jalur & jarak)
✅ Desain modern (Tailwind + shadcn + animasi Framer Motion)

Algoritma Dijkstra merupakan salah satu algoritma terpenting dalam komputasi modern, terutama dalam penyelesaian masalah jalur terpendek. Dengan sifatnya yang efisien dan mudah diimplementasikan, Dijkstra menjadi fondasi bagi berbagai aplikasi dunia nyata seperti navigasi, jaringan komputer, hingga kecerdasan buatan.

Meskipun memiliki keterbatasan pada graf berbobot negatif, algoritma ini tetap menjadi pilihan utama dalam banyak kasus praktis karena kecepatan dan keakuratannya. Pemahaman konsep, langkah kerja, serta implementasinya sangat penting bagi siapa saja yang ingin mendalami graf dan algoritma pencarian jalur.

Semoga penjelasan ini dapat membantu memperluas pemahaman Anda mengenai Algoritma Dijkstra dan manfaatnya dalam bidang ilmu komputer. Apabila diperlukan, Anda dapat melanjutkan dengan mempelajari algoritma terkait seperti A*, Bellman-Ford, atau Floyd-Warshall untuk memahami berbagai pendekatan penentuan jarak dalam graf.

Post Views: 336