Implementasi Algoritma Matriks untuk Mencari Rute Terpendek Antar Kota

Nama Lengkap: Leonardo Vistara NPM: 011250020 Program Studi: S1 Informatika Mata Kuliah: Aljabar Linier Dosen: Rendy Almaheri Adhi Pratama [Rendy Almaheri] Institut Teknologi dan Bisni Palcomtech [https://palcomtech.ac.id/]

Pendahuluan

Dalam dunia komputasi, pencarian rute terpendek merupakan salah satu permasalahan klasik dalam teori graf (graph theory). Permasalahan ini sering digunakan dalam berbagai bidang seperti navigasi, logistik, hingga jaringan komputer. Salah satu pendekatan yang dapat digunakan untuk menyelesaikan masalah ini adalah dengan menggunakan representasi matriks dan algoritma berbasis matriks.

Pada tugas ini, dilakukan perubahan pendekatan dari teori graf klasik menjadi pendekatan berbasis matriks dengan menggunakan bahasa pemrograman Python. Tujuan utama dari implementasi ini adalah untuk menghitung rute terpendek antar kota, khususnya untuk jalur Cairo → Hong Kong → Mexico City, serta menampilkan detail jarak yang ditempuh dan total keseluruhan jarak perjalanan.

Konsep Dasar

Secara konsep, setiap kota direpresentasikan sebagai node dan hubungan antar kota direpresentasikan sebagai edge dengan bobot berupa jarak. Data ini kemudian diubah ke dalam bentuk matriks jarak (distance matrix), di mana setiap elemen matriks menyatakan jarak langsung antar dua kota.

Untuk menghitung rute terpendek dari semua pasangan kota, digunakan algoritma Floyd-Warshall Algorithm. Algoritma ini bekerja dengan cara membandingkan semua kemungkinan jalur melalui node perantara dan memperbarui jarak minimum secara bertahap hingga diperoleh jarak terpendek global.

Pendekatan ini sangat cocok digunakan karena mampu menghitung semua pasangan rute terpendek dalam satu kali proses komputasi.

Struktur Data & Representasi

Dalam implementasi ini, digunakan beberapa struktur data utama, yaitu daftar kota, data jarak antar kota, serta matriks jarak.

Daftar kota disimpan dalam bentuk array, yang kemudian di-mapping ke indeks numerik agar dapat digunakan dalam matriks. Selanjutnya, matriks jarak diinisialisasi dengan nilai tak hingga (infinity) untuk menunjukkan bahwa belum ada jalur yang diketahui, kecuali untuk jarak kota ke dirinya sendiri yang bernilai nol.

Data koneksi antar kota dimasukkan dalam bentuk pasangan kota beserta bobot jaraknya, lalu diisikan ke dalam matriks secara simetris karena graf yang digunakan bersifat tidak berarah (undirected graph).

Implementasi Algoritma

Algoritma utama yang digunakan adalah Floyd-Warshall, yang bekerja dengan tiga perulangan bersarang untuk mengevaluasi setiap kemungkinan jalur melalui node perantara.

Pada setiap iterasi, algoritma akan memeriksa apakah jalur dari kota A ke kota C melalui kota B lebih pendek dibandingkan jalur langsung. Jika lebih pendek, maka nilai matriks akan diperbarui, dan jalur akan disimpan untuk keperluan rekonstruksi rute.

Dengan pendekatan ini, sistem tidak hanya mampu mengetahui jarak terpendek, tetapi juga jalur yang harus ditempuh.

Algoritma Floyd Warshall pada Python

Implementasi Sistem Navigasi

Setelah proses perhitungan selesai, dibuat sebuah sistem sederhana berbasis terminal untuk menerima input kota dari pengguna. Sistem ini memungkinkan pengguna untuk memasukkan beberapa kota sekaligus, lalu menghitung rute terpendek antar setiap pasangan kota secara berurutan.

Selain itu, sistem juga menampilkan rincian perjalanan, termasuk:

• Jalur yang dilewati
• Jarak antar kota
• Proses penjumlahan jarak
• Total jarak keseluruhan

Hal ini membuat hasil perhitungan menjadi transparan dan mudah diverifikasi.

Contoh Input yang Diberikan

Output yang Dihasilkan (1)

Output yang Dihasilkan (2)

Penjelasan Code Secara Bertahap

Pada bagian ini, dilakukan penjelasan terhadap kode program yang telah dibuat secara bertahap agar dapat dipahami bagaimana sistem bekerja dari awal hingga menghasilkan output.

• Import Library

Program menggunakan library NumPy untuk mempermudah pengolahan data berbasis matriks.

NumPy digunakan karena memiliki efisiensi tinggi dalam operasi array multidimensi, khususnya untuk inisialisasi matriks jarak dan operasi numerik lainnya.

Import Library numpy

• Daftar Kota

Pada bagian ini, dibuat sebuah list yang berisi seluruh kota yang digunakan dalam sistem.

Setiap kota nantinya akan dipetakan ke dalam indeks numerik agar dapat direpresentasikan dalam bentuk matriks. Pendekatan ini penting karena matriks hanya dapat diakses menggunakan indeks angka, bukan string.

Bagian DAFTAR_KOTA

• Data Jarak Antar Kota

Data jarak disimpan dalam bentuk tuple yang berisi kota asal, kota tujuan, bobot jarak. Struktur ini memudahkan dalam proses iterasi untuk mengisi matriks jarak. Data ini juga bersifat dua arah (undirected), sehingga jarak dari kota A ke B sama dengan B ke A.

Bagian DATA_JARAK (1)

Bagian DATA_JARAK (2)

Bagian DATA_JARAK (3)

• Mapping Kota ke Indeks

Pada bagian ini, digunakan struktur dictionary untuk memetakan nama kota ke indeks numerik.

Hal ini dilakukan dengan tujuan agar pencarian indeks kota menjadi lebih cepat dan efisien. Selain itu, dibuat juga mapping kebalikannya untuk mengubah indeks kembali menjadi nama kota saat menampilkan hasil.

Bagian city_to_idx dan idx_to_city

• Inisialisasi Matriks Jarak

Matriks jarak dibuat menggunakan NumPy dengan ukuran sebanyak jumlah kota yang tersedia.

Semua nilai awal diisi dengan tak hingga (infinity) untuk menandakan bahwa belum ada jalur yang diketahui. Kemudian, nilai diagonal diisi dengan nol karena jarak dari suatu kota ke dirinya sendiri adalah nol.

Selain itu, dibuat juga matriks next_node untuk menyimpan informasi jalur yang akan digunakan dalam proses rekonstruksi rute.

Inisialisasi dist_matrix dan next_node

• Pengisian Matriks Berdasarkan Data

Pada tahap ini, data koneksi antar kota dimasukkan ke dalam matriks jarak.

Setiap pasangan kota diambil dari DATA_JARAK, kemudian nilai jaraknya dimasukkan ke dalam matriks pada posisi yang sesuai. Karena graf bersifat tidak berarah, maka nilai dimasukkan ke dua arah sekaligus.

Loop Pengisian Matriks

• Implementasi Algoritma Floyd-Warshall

Bagian ini merupakan inti dari program, yaitu proses pencarian rute terpendek menggunakan algoritma Floyd-Warshall Algorithm.

Algoritma bekerja dengan tiga perulangan bersarang yang mengevaluasi setiap kemungkinan jalur melalui node perantara. Jika ditemukan jalur yang lebih pendek, maka nilai matriks akan diperbarui.

Selain itu, matriks next_node juga diperbarui untuk menyimpan jalur yang optimal.

Triple Loop Floyd-Warshall

• Fungsi Validasi Input Kota

Fungsi get_valid_city() digunakan untuk memastikan bahwa input yang diberikan oleh pengguna sesuai dengan daftar kota yang tersedia.

Jika pengguna memasukkan nama kota yang tidak valid, maka sistem akan meminta input ulang hingga mendapatkan kota yang benar.

Fungsi get_valid_city

• Rekonstruksi Jalur Terpendek

Setelah algoritma selesai dijalankan, jalur terpendek tidak langsung tersedia dalam bentuk list kota. Oleh karena itu, digunakan proses rekonstruksi jalur dengan bantuan matriks next_node.

Proses ini dilakukan dengan menelusuri node berikutnya dari kota asal hingga mencapai kota tujuan.

Bagian Rekonstruksi Path

• Perhitungan dan Output

Pada bagian akhir, program menghitung total jarak dari setiap segmen perjalanan yang dimasukkan oleh pengguna.

Program juga menampilkan rincian jalur antar kota, jarak setiap segmen, proses penjumlahan, dan total keseluruhan jarak. Output ini menjadi bagian penting karena menunjukkan bahwa program tidak hanya menghitung, tetapi juga memberikan transparansi dalam prosesnya.

Bagian Menampilkan Output Berupa Perhitungan dan Total Jarak

Studi Kasus: Cairo → Hong Kong → Mexico City

Pada studi kasus ini, dilakukan perhitungan rute dari Cairo menuju Hong Kong, kemudian dilanjutkan ke Mexico City.

Program akan secara otomatis:

• Mencari rute terpendek dari Cairo ke Hong Kong
• Mencari rute terpendek dari Hong Kong ke Mexico City
• Menjumlahkan total jarak perjalanan

Setiap segmen perjalanan akan ditampilkan secara rinci, termasuk kota-kota perantara yang dilalui.

Input pada Program

Hasil Perhitungan Jarak Cairo ke Hong Kong

Hasil Perhitungan Jarak Hong Kong ke Mexico City

Total Keseluruhan Jarak

Visualisasi Menggunakan GeoGebra

Selain menggunakan kode Python, visualisasi rute juga dilakukan menggunakan GeoGebra. Dengan GeoGebra, hubungan antar kota dapat divisualisasikan dalam bentuk graf, sehingga jalur yang diambil oleh algoritma dapat terlihat secara langsung.

Visualisasi ini membantu dalam memahami bagaimana algoritma memilih jalur tertentu dibandingkan jalur lainnya.

Tampilan Rute pada GeoGebra

Analisis Hasil

Dari hasil yang diperoleh, terlihat bahwa algoritma mampu menemukan rute paling efisien dengan mempertimbangkan berbagai kemungkinan jalur. Dalam beberapa kasus, rute terpendek tidak selalu merupakan jalur langsung, melainkan melalui beberapa kota perantara.

Hal ini menunjukkan keunggulan pendekatan matriks dan algoritma Floyd-Warshall dalam mengevaluasi seluruh kemungkinan jalur secara menyeluruh.

Selain itu, sistem juga berhasil menampilkan rincian perhitungan secara transparan, sehingga hasilnya dapat dipahami dan diverifikasi dengan mudah.

Kesimpulan

Berdasarkan implementasi yang telah dilakukan, dapat disimpulkan bahwa pendekatan berbasis matriks dengan algoritma Floyd-Warshall efektif digunakan untuk mencari rute terpendek antar kota.

Program yang dibuat tidak hanya mampu menghitung jarak minimum, tetapi juga menampilkan jalur perjalanan secara detail. Integrasi dengan GeoGebra juga memberikan nilai tambah dalam bentuk visualisasi graf yang memperjelas hasil perhitungan.

Dengan demikian, sistem ini dapat dijadikan sebagai dasar untuk pengembangan sistem navigasi yang lebih kompleks di masa depan.

Lampiran Code Lengkap

Pada bagian ini, sertakan seluruh kode Python yang telah dibuat sebagai bukti implementasi.

import numpy as np

# 1. DAFTAR KOTA
DAFTAR_KOTA = [
    "San Francisco", "Los Angeles", "Chicago", "Mexico City", "Atlanta",
    "Montréal", "Miami", "Bogotá", "Lima", "New York", "Washington",
    "Santiago", "Buenos Aires", "São Paulo", "Lagos", "Khartoum",
    "Kinshasa", "Johannesburg", "Madrid", "London", "Essen", "Paris",
    "Milan", "St. Petersburg", "Algiers", "Cairo", "Istanbul", "Baghdad",
    "Moscow", "Tehran", "Riyadh", "Karachi", "Mumbai", "Delhi", "Kolkata",
    "Chennai", "Bangkok", "Jakarta", "Ho Chi Minh City", "Hong Kong",
    "Shanghai", "Beijing", "Seoul", "Tokyo", "Osaka", "Taipei", "Manila", "Sydney"
]

# 2. DATA KONEKSI & JARAK (Update Berdasarkan File Terbaru)
DATA_JARAK = [
    ("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. INISIALISASI MATRIKS
city_to_idx = {city.lower(): i for i, city in enumerate(DAFTAR_KOTA)}
idx_to_city = {i: city for i, city in enumerate(DAFTAR_KOTA)}
num_nodes = len(DAFTAR_KOTA)

dist_matrix = np.full((num_nodes, num_nodes), np.inf)
np.fill_diagonal(dist_matrix, 0)
next_node = [[None for _ in range(num_nodes)] for _ in range(num_nodes)]

for u_name, v_name, weight in DATA_JARAK:
    u, v = city_to_idx[u_name.lower()], city_to_idx[v_name.lower()]
    dist_matrix[u][v] = dist_matrix[v][u] = weight
    next_node[u][v], next_node[v][u] = v, u

# 4. ALGORITMA FLOYD-WARSHALL
for k in range(num_nodes):
    for i in range(num_nodes):
        for j in range(num_nodes):
            if dist_matrix[i][j] > dist_matrix[i][k] + dist_matrix[k][j]:
                dist_matrix[i][j] = dist_matrix[i][k] + dist_matrix[k][j]
                next_node[i][j] = next_node[i][k]

# 5. FUNGSI NAVIGASI
def get_valid_city(prompt):
    while True:
        entry = input(prompt).strip().lower()
        if entry in city_to_idx:
            return idx_to_city[city_to_idx[entry]]
        print(f"Kota '{entry}' tidak ditemukan. Silakan cek daftar kota.")

# 6. INTERFACE
print("--- SISTEM NAVIGASI MATRIKS (DATA TERKOREKSI) ---")
try:
    n = int(input("Mau input berapa titik kota? "))
    if n < 2: exit()

    titik_kota = [get_valid_city(f"Masukkan Kota ke-{i+1}: ") for i in range(n)]
    total_jarak_akhir = 0
    print("\n" + "="*50)

    for i in range(len(titik_kota) - 1):
        asal, tujuan = titik_kota[i], titik_kota[i+1]
        u_idx, v_idx = city_to_idx[asal.lower()], city_to_idx[tujuan.lower()]

        # Rekonstruksi Jalur
        path_indices = []
        curr = u_idx
        while curr != v_idx:
            path_indices.append(curr)
            curr = next_node[curr][v_idx]
        path_indices.append(v_idx)

        print(f"Rincian Bagian: {asal} -> {tujuan}")
        sub_total = 0
        rincian_angka = []
        for j in range(len(path_indices)-1):
            a, b = path_indices[j], path_indices[j+1]
            d = dist_matrix[a][b]
            sub_total += d
            rincian_angka.append(str(round(d, 2)))
            print(f"  {idx_to_city[a]} -> {idx_to_city[b]} : {d:.2f}")

        print(f"  Proses: {' + '.join(rincian_angka)} = {sub_total:.2f}")
        total_jarak_akhir += sub_total
        print("-" * 30)

    print(f"TOTAL JARAK KESELURUHAN: {total_jarak_akhir:.2f}")
    print("="*50)

except ValueError:
    print("Input harus angka.")

Lampiran Output Studi Kasus

--- SISTEM NAVIGASI MATRIKS (DATA TERKOREKSI) ---
Mau input berapa titik kota? 3
Masukkan Kota ke-1: Cairo
Masukkan Kota ke-2: Hong Kong
Masukkan Kota ke-3: Mexico City

==================================================
Rincian Bagian: Cairo -> Hong Kong
  Cairo -> Baghdad : 6.89
  Baghdad -> Karachi : 7.31
  Karachi -> Delhi : 5.51
  Delhi -> Kolkata : 5.58
  Kolkata -> Hong Kong : 6.07
  Proses: 6.89 + 7.31 + 5.51 + 5.58 + 6.07 = 31.36
------------------------------
Rincian Bagian: Hong Kong -> Mexico City
  Hong Kong -> Kolkata : 6.07
  Kolkata -> Delhi : 5.58
  Delhi -> Karachi : 5.51
  Karachi -> Baghdad : 7.31
  Baghdad -> Cairo : 6.89
  Cairo -> Algiers : 5.66
  Algiers -> Madrid : 8.98
  Madrid -> New York : 12.74
  New York -> Washington : 4.80
  Washington -> Miami : 7.06
  Miami -> Mexico City : 8.53
  Proses: 6.07 + 5.58 + 5.51 + 7.31 + 6.89 + 5.66 + 8.98 + 12.74 + 4.8 + 7.06 + 8.53 = 79.13
------------------------------
TOTAL JARAK KESELURUHAN: 110.49
==================================================