69

Android – Aplikasi dijkstra rute angkutan umum

Tutorialnya sebelumnya :

1. Membuat rute angkutan umum di https://www.google.com/maps/d/
2. Menggambar graf sesuai rute yang dibuat pada tahap 1
3. Membuat koordinat rute angkutan umum dan SMK di http://graph.latcoding.com
4. Mengupdate graf yang sudah dibuat pada tahap 2
5. Menggunakan database Sqlite di Mozilla (untuk menyimpan grafnya)

Tahap 6 (Finishing) : Pembuatan aplikasi pencarian rute angkutan umum menggunakan algoritma dijkstra di android – aplikasi dijkstra.

Download aplikasinya

download app dijkstra in android

Tutorial kali ini akan menjelaskan ‘sedikit’ cara pembuatan aplikasi pencarian rute angkutan umum menggunakan algoritma dijkstra di android. Loh kenapa sedikit? ya karena lumayan banyak script yg dibuat gan. :hammer: Kalo mau tau lebih detail scriptnya, oprek2x sendiri gan. Udah dikasi komentar kok tiap scriptnya. Yang saya bahas disini lebih menerangkan alur sistemnya, OK?
Btw, buat yang belum baca tutorial sebelumnya, baca dulu tutorial di atas, nanti baru kesini lagi.

Oke, kita disini akan membuat aplikasinya menggunakan eclipse ya, jadi buat yang pake android studio harap menyesuaikan.

Cekidot cara pembuatannya ::

1. Karena aplikasi yg kita buat berbasis peta, dapetin dulu ‘API KEY GOOGLE ANDROID‘ buat munculin peta di android. Caranya? ada di sini
2. Setelah itu buka eclipse tentunya
starting ADT software3. Kita buat projectnya, isi kaya di bawah, trus next aja sampek finish
create a new project android4. Setelah projectnya kebuat, sekarang buka AndroidManifest.xml, tambahkan tag ‘permission’ dan ‘meta-data’
permission and  meta-data TAG android
* yang dicoret hijau ganti dengan API KEY punya anda.

.............
<permission android:name="com.app.dijkstra.permission.MAPS_RECEIVE" android:protectionLevel="signature"></permission>
<uses-permission android:name="com.app.dijkstra.permission.MAPS_RECEIVE" />
<uses-permission android:name="android.permission.ACCESS_NETWORK_STATE" />
<uses-permission android:name="android.permission.INTERNET" />
<uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE" />
<uses-permission android:name="android.permission.ACCESS_COARSE_LOCATION" />
<uses-permission android:name="android.permission.ACCESS_FINE_LOCATION" />
<uses-permission android:name="com.google.android.providers.gsf.permission.READ_GSERVICES" />

................. 
<meta-data android:name="com.google.android.gms.version" android:value="@integer/google_play_services_version" />
<meta-data android:name="com.google.android.maps.v2.API_KEY" android:value="API_KEY_ANDA" />

5. Lalu Import library ‘google-play-services_lib’ supaya icon silang merah pada gambar di atas hilang. Caranya klik kanan ‘App_dijkstra’ > Properties > android > add > ok > ok
import google play service6. Copy database schoolnav.sqlite yang sudah kita buat pada tutorial ke 5, ke dalam folder App_dijkstra/assets, lalu klik kanan ‘App_dijkstra’ > Refresh
database schoolnavapp dijkstra refresh7. Sekarang kita akan edit activity.xml, buka res > layout > activity.xml.
Paste-kan script dibawah ini ke activity.xml

<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="http://schemas.android.com/tools" android:layout_width="match_parent" android:layout_height="match_parent" tools:context=".MainActivity">
<FrameLayout xmlns:android="http://schemas.android.com/apk/res/android" android:id="@+id/content_frame" android:layout_width="match_parent" android:layout_height="match_parent" android:orientation="horizontal">
<fragment android:id="@+id/peta" android:layout_width="match_parent" android:layout_height="match_parent" android:name="com.google.android.gms.maps.SupportMapFragment" />
</FrameLayout>
<FrameLayout android:layout_width="match_parent" android:layout_height="wrap_content" android:layout_alignParentTop="true">
<LinearLayout android:layout_width="match_parent" android:layout_height="96dip" android:orientation="vertical" android:weightSum="2">
<Spinner android:layout_width="match_parent" android:layout_height="wrap_content" android:layout_centerHorizontal="true" android:layout_centerVertical="true" android:id="@+id/spinner_list_smk"></Spinner>
</LinearLayout>
</FrameLayout>
</RelativeLayout>

8. Setelah itu import gambar ‘angkot’ ke folder drawable-mdpi
car app dijkstragambarnya bisa didownload dari sini

