Agilham/Tucil3_13521118_13521152

Tugas Kecil 3 -- IF2211 - Strategi Algoritma

Shortest Path Finder With UCS and A* Algorithm

---

Table of Contents

1. General Info
2. Creator Info
3. Features
4. Technologies Used
5. Setup
6. Usage
7. Screenshots
8. Structure
9. Project Status
10. Room for Improvement
11. Acknowledgements

General Information

Shortest Path Finder merupakan program yang berguna menentukan lintasan terpendek berdasarkan matriks ketetanggaan yang merepresentasikan graf berbobot. Matriks ketetanggan dapat diperoleh dengan dua cara, yaitu memasukkan input berupa sebuah file yang berisi matriks ketetanggaan antar simpul beserta namanya atau memasukkan koordinat peta yang akan diubah menjadi graf dan matriks ketetanggaan. Jika memilih menggunakan input file, pengguna akan diminta memilih start node dan end node. Jika memilih menggunakan koordinat peta, pengguna akan diminta memasukkan koordinat start point dan destination point. Program akan memanggil algoritma UCS dan A* untuk mencari shortest path, menampilkan informasi terkait hasil algoritma, dan membuat visualisasi graf atau peta beserta shortest path yang dihasilkan.

Creator Information

Nama	NIM	E-Mail
Ahmad Ghulam Ilham	13521118	13521118@std.stei.itb.ac.id
Muhammad Naufal Nalendra	13521152	13521152@std.stei.itb.ac.id

Features

• Pengguna dapat memilih metode input (file atau koordinat peta) program
• Pengguna dapat memilih start node dan end node (metode input file)
• Pengguna dapat memasukkan koordinat start point dan destination point (metode input koordinat peta)
• Pengguna dapat melihat informasi mengenai jarak, iterasi, dan waktu yang dihasilkan
• Pengguna dapat melihat graph atau peta beserta shortest path yang dihasilkan

Technologies Used

• Python 3.11
• Python Standard Library
• OpenStreetMap API
• Matplotlib
• NetworkX
• Folium

Note: The version of the libraries above is the version that we used in this project. You can use the latest version of the libraries.

Setup

1. Install Python
2. Install osmnx melalui command prompt:

pip install osmnx

3. Install matplotlib melalui command prompt:

pip install matplotlib

4. Install networkx melalui command prompt:

pip install networkx

5. Install folium melalui command prompt:

pip install folium

Usage

WINDOWS (VS Code)

Note: Untuk menjalankan program ini, pastikan anda telah memiliki semua requirements yang dibutuhkan

1. Clone repository ini ke dalam direktori lokal Anda, dengan cara:

git clone https://github.com/Agilham/Tucil3_13521118_13521152.git

2. Masuk ke dalam direktori Tucil3_13521118_13521152 yang telah Anda clone, dengan cara:

cd Tucil3_13521118_13521152

3. Buat terminal baru pada VSCode, masukkan perintah berikut:

python src/program.py

4. Ikuti petunjuk input yang diberikan program. Pastikan semua input yang dimasukkan valid. Informasi hasil algoritma (jarak, iterasi, waktu) akan ditampilkan pada terminal
5. Visualisasi graf (metode input file) beserta shortest path akan muncul sebagai pop up. Selama pop up belum ditutup, program akan berhenti berjalan. Pastikan untuk menutup pop up agar program kembali berjalan
6. Visualisasi peta (metode input koordinat peta) akan disimpan sebagai file ekstensi .html pada folder test. Buka file tersebut pada browser untuk melihat peta dan shortest path yang dihasilkan

Screenshots

1. Contoh Menggunakan File Matriks Ketetanggaan
2. Contoh Hasil Berdasarkan Input File
3. Contoh Menggunakan Koordinat Peta
4. Contoh Hasil Berdasarkan Input Koordinat

Structure

.
├── README.md
├── doc
│   └── Tucil3_13521118_13521152.pdf
├── img
│   ├── SS1.png
│   ├── SS2.png
│   ├── SS3.png
│   └── SS4.png
├── src
│   ├── lib
│   │   ├── astar.py
│   │   ├── input.py
│   │   ├── output.py
│   │   ├── prioitem.py
│   │   └── ucs.py
│   └── program.py
└── test
    ├── graph1.txt
    ├── graph2.txt
    └── graph3.txt

Project Status

Project is: Completed

Room for Improvement

• Menambahkan GUI

Acknowledgements

• Thanks To Allah SWT and His guidance, we were able to design this project without any meaningful hurdle

---