Analisis Jalur Terpendek Antar Kota Menggunakan Algoritma Dijkstra dan Weighted Adjacency Matrix

Identitas Mahasiswa

• Nama Lengkap: Muhammad Fauzan Taris
• NPM: 011250037
• Program Studi: S1 Informatika
• Mata Kuliah: Aljabar Linier
• Dosen: Rendy Almaheri Adhi Pratama (Rendy Almaheri)
• Institut Teknologi dan Bisnis PalComTech

Pendahuluan

Dalam cabang ilmu matematika diskret dan struktur data, masalah pencarian jalur terpendek (shortest path problem) merupakan salah satu persoalan optimasi klasik yang paling sering ditemui. Untuk menyelesaikan masalah ini, representasi matematis dari jaringan dunia nyata dimodelkan menggunakan Teori Graf.

Berikut adalah beberapa konsep dasar penunjang dalam pemodelan graf:

• Vertex (Node): Titik objek dalam graf yang merepresentasikan entitas tertentu. Dalam studi kasus ini, vertex merepresentasikan kota.
• Edge (Sisi): Garis penghubung antar dua vertex yang menggambarkan adanya hubungan atau rute langsung.
• Weighted Graph (Graf Berbobot): Sebuah graf di mana setiap edge memiliki nilai atau bobot tertentu, seperti jarak (km), biaya, atau waktu tempuh.
• Weighted Adjacency Matrix (Matriks Ketenaran Berbobot): Matriks persegi berukuran N×N (di mana N adalah jumlah vertex) yang merepresentasikan bobot antar-titik. Jika titik i dan j terhubung langsung, elemen matriks A[i][j] berisi nilai bobotnya. Jika tidak terhubung, nilainya diisi dengan tak hingga (∞), sedangkan diagonal utamanya bernilai 0.
• Algoritma Dijkstra: Algoritma berbasis greedy yang digunakan untuk menentukan jalur terpendek dari satu titik sumber (single-source shortest path) ke titik-titik lainnya pada graf yang memiliki bobot non-negatif.

Studi Kasus

Berdasarkan hasil undian sistem otomatis yang diperoleh, didapatkan data kota sebagai berikut:

1. Kota 1 (Asal): New York (No. Indeks: 6)
2. Kota 2: Bangkok (No. Indeks: 37)
3. Kota 3 (Tujuan): Cairo (No. Indeks: 25)

Hasil Undian

Map Kosong

Tujuan utama dari studi kasus ini adalah mencari rute dengan akumulasi bobot jarak minimum dari New York menuju Cairo melewati interkoneksi graf global.

Pembentukan Weighted Adjacency Matrix

Dengan total 48 kota dan 87 rute interkoneksi tak berarah (undirected graph), struktur matriks ketenaran berbobot dibentuk dalam dimensi 48×48.

Prinsip pengisian elemen matriks M[i][j] dirumuskan sebagai berikut:

Berikut adalah cuplikan (snippet) representasi baris dan kolom untuk beberapa kota terkait dalam bentuk tabel:

Perhitungan Algoritma Dijkstra

Pencarian rute terpendek dihitung secara manual/runtut dari titik asal New York. Nilai inisialisasi awal seluruh kota selain New York diatur ke ∞.

1. Inisialisasi Node awal

• Jarak minimum saat ini: D[New York]=0
• Kota belum dikunjungi: Semua 48 kota.
• Predecessor awal: Semua None.

2. Langkah Iterasi & Relaksasi Jarak

• Iterasi 1 (Evaluasi New York, Jarak = 0):
• Tetangga terhubung langsung: Washington (4.8), Madrid (12.74), London (13.98), Montréal (5.76)
• Update Jarak: D[Washington]=4.8, D[Montreˊal]=5.76, D[Madrid]=12.74, D[London]=13.98.
• Predecessor: {'Washington': 'New York', 'Montréal': 'New York', 'Madrid': 'New York', 'London': 'New York'}
• Iterasi 2 (Pilih Jarak Terkecil: Washington, Jarak = 4.8):
• Tetangga terhubung: Montréal (6.07), New York (4.8), Miami (7.06), Atlanta (7.9).
• Relaksasi: D[Miami]=4.8+7.06=11.86, D[Atlanta]=4.8+7.9=12.7.
• Iterasi 3 (Pilih Jarak Terkecil: Montréal, Jarak = 5.76):
• Evaluasi rute melalui Montréal ke Chicago (7.54).
• Relaksasi: D[Chicago]=5.76+7.54=13.3.
• Iterasi 4 (Pilih Jarak Terkecil: Miami, Jarak = 11.86):
• Evaluasi rute Bogotá (6.96), Mexico City (8.53).
• Relaksasi: D[Bogotaˊ]=11.86+6.96=18.82.
• Iterasi 5 (Pilih Jarak Terkecil: Atlanta, Jarak = 12.7):
• Tidak menghasilkan rute yang lebih pendek dari yang sudah ada.
• Iterasi 6 (Pilih Jarak Terkecil: Madrid, Jarak = 12.74):
• Tetangga terhubung: Paris (7.34), Algiers (8.98).
• Relaksasi: D[Algiers]=12.74+8.98=21.72.
• Predecessor: {'Algiers': 'Madrid'}
• Iterasi 7 sampai 12: Evaluasi berturut-turut untuk Chicago, London, Bogotá, Paris, Mexico City, Essen (tidak memengaruhi jalur optimal ke Cairo).
• Iterasi 13 (Pilih Jarak Terkecil: Algiers, Jarak = 21.72):
• Tetangga terhubung: Istanbul (7.77), Cairo (5.66).
• Relaksasi ke target: D[Cairo]=21.72+5.66=27.38.
• Predecessor: {'Cairo': 'Algiers'}
• Iterasi Akhir: Node Cairo dievaluasi dengan nilai jarak absolut 27.38. Proses dihentikan karena target minimum telah dikunci.

