Struktur Data Graph dan Algoritma
Shortest Path dari Dijkstra

Pengantar

Dalam tugas ke empat ini draft tugas adalah sama untuk semua kelompok asistensi. Tetapi, masing-masing asisten memiliki otoritas untuk menambahkan variasi tertentu (dan saya mengharapkannya begitu supaya terdapat perbedaan di antara kelompok).

Tugas ini adalah mengulangi Tugas ke 5 dari kuliah Struktur Data tahun lalu kecuali tugas dikerjakan dengan Applet/Java (iteraksi grafis). Terdapat pilihan dalam mengerjakannya:

• versi wajib: spesifikasi yang minimal harus dipeluhi oleh semua
• versi lanjutan: optional untuk mendapatkan nilai tambahan, spesifikasi dapat ditentukan oleh asisten ybs.

Jika anda mengerjakan versi wajib dengan sebaik-baiknya maka anda akan mendapatkan nilai penuh. Jika anda mengerjakan versi lanjutannya juga, maka anda akan mendapatkan nilai bonus.

Versi Wajib (minimal)

• membaca data graph dari suatu file ke dalam struktur data di memory serta men-save-nya jika terjadi perubahan (Note: untuk menyederhanakan masalah maka graph diasumsikan tak berarah, jadi setiap sisi berlaku untuk kedua arah / simetris).
• menyimpan dalam jumlah 'tak terbatas' verteks/sisi (dibatasi kapasitas memory)
• mengupdate informasi yang ada di struktur data (menghapus/menambah verteks baru, mengubah bobot sisi, menghapuskan/menambahkan ege baru).
• menjawab query shortest-path dari suatu verteks ke verteks lain dengan menjalankan algoritma Dijkstra.

Versi Lanjutan

• bobot sisi bersifat kombinasi dari beberapa kriteria (misalnya jarak, biaya, estimasi waktu tempuh dan jenis kendaraan yang boleh) dalam fungsi yang 'make sense' serta suatu dialog query shortest path menyertakan pemilihan kriteria tsb.
• algoritma Dijkstra dimodifikasi untuk dapat menangani 'kendala', misalnya, shortest path yang menghindari satu/beberapa verteks tertentu (kendala yang spesifik ataupun yang umum).
• struktur data tambahan dapat digunakan untuk membantu mempercepat proses
• verteks berisi soft link alamat suatu URL yang apabila diklik browser dapat mengakses alamat tsb.

Antarmuka yang diminta diberikan dalam templat yang segera di posting. Tetapi yang paling perlu anda utamakan adalah implementasi struktur data graph dinamis serta algoritma Dijkstra sendiri. Kreatifitas lain untuk antar muka dipersilakan tapi belum tentu mendapatkan nilai tambahan (jika dalam tugas ini anda kerjakan dengan baik maka nanti setelah kuliah Grafika Komputer anda bisa kembangkan suatu perangkat lunak navigasi yang bagus!).

Format data versi wajib (file teks):

• baris pertama berisi bilangan N yang menyatakan jumlah verteks
• N baris berikutnya menyatakan nama-nama verteks serta data posisi dalam penggambarannya yang masing-masing berformat: NAMA VERTEKS#absis#ordinat
  Note: NAMA VERTEKS adalah nama/id dari verteks dan pada graph akan digambarkan pada koordinat (absis, ordinat). Karakter # digunakan sebagai separator.
• baris berikutnya berisi bilangan M yang menyatakan jumlah sisi
• M baris berikutnya menyatakan informasi mengenai sisi-sisi tsb., setiap baris berformat:
  
  VERTEKS ASAL#VERTEKS TUJUAN#WEIGHT
  Note: VERTEKS ASAL adalah nama verteks asal sisi, VERTEKS TUJUAN adalah nama verteks tujuan sisi, dan WEIGHT adalah bilangan real berisikan bobot. Disini juga karakter # digunakan sebagai separator. Karena sisi simetris maka sisi ini berlaku untuk kedua arah.

  Contoh: Lihat data contoh dan lihat graph tersebut jika digambarkan.

Untuk versi lanjutan maka bobot bisa dinyatakan terdiri atas beberapa bilangan sesuai dengan kriteria yang anda pakai. Demikian juga informasi verteks dapat disertakan setelah nama verteks tsb. untuk dapat digunakan dalam query berkendala.

Data test yang disediakan adalah untuk versi wajib saja karena format versi lanjutan ini nanti bisa tidak standard. Jadi bagi anda yang membuat versi lanjutan harus juga mengumpulkan versi wajibnya kecuali kalau anda bisa membuat satu program yang dapat mengenali baik format wajib maupun format lanjutannya.