9. Download file .java dari sini, lalu import file tersebut seperti gambar dibawah
import file java in eclipse

10. Ada beberapa file .java yang diperlukan dalam aplikasi ini
SQLHelper.java
Buat koneksi ke database sqlite
GraphToArray.java
Class untuk menkonversi tabel ‘graph’ dari database ke dalam bentuk array[][] multi dimensional. Array ini dipergunakan untuk perhitungan algoritma dijkstra nantinya.
Get_koordinat_awal_akhir.java
Class untuk mendapatkan koordinat jalur angkutan umum terdekat dari posisi kita berada dan posisi SMK.
Tambah_simpul.java
Menkonversi koordinat jalur angkutan umum terdekat menjadi sebuah simpul baru (simpul awal dan akhir)
Count_Bobot_Tambah_Simpul.java
Menghitung total jarak jika ada simpul baru (simpul awal dan akhir)
dijkstra.java
Ini yang paling penting, perhitungan algoritma dijkstra akan di proses pada class ini.
– MainActivity.java
Class utama di android

Untuk lebih jelasnya, alur sistem aplikasinya seperti ini :

flowchart app dijkstra

Penjelasan flowcartnya sebagai berikut :


1. MainActivity.java

Pertama kali aplikasi akan mencari koordinat posisi kita berada dan koordinat tujuan yaitu SMK.
– Script untuk mencari koordinat posisi kita berada (via tap pada peta) yaitu :

	@Override
	public void onMapClick(LatLng arg0) {
		// TODO Auto-generated method stub

		// your coordinate position
		double latUser = arg0.latitude;
		double lngUser = arg0.longitude;

		__global_yourCoordinate_exist = arg0;

		// destination coordinate position
		String endposition = __global_endposition;

		if(endposition != null){

			// dipecah coordinate SMK
			String[] exp_endposition = endposition.split(",");
			double lat_endposition = Double.parseDouble(exp_endposition[0]);
			double lng_endposition = Double.parseDouble(exp_endposition[1]);

			// ========================================================================
			// CORE SCRIPT
			// fungsi cari simpul awal dan tujuan, buat graph sampai algoritma dijkstra
			// ========================================================================
			try {
				startingScript(latUser, lngUser, lat_endposition, lng_endposition);
			} catch (JSONException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}

		}else{
			Toast.makeText(getApplicationContext(), "pilih SMK dulu", Toast.LENGTH_LONG).show();
		}
	}


– Script untuk mendapatkan posisi koordinat tujuan (SMK) yaitu :

		spinner.setOnItemSelectedListener(new AdapterView.OnItemSelectedListener() {

			@Override
			public void onItemSelected(AdapterView<> arg0, View arg1,
					int arg2, long arg3) {
				// TODO Auto-generated method stub

				if(arg0.getItemAtPosition(arg2).toString() != "-- Pilih SMK --"){

	 				String pilih_smk = arg0.getItemAtPosition(arg2).toString();
	 				cursor = db.rawQuery("SELECT koordinat FROM sekolah where sekolah = '" + pilih_smk + "'", null);
	 				cursor.moveToFirst();
	 				cursor.moveToPosition(0);

	 				// get coordinate SMK from field koordinat
	 				__global_endposition = cursor.getString(0).toString();

	 				// user men-tap peta
	 				if(__global_yourCoordinate_exist != null){

	 					// your coordinate
	 					double latUser = __global_yourCoordinate_exist.latitude;
	 					double  lngUser = __global_yourCoordinate_exist.longitude;

	 					// destination coordinate SMK
	 					String[] exp_endCoordinate = __global_endposition.split(",");
	 					double lat_endposition = Double.parseDouble(exp_endCoordinate[0]);
	 					double lng_endposition = Double.parseDouble(exp_endCoordinate[1]);

	 					// ========================================================================
	 					// CORE SCRIPT
	 					// fungsi cari simpul awal dan tujuan, buat graph sampai algoritma dijkstra
	 					// ========================================================================
	 					try {
	 						startingScript(latUser, lngUser, lat_endposition, lng_endposition);
	 					} catch (JSONException e) {
	 						// TODO Auto-generated catch block
	 						e.printStackTrace();
	 					}

	 				}else{
	 					Toast.makeText(getApplicationContext(), "Tap pada peta untuk menentukan posisi Anda", Toast.LENGTH_LONG).show();
	 				}

				}// if -- pilih SMK --
			}

			@Override
			public void onNothingSelected(AdapterView<> arg0) {
				// TODO Auto-generated method stub

			}

	    });//setOnItemSelectedListener

2-3. Get_koordinat_awal_akhir.java