3. Rekonstruksi Jalur Akhir (Backtracking)

Melalui pelacakan predecessor mundur dari target ke asal:

1. Cairo ← didapat dari Algiers
2. Algiers ← didapat dari Madrid
3. Madrid ← didapat dari New York

Maka, urutan kota yang dilalui adalah: New York → Madrid → Algiers → Cairo dengan total bobot jarak 27.38.

Implementasi Program

Berikut adalah implementasi kode program menggunakan bahasa pemrograman Python untuk membaca data graf, mengeksekusi Algoritma Dijkstra, dan menyajikan hasil secara otomatis.

Python

import heapq
# 1. Definisi Data Master Kota (48 Kota)
cities = {
    1: "San Francisco", 2: "Los Angeles", 3: "Mexico City", 4: "Chicago", 5: "Montréal",
    6: "New York", 7: "Atlanta", 8: "Washington", 9: "Miami", 10: "Bogotá",
    11: "Lima", 12: "Santiago", 13: "São Paulo", 14: "Buenos Aires", 15: "London",
    16: "Madrid", 17: "Paris", 18: "Essen", 19: "Milan", 20: "St. Petersburg",
    21: "Algiers", 22: "Lagos", 23: "Kinshasa", 24: "Johannesburg", 25: "Cairo",
    26: "Khartoum", 27: "Istanbul", 28: "Moscow", 29: "Baghdad", 30: "Tehran",
    31: "Riyadh", 32: "Karachi", 33: "Mumbai", 34: "Chennai", 35: "Delhi",
    36: "Kolkata", 37: "Bangkok", 38: "Ho Chi Minh City", 39: "Jakarta", 40: "Manila",
    41: "Hong Kong", 42: "Shanghai", 43: "Beijing", 44: "Seoul", 45: "Taipei",
    46: "Tokyo", 47: "Osaka", 48: "Sydney"
}
# 2. Definisi Hubungan Rute dan Jarak (87 Sisi Berbobot)
routes_data = [
    ("San Francisco", "Chicago", 9.9), ("San Francisco", "Los Angeles", 7.48),
    ("Los Angeles", "Mexico City", 7.55), ("Los Angeles", "Chicago", 12.87),
    ("Chicago", "Mexico City", 12.16), ("Chicago", "Atlanta", 5.81),
    ("Mexico City", "Miami", 8.53), ("Atlanta", "Miami", 7.65),
    ("Chicago", "Montréal", 7.54), ("Atlanta", "Washington", 7.9),
    ("Montréal", "New York", 5.76), ("Montréal", "Washington", 6.07),
    ("Washington", "New York", 4.8), ("Miami", "Washington", 7.06),
    ("Mexico City", "Lima", 14.9), ("Mexico City", "Bogotá", 9.7),
    ("Miami", "Bogotá", 6.96), ("Lima", "Bogotá", 8.48),
    ("Lima", "Santiago", 7.85), ("Bogotá", "Buenos Aires", 15.59),
    ("Bogotá", "São Paulo", 13.88), ("Buenos Aires", "São Paulo", 6.98),
    ("São Paulo", "Lagos", 17.24), ("São Paulo", "Madrid", 24.75),
    ("Lagos", "Kinshasa", 6.93), ("Kinshasa", "Johannesburg", 8.19),
    ("Johannesburg", "Khartoum", 13.34), ("Kinshasa", "Khartoum", 7.53),
    ("Lagos", "Khartoum", 9.37), ("New York", "Madrid", 12.74),
    ("New York", "London", 13.98), ("Madrid", "London", 7.25),
    ("Madrid", "Paris", 7.34), ("Madrid", "Algiers", 8.98),
    ("London", "Paris", 6.61), ("Paris", "Essen", 5.08),
    ("London", "Essen", 7.4), ("Paris", "Algiers", 7.39),
    ("Paris", "Milan", 5.25), ("Essen", "Milan", 4.66),
    ("Essen", "St. Petersburg", 8.19), ("Milan", "Istanbul", 5.09),
    ("Algiers", "Istanbul", 7.77), ("Algiers", "Cairo", 5.66),
    ("Cairo", "Istanbul", 6.24), ("St. Petersburg", "Istanbul", 8.88),
    ("St. Petersburg", "Moscow", 6.25), ("Istanbul", "Moscow", 6.96),
    ("Cairo", "Baghdad", 6.89), ("Istanbul", "Baghdad", 6.54),
    ("Baghdad", "Tehran", 6.74), ("Moscow", "Tehran", 5.99),
    ("Cairo", "Khartoum", 7.02), ("Cairo", "Riyadh", 8.11),
    ("Baghdad", "Riyadh", 6.62), ("Riyadh", "Karachi", 7.55),
    ("Baghdad", "Karachi", 7.31), ("Tehran", "Karachi", 6.72),
    ("Tehran", "Delhi", 8.33), ("Karachi", "Delhi", 5.51),
    ("Delhi", "Mumbai", 8.51), ("Mumbai", "Karachi", 5.72),
    ("Mumbai", "Chennai", 6.35), ("Delhi", "Chennai", 10.9),
    ("Chennai", "Kolkata", 10.16), ("Delhi", "Kolkata", 5.58),
    ("Kolkata", "Bangkok", 6.01), ("Chennai", "Bangkok", 6.32),
    ("Chennai", "Jakarta", 8.32), ("Jakarta", "Bangkok", 9.74),
    ("Kolkata", "Hong Kong", 6.07), ("Hong Kong", "Bangkok", 5.29),
    ("Bangkok", "Ho Chi Minh City", 6.85), ("Ho Chi Minh City", "Hong Kong", 8.3),
    ("Jakarta", "Ho Chi Minh City", 6.45), ("Jakarta", "Sydney", 18.93),
    ("Manila", "Sydney", 15.53), ("Ho Chi Minh City", "Manila", 7.36),
    ("Hong Kong", "Manila", 10.99), ("Manila", "Taipei", 8.95),
    ("Hong Kong", "Taipei", 6.1), ("Taipei", "Osaka", 5.87),
    ("Osaka", "Tokyo", 5.42), ("Taipei", "Shanghai", 8.45),
    ("Shanghai", "Hong Kong", 5.89), ("Shanghai", "Tokyo", 11.81),
    ("Tokyo", "Seoul", 6.02), ("Seoul", "Shanghai", 8.31),
    ("Beijing", "Shanghai", 5.09), ("Beijing", "Seoul", 6.67)
]
# 3. Transformasi ke Adjacency List (Graf Tak Berarah)
graph = {city: {} for city in cities.values()}
for u, v, w in routes_data:
    graph[u][v] = w
    graph[v][u] = w
