Penyelesaian masalah lintasan terpendek (shortest path) dengan menggunakan algoritma Johnson / Dewi Wahyuningsih
| Main Author: | Dewi Wahyuningsih |
|---|---|
| Format: | Thesis NonPeerReviewed |
| Terbitan: |
, 2009
|
| Subjects: | |
| Online Access: |
http://repository.um.ac.id/16750/ |
Daftar Isi:
- Teorigraphadalahsalahsatucabangdariilmumatematikayangsangatpentingdanbanyaksekaliaplikasinya.Salahsatunyaadalahpenyelesaianmasalahlintasanterpendek.AdabeberapametodeyangsudahadadanseringdigunakanuntukmenyelesaikanmasalahlintasanterpendekmisalnyaAlgoritmaDijkstraAlgoritmaBellmanForddanAlgoritmaFloyd-Warshall.Selainmenggunakanmetode-metodetersebutadametodelainyangdapatdigunakanuntukmenyelesaikanmasalahlintasanterpendekyaituAlgoritmaJohnson.Dalamskripsiinidibahastentangpenyelesaianmasalahlintasanterpendek(shortestpath)denganmenggunakanAlgoritmaJohnson.LangkahawalpenyelesaianAlgoritmaJohnsonadalahmengkonstruksidigraphbarudenganmenambahkantitikbarupadadigraphdanmemberibobotsisiyangkeluardarititikbarutersebutdengan0.Langkahselanjutnyaadalahmencarilintasanterpendekdarititikbarukesemuatitiklain.Lintasanterpendektersebutdigunakanuntukmengubahbobotsemuasisipadadigraphbaruagarbobotsemuasisibernilaipositif.Setelahitumencarilintasanterpendekdaritiaptitikkesemuatitiklaindanmengubahhasilnyadenganmenggunakanlintasanterpendekdarititikbarukesemuatitiklain.Hasildariperhitunganiniberupamatriks.Darimatriksinidapatdiketahuipanjanglintasanterpendekdaritiaptitikkesemuatitiklain.UntukmenghitunglintasanterpendekdarititikbarukesemuatitiklainyangbergunauntukmengubahsemuabobotmenjadipositifdigunakanAlgoritmaBellman-Ford.UntukmenghitunglintasanterpendekdaritiaptitikkesemuatitiklainyangsemuabobotsisinyasudahbernilaipositifdigunakanAlgoritmaDijkstra.KelebihanAlgoritmaJohnsoniniadalahdapatdigunakanuntukdigraphyangberbobotnegatifdanuntukmenyelesaikanmasalahlintasanterpendekdaritiaptitikkesemuatitiklain.UntukmemeriksakebenaranperhitungandariAlgoritmaJohnsondapatdigunakanAlgoritmaFloyd-Warshall.DariprosesperhitungandiperolehhasilyangsamaantarapenyelesaianmasalahlintasanterpendekdenganmenggunakanAlgoritmaJohnsondanAlgoritmaFloyd-Warshall.UntukmemeriksaperhitungansecaramanualdalamskripsiinijugadigunakanprogrambantuGIDEN.