Lintasan terpendek adalah kumpulan sisiyang terhubung sehingga membentuk lintasan dengan jarak terpendek antara simpulawal ke simpul tujuanpada grafyang setiap sisinya memiliki bobot, pencarian rute jalan terdekat pada peta adalah salah satu contohnya. Optimasi waktu sebuah algoritma merupakan salah satu permasalahan yang terjadi pada penentuan lintasan terpendek. Pada penelitian Tugas Akhir ini, diterapkan algoritma berbasis coding graph untuk menentukan lintasan terpendek dari simpul awal ke simpul tujuan. Time complexity dari algoritma berbasis coding graph adalah O(n+e). Algoritma berbasis coding graph terdiri dari tiga tahapan utama, yakni pembentukan struktur data orthogonal list untuk menyimpan data graf dan solusi bobot lintasan terpendek, pembangunan coding graphdengan penelusuran seluruh simpuluntuk menentukan solusi bobot lintasan terpendek dan penentuan lintasan terpendek. Penulis mengusulkan pembangunancoding graph dengan penghentian penelusuran simpul untuk mengoptimasi waktu eksekusi. Dengan data masukan yakni peta kota Bandung yang diperoleh dari OpenStreetMap, sistem yang dibangun diimplementasikan pada GIS. Berdasarkan uji coba yang telah dilakukan, algoritma berbasis coding graph memiliki performansi yang baik untuk menentukan lintasan terpendek, hal ini dibuktikan dengan akurasi solusi sebesar 100%. Algoritma berbasis coding graph dengan menghentikan penelusuran simpul lebih baik performansinya dari segi waktu dibanding dengan algoritma berbasis coding graph dengan menelusuri seluruh simpul. Semakin banyak simpul yang harus ditelusuri maka semakin lama waktu yang dibutuhkan algoritma berbasis coding graph untuk menentukan lintasan terpendek. lintasan terpendek, optimasi waktu, coding graph, orthogonal list, dan GIS