Algoritma Floyd-Warshall

Masalah-Algoritma-Floyd-Warshall

Algoritme Floyd-Warshall adalah algoritme untuk mencari lintasan terpendek pada sebuah graf berbobot dengan bobot positif atau negatif (namun tidak memiliki siklus negatif).

Sejarah

Algoritme Floyd-Warshall merupakan sebuah contoh penerapan dari pemrograman dinamis yang diperkenalkan oleh Robert Floyd pada tahun 1962. Namun, pada dasarnya memiliki kesamaan dengan algoritme yang pernah diperkenalkan sebelumnya oleh Bernard Roy pada tahun 1959 dan juga Stephen Warshall pada 1962.

Algoritme Floyd Warshall juga dikenal dengan Algoritme Floyd, Algoritme Roy-Warshall, Algoritme Roy-Floyd, dan algoritme WFI.

Algoritme

Algoritme Floyd-Warshall memiliki input graf berarah dan berbobot (V,E), yang berupa daftar titik (node/vertex V) dan daftar sisi (edge E). Jumlah bobot sisi-sisi pada sebuah jalur adalah bobot jalur tersebut. Sisi pada E diperbolehkan memiliki bobot negatif, akan tetapi tidak diperbolehkan memiliki siklus dengan bobot negatif. Algoritme ini menghitung bobot terkecil dari semua jalur yang menghubungkan sebuah pasangan titik, dan melakukannya sekaligus untuk semua pasangan titik. Algoritme ini berjalan dengan waktu Θ(|V|3).

Dasar algoritme ini adalah observasi berikut: 

--belum diterjemahkan—Implementasi algoritme ini dalam pseudocode:

(Graf direpresentasikan sebagai matrix keterhubungan, yang isinya ialah bobot/jarak sisi yang menghubungkan tiap pasangan titik, dilambangkan dengan indeks baris dan kolom) (Ketiadaan sisi yang menghubungkan sebuah pasangan dilambangkan dengan Tak-hingga) 


 function fw(int[1..n,1..n] graph) {
    // Inisialisasi
    var int[1..n,1..n] jarak:= graph
    var int[1..n,1..n] sebelum
    for i from 1 to n
        for j from 1 to n
            if jarak[i,j] < Tak-hingga
                sebelum[i,j]:= i
    // Perulangan utama pada algoritme
    for k from 1 to n
        for i from 1 to n
            for j from 1 to n
                if jarak[i,j] > jarak[i,k] + jarak[k,j]
                    jarak[i,j] = jarak[i,k] + jarak[k,j]
                    sebelum[i,j] = sebelum[k,j]
    return jarak
}

Aplikasi dan Generalisasi

  • Jalur terpendek dalam graf berarah (Algoritme Floyd).
  • Perhitungan cepat untuk menemukan rute terpendek dalam jaringan.

Implementasi

Referensi

Pranala luar

Read other articles:

Contea di Ohio (Kentucky)

Questa voce sull'argomento contee del Kentucky è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Contea di OhioconteaLocalizzazioneStato Stati Uniti Stato federato Kentucky AmministrazioneCapoluogoHartford Data di istituzione1799 TerritorioCoordinatedel capoluogo37°28′12″N 86°50′24″W / 37.47°N 86.84°W37.47; -86.84 (Contea di Ohio)Coordinate: 37°28′12″N 86°50′24″W / 37.47°N 86.84°W37.47;...

 

 

Lazio

Mapa kun diin makikit-an an mga lalawigan han Rehiyon han Lazio An Lazio (alternatibo nga ngaran ha Winaray ngan ha Kinatsila: Lacio; Linatin: Latium) amo an usa (1) ha karuhaan (20) ka rehiyon han Italya. An ulohan hini amo an Roma. Mga lalawigan han Lazio Frosinone Latina Rieti Roma Viterbo khlMga Rehiyon han Italya    AbruzzoSiong han AostaApuliaBasilicata CalabriaCampaniaEmilia-RomagnaFriuli-Venezia Giulia LazioLiguriaLombardiyaMarche MolisePiemonteSardinyaSicilia Trentino-...

 

 

Mike Gascoyne

Mike GascoyneNama lainGazzaPekerjaanInsinyurTahun aktif1989 - …Tempat kerjaTeam Caterham Mike Gazza Gascoyne (lahir 2 April 1963) adalah seorang insinyur ahli mobil Formula 1 asal Inggris. Saat ini ia bergabung di tim Team Caterham sebagai ahli aerodinamika. Profil Gazza merupakan lulusan Cambridge University, Inggris. Ia memulai karier di Westland Helicopters. Pada 1989 ia pindah ke McLaren bersama Steve Nichols. Kemudian di 1990 ia hengkang ke Tyrrell dan membuat penemuan revol...

Fernando Luiz Roza

Fernandinho Fernandinho bermain untuk Shakhtar Donetsk pada 2010Informasi pribadiNama lengkap Fernando Luiz RozaTanggal lahir 4 Mei 1985 (umur 38)Tempat lahir Londrina, BrasilTinggi 1,76 m (5 ft 9+1⁄2 in)Posisi bermain GelandangInformasi klubKlub saat ini Atlético ParanaenseKarier senior*Tahun Tim Tampil (Gol)2002–2005 Atlético Paranaense 72 (14)2005–2013 Shakhtar Donetsk 184 (31)2013–2022 Manchester City 382 (26)2022– Atlético Paranaense 0 (0)Tim nasiona...

 

 

Stalaktit

Stalaktit dari jenis yang disebut sedotan soda, di gua Choranche, Dataran Tinggi Vercors, Prancis. Stalaktit atau batu tetes[1] (Yunani: σταλάσσω, stalasso, artinya yang menetes) adalah jenis speleothem (mineral sekunder) yang menggantung dari langit-langit gua kapur. Ia termasuk dalam jenis batu tetes (Inggris: dripstone). Stalaktit terbentuk dari pengendapan kalsium karbonat dan mineral lainnya, yang terendapkan pada larutan air bermineral. Batu kapur adalah batuan k...

 

 

Prix ACM Software System

Prix ACM Software SystemPrésentationType Prix scientifique (d)Fondation 1983Site web (en) awards.acm.org/software-systemmodifier - modifier le code - modifier Wikidata ACM 2005 Software System Award Le prix ACM Software System ou ACM Software System Award, est attribué tous les ans depuis 1983 à une institution ou à une ou plusieurs personnes sélectionnée pour le développement d'un logiciel ayant eu une influence sur le long terme, qui s'est traduite par des contributions conceptu...

Konrad Adenauer

Konrad AdenauerAdenauer nel giugno 1952 Cancelliere federale della Germania[1]Durata mandato15 settembre 1949 –16 ottobre 1963 PresidenteTheodor HeussHeinrich Lübke Vice capo del governoFranz BlucherLudwig Erhard PredecessoreLutz Graf Schwerin von Krosigk[2] SuccessoreLudwig Erhard Ministro federale degli affari esteriDurata mandato15 marzo 1951 –6 giugno 1955 Capo del governose stesso PredecessoreLutz Graf Schwerin von Krosigk Succes...

 

 

Bamberg City Hall

United States historic placeBamberg City HallU.S. National Register of Historic Places Show map of South CarolinaShow map of the United StatesLocation3069 Main Hwy, Bamberg, South CarolinaCoordinates33°17′47″N 81°2′7″W / 33.29639°N 81.03528°W / 33.29639; -81.03528Arealess than one acreBuilt1909ArchitectSayre & BaldwinArchitectural styleClassical RevivalNRHP reference No.05001099[1]Added to NRHPSeptember 28, 2005 Bamberg City Hall,...

 

 

Le Palais-sur-Vienne

Peta infrastruktur dan tata guna lahan di Komune Le Palais-sur-Vienne.  = Kawasan perkotaan  = Lahan subur  = Padang rumput  = Lahan pertanaman campuran  = Hutan  = Vegetasi perdu  = Lahan basah  = Anak sungaiLe Palais-sur-Vienne merupakan sebuah komune di departemen Haute-Vienne di Prancis. Lihat pula Komune di departemen Haute-Vienne Referensi INSEE lbsKomune di departemen Haute-Vienne Aixe-sur-Vienne Ambazac Arnac-la-Poste Augne Aureil Azat-le-Ris Ba...

Bumps race

Form of rowing race Bumps redirects here. For other uses, see Bump (disambiguation). A ’bump’ during Torpids at the University of Oxford, 1999: Jesus College Men's 1st VIII catch Hertford College A bumps race is a form of rowing race in which a number of boats chase each other in single file, each crew attempting to catch and 'bump' the boat in front without being caught by the boat behind. The form is mainly used in intercollegiate competitions at the University of Oxford since 1815, and...

 

 

Permainan siluman

Artikel ini bukan mengenai Siluman. Artikel ini adalah bagian dari seri:Permainan video Pelantar Dingdong Konsol permainan Konsol video rumah Permainan elektronik Konsol genggam Permainan ponsel Permainan daring Permainan PC Linux Mac Genre Laga Berhantam Bertarung Arung pelantar Bertahan hidup Siluman Bertahan hidup horor Petualangan Bermain peran Bermain peran laga Bermain peran taktik Simulasi Konstruksi dan manajemen Simulasi kehidupan Olahraga Kendaraan Strategi Bertarung daring banyak p...

 

 

M1 carbine

Auto-loading carbine Carbine, Caliber .30, M1 M1 carbineTypeSemi-automatic carbine (M1)Selective-fire carbine (M2/M3)Place of originUnited StatesService historyIn service 1942–1973 (United States) 1942–present (other countries) Used bySee UsersWars World War II Hukbalahap Rebellion Chinese Civil War (limited) First Indochina War Indonesian National Revolution[1] Korean War Malayan Emergency Second Taiwan Strait Crisis Algerian War Suez Crisis Cuban Revolution V...

Тамбора (вулкан)

Ця стаття про вулкан. Про однойменну археологічну культуру див. Тамборська культура.Про мову тамбора див. Тамборська мова. Тамбора Вулкан Тамбора. Вид з космосуВулкан Тамбора. Вид з космосу 8°15′ пд. ш. 118°00′ сх. д. / 8.250° пд. ш. 118.000° сх. д. / -8.2...

 

 

Chiesa della Commenda

Chiesa della CommendaL'internoStato Italia RegioneEmilia-Romagna LocalitàFaenza Indirizzopiazza Frà Saba 1 ‒ Faenza (RA) Coordinate44°16′53.22″N 11°53′34.37″E44°16′53.22″N, 11°53′34.37″E ReligioneCattolica TitolareMaria Maddalena Diocesi Faenza-Modigliana Consacrazioneignoto Stile architettonicoromanico Inizio costruzione1100 Completamentoignoto Modifica dati su Wikidata · Manuale La chiesa della Commenda si trova nel Borgo Durbecco a Faenza. Fa parte della ...

 

 

Phidippus clarus

Species of spider Phidippus clarus Male Eastern female Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Arthropoda Subphylum: Chelicerata Class: Arachnida Order: Araneae Infraorder: Araneomorphae Family: Salticidae Subfamily: Salticinae Genus: Phidippus Species: P. clarus Binomial name Phidippus clarusKeyserling, 1884[1] Phidippus clarus is found in North America Phidippus clarus, also known as the brilliant jumping spider, is a species of jumping spider (fam...

Yamato River

River in Kansai, Japan Yamato RiverNative name大和川 (Japanese)LocationCountryJapanRegionKansai regionPhysical characteristicsSource  • locationKaikira-yama, Nara Prefecture • elevation822 m (2,697 ft) MouthOsaka Bay • coordinates34°36′30″N 135°26′28″E / 34.6084°N 135.4410°E / 34.6084; 135.4410Length68 km (42 mi) River in Sakurai, Nara Prefecture. The Yamato River (大和�...

 

 

Kekaisaran Maurya

Kekaisaran Mauryaमौर्य साम्राज्यम् (Sanskrit)मौर्य साम्राज्य (Hindi)322 SM–185 SM BenderaDinasti Maurya pada keemasannya di bawah kepemimpinan Asoka yang AgungIbu kotaPataliputraBahasa yang umum digunakanIndo-Arya (Sanskrit, Prakrit)Agama HinduBuddhaJainismePemerintahanMonarki absolut, sebagaimana diperihalkan dalam karya ArthashastraSamraat (Kaisar) • 320–298 SM Chandragupta Maurya• 187–180 SM Brihadrat...

 

 

M249 SAW

M 249 M 249 без магазина Тип Ручной пулемёт Страна  Бельгия (Minimi) США (M249) История службы Годы эксплуатации 1984 — настоящее время На вооружении  США Ливан[1]другие страны (список) Войны и конфликты Вторжение США в ПанамуВойна в Персидском заливеБоснийская войнаКо�...

Provincia de El Collao

Provincia de El Collao Provincia del Perú Paisaje de puna cerca a la localidad de Sahacata en el distrito de Santa Rosa. BanderaEscudo Coordenadas 16°05′07″S 69°38′13″O / -16.085277777778, -69.637041666667Capital IlaveIdioma oficial Español • Co-oficiales Quechua y aimaraEntidad Provincia del Perú • País Perú Perú • Departamento PunoAlcalde Villanueva Maquera Resalaso(2019-2022)Distritos 5Eventos históricos   • Fundación Creac...

 

 

Hidangan Yaman

Saltah dianggap merupakan hidangan nasional Yaman Letak Yaman Masakan Yaman adalah masakan khas secara keseluruhan dari masakan-masakan Timur Tengah paling dikenal, dan berbeda dari kawasan ke kawasan. Sepanjang sejarah, masakan Yaman mendapatkan pengaruh kecil Utsmaniyah di beberapa bagian utara, dan pengaruh gaya India Mughlai yang sangat kecil di Aden dan kawasan-kawasan sekitar di selatan, tetapi pengaruh-pengaruh tersebut baru datang pada 300 tahun terakhir. Masakan Yaman sangat populer ...