# 4. Fungsi Algoritma Dijkstra
def dijkstra(graph, start_node, end_node):
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0
    predecessors = {node: None for node in graph}

    # Priority Queue untuk optimasi pemilihan node berjarak minimum
    pq = [(0, start_node)]

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue

        if current_node == end_node:
            break

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_node
                heapq.heappush(pq, (distance, neighbor))

    # Rekonstruksi rute
    path = []
    curr = end_node
    while curr is not None:
        path.append(curr)
        curr = predecessors[curr]
    path.reverse()

    return path, distances[end_node]
# 5. Eksekusi Program Utama
start_city = "New York"
end_city = "Cairo"
shortest_path, total_weight = dijkstra(graph, start_city, end_city)
# 6. Menampilkan Hasil Output
print("=" * 50)
print("HASIL ANALISIS JALUR TERPENDEK ALGORITMA DIJKSTRA")
print("=" * 50)
print(f"Kota Asal     : {start_city}")
print(f"Kota Tujuan   : {end_city}")
print(f"Total Bobot   : {total_weight:.2f}")
print("Urutan Rute   : ", " -> ".join(shortest_path))
print("=" * 50)

Penjelasan Program Python

Output eksekusi program Python.

• Struktur Data: Menggunakan dictionary of dictionaries (graph) untuk memetakan nama kota asal ke daftar tetangga beserta bobot jaraknya. Ini memberikan efisiensi pencarian waktu nyata yang optimal.
• Priority Queue (heapq): Memanfaatkan modul bawaan Python untuk menyimpan urutan pencarian berdasarkan jarak terkecil secara konstan sehingga kompleksitas waktu algoritma terjaga pada batas O((V+E)logV).
• Mekanisme Relaksasi: Secara dinamis mengevaluasi jika kombinasi jalur baru menawarkan nilai bobot akumulatif yang lebih hemat dibanding penyimpanan data sebelumnya.

Kesimpulan

Berdasarkan hasil analisis berbasis perhitungan manual terstruktur dan validasi komputasi Python, rute terbaik dari New York menuju Cairo dicapai dengan transit melalui kota Madrid dan Algiers dengan efisiensi total bobot jarak sebesar 27.38.

Pemanfaatan matriks ketenaran berbobot (weighted adjacency matrix) terbukti mempermudah struktur penyimpanan data graf berskala besar, yang kemudian diproses secara efektif oleh Algoritma Dijkstra untuk menghasilkan jalur bebas redundansi.