Setelah mendapatkan koordinat posisi kita dan koordinat SMK, selanjutnya adalah mencari koordinat jalur angkutan umum terdekat. Perhatikan gambar :
graph algoritma dijkstraPada gambar di atas, koordinat jalur angkutan umum terdekat dari posisi kita ada diantara simpul 0 dan 1 (kita sebut x), sedangkan koordinat jalur angkutan umum terdekat dari posisi SMK berada diantara simpul 4 dan 9 (kita sebut y). Lihat kembali ke flowchart pada simbol decision, apakah koordinat x dan y berada diantara dua simpul ? ternyata ‘YA’. Berarti kita harus menambahkan simpul baru seperti gambar dibawah :

adding vertex in graph4. Tambah_simpul.java

Pada gambar di atas, terdapat 2 buah simpul baru yaitu simpul awal 10 dan  simpul tujuan 11. Nah untuk membuat simpul 10 dan 11 itu menggunakan class Tambah_simpul.java ini.

5. MainActivity.java

Setelah didapatkan simpul awal dan tujuan, selanjutnya melakukan perhitungan algoritma dijkstra. Input utama dari algoritma dijkstra adalah simpul awal (10) dan tujuan/akhir (11) seperti gambar diatas.

	public void startingScript(double latUser, double lngUser, double lat_endposition, double lng_endposition) throws JSONException{				

.................
		// ALGORITMA DIJKSTRA
		// ==========================================
		dijkstra algo = new dijkstra();
		algo.jalurTerpendek(__global_graphArray, __global_simpul_awal, __global_simpul_akhir);
.................

	}

Return dari script di atas adalah jalur terpendek, yaitu 10->1->4->11

Setelah didapatkan jalur terpendek, kemudian digambarlah jalur menggunakan polyline menggunakan method :

public void drawJalur(String alg, String[] exp) throws JSONException{
.........
}

————— skip skip ——————

Balik lagi ke flowchart nomor 2-3. Jika posisi kita dan SMK tidak berada diantara 2 simpul(tp lebih ke satu simpul), maka tidak perlu untuk menambahkan simpul :
algoritma dijkstra7. MainActivity.java

Setelah didapatkan simpul awal dan tujuan/akhir (0 dan 9). Maka dilakukan perhitungan dijkstra juga seperti langkah flowchart nomor 5.

	public void startingScript(double latUser, double lngUser, double lat_endposition, double lng_endposition) throws JSONException{				

.................
		// ALGORITMA DIJKSTRA
		// ==========================================
		dijkstra algo = new dijkstra();
		algo.jalurTerpendek(__global_graphArray, __global_simpul_awal, __global_simpul_akhir);
.................

	}

Return dari script di atas adalah jalur terpendek, yaitu 0->1->4->9

Setelah didapatkan jalur terpendek, kemudian digambarlah jalur menggunakan polyline menggunakan method :

public void drawJalur(String alg, String[] exp) throws JSONException{
.........
}

11. Running projectnya — selesai —

———————————————————-

Setelah aplikasi ini jadi, ada kelemahan jika algoritma dijkstra dijalankan di Android, yaitu :

1. Kalau simpulnya mencapai > 80, seperti ini
complex graphni aplikasi bakalan lemot pastinya. Kenapa? Karena memori hape & processornya kaga bakalan kuat. Mending proses algoritma dijkstranya dibuat via ‘web service’, jadi yang ngehandle server komputer bukan hape. wkkaka. Btw graph diatas itu hasil skripsi saya. Dan pas demo ke penguji muter2 doang appnya lemot 30 detik baru kebuka… Haha. Tapi alhamdulillah lulus 🙂

Buat yang males baca teks, bisa lihat tutorial versi videonya :

VIDEO TUTORIAL

1) [part 1 – convert graph] https://www.youtube.com/watch?v=1LBbyvZkcJ0
2) [part 2 – insert coordinates into sqlite DB] https://www.youtube.com/watch?v=pCapk8Xxxyo
3) [part 3 – finishing~create app] https://www.youtube.com/watch?v=2soi0VcNvz8

Ambar Hasbiyatmoko

Hello, I'm web developer. Passionate about programming, web server, and networking.

69 Comments

  1. Mantaf gan.. ijin minta ilmunya.. ada referensi cara membuat applikasi android algoritma dijkstra lagi ga??

    makasih gan..

  2. Saya ada kendala bang pas saya import kok banyak tanda merahnya ya.. Dan saya ikutin tutorial juga stuck di eclipsenya gan..

  3. gan, ane mau nanya dong, ane mau buat aplikasi tentang angkot gitu, nah ane ngesave rute angkot itu pake ini gan google(d0t)com/maps/d/ ? nah kalo bolak balik itu bikin 2 atau 1 aja ya? thanks

    • apanya yg bolak balik? rutenya?

      kalo rutenya bolak balik tapi jalurnya sama bikin 1 rute aja (nanti koordinat rutenya tinggal dibalik, dari A-B jadi B-A).

      kalo rutenya bolak balik tapi jalurnya berbeda, ya bikin 2 (koordinatnya juga dibikin 2, misal jalur berangkat:A-B-C –> jalur pulang:C-D-A).

      • cette tutoriel ne ça marche pas pour moi, quand j’execute l’application, elle bloque et affiche le message ” Unfortunately name app has stopped “, tu peut m’aider s’il vous plaît ?

      • gan kalo nambahin harga rutenya kira kira ditaro dimana ya? mohon pencerahannya

        • tambahin 1 field lagi -> ‘harga_rute’ di tabel angkutan_umum mas.
          Trus contoh isian fieldnya ky gini : ,2000,4000,5000,

  4. cette tutoriel ne ça marche pas pour moi, quand j’execute l’application, elle bloque et affiche le message ” Unfortunately name app has stopped “, tu peut m’aider s’il vous plaît ?

  5. Anda dapat membantu saya untuk menghitung kemacetan lalu lintas di jalan lalu lintas perkotaan di aplikasi ini

    • Anda dapat membantu saya untuk menghitung kemacetan lalu lintas di jalan lalu lintas perkotaan di aplikasi ini

  6. mas punya cara supaya lokasi kita terdeteksi sendiri lewat GPS nggak? jadi tidak perlu memilih lokasi awal lagi

  7. jika tujuan yg dicapai ada 3 bagaimana caranya mas? misalkan saya ingin ke tujuan 1,2 dan 3 kemudian tampil jarak 1, jarak 2, dan jarak 3 dan didapatlah jarak terpendek no 2,1,3.. maka saya akan ke tujuan 2 kemudian ke 1 baru ke 3.. nah untuk case diatas apa yang harus ditambahkan?

    makasih sebelumnya

    • kalo 3 tujuan, ya tinggal 3 kali looping dijkstranya mas bro :
      startingScript(latUser, lngUser, lat_tujuan1, lng_tujuan1);
      startingScript(latUser, lngUser, lat_tujuan2, lng_tujuan2);
      startingScript(latUser, lngUser, lat_tujuan3, lng_tujuan3);

      • jika di php dibagian mana yg di looping 3x mas? saya tes yg php dg mysql

        • kalo yg php, komennya di tutorial php mas.. jgn disini..

          • di comment di tutorial php tidak bisa komen mas, mkanya ane tanya disini..

  8. bro mau Tanya dong maklum newbie hehe. ane mau buat tugas akhir rute bus dalam dan luar kota kalau rute buat yg bus luar kotanya apakah harus bikin nodenya banyak seperti itu misalnya dari 0-9? apakah ada cara yg lebih singkatnya? soalnya kan kalo rute yg dilalui bus untuk luar kota kan panjang2 tuh, kayanya kalo dibikin nodenya seperti itu agak banyak ya? mohon pencerahannya

  9. mas, saya meng impementasikan source di atas, tp kenap ya klo simpul nya lebih dari sertus force close?

  10. Mas kalo mau di implementasikan ke android srudio bisa ga ya?
    sudah saya coba import,banyak yang error nya.

  11. mas mau tanya, ketika ada kasus seperti di bawah:
    nama angkot : A
    simpul rute : ,0-1,1-2,2-3,
    nama angkot : B
    simpul rute : ,4-5,5-6,6-3,

    graph pada table:
    0-1
    1-2(‘…….)
    2-3(‘…….)
    4-5(‘…….)
    5-6(‘…….)
    6-3(‘…….)

    yang ditanyakan, kenapa saat di build ke apk dan di coba pada device.
    lokasi awal di tap pada lokasi angkot b dan lokasi tujuan dekat angkot a,
    namun rute tidak keluar dan tidak ada error juga, itu kenapa ya mas?
    terimakasih

    • setelah saya cek di line 368 sampai 662 ga ada kendala, namun pada algo djikstra.java mas selalu hang ketika simpul seperti ini, ,0-1,1-2,2-71,71-3,3-5,5-6,6-7,7-8,8-10,
      terimakasih

  12. the file is not available anymore, can you send me the file instead?

  13. bang kalo mau nampilin hasil perhitungan jarak terpendeknya di textview gimana bang? urgent

  14. bang saya punya 500 node terus pas saya jalanin pencarian rutenya aplikasi nya ngefreeze tapi dijkstranya tetep jalan n berhasil nampilin jaraknya, tapi aplikasinya ngefreeze pas item di spinnernya diklik

    • Iya memang kalo nodenya banyak bakal lemot, solusinya pindahin algoritmanya ke web service, atau dibuat thread masing-masing diandroidnya.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload the CAPTCHA.