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:

Xª Flottiglia MAS (Regno d'Italia)

10ª Flottiglia MASTeseo Tesei, sviluppatore del siluro a lenta corsa Descrizione generaleAttiva23 aprile 1939 - 8 settembre 1943 Nazione Italia RuoloAttacco al naviglio nemico in rada tramite sabotaggio e in mare aperto con l'uso di naviglio sottile silurante o esplodente EquipaggiamentoNaviglio sottile; mezzi d'assalto subacquei e di superficie trasportabili da sommergibili modificati MottoMemento audere semper per la 1ª Flottiglia MASPer il Re e per la bandiera per la Xª Flottiglia ...

 

Daftar film Korea

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Oktober 2022. Daftar film Korea dapat merujuk pada: Daftar film Korea (Pra 1948), kronologi film-film Korea Bersatu sebelum pembagian negara Daftar film Korea Selatan, kronologi film yang diproduksi di Korea Selatan (pasca September 1948) Daftar film Korea Utara, kr...

 

Insiden 28 Januari

Insiden 28 JanuariBagian dari the Perang Tiongkok-Jepang KeduaTanggal28 Januari – 3 Maret 1932LokasiShanghai, TiongkokHasil Gencatan senjata; demiliterisasi ShanghaiPihak terlibat Republik Tiongkok  Empire of Japan Kekaisaran JepangTokoh dan pemimpin 19th Route Army: Jiang Guangnai (Chinese: 蔣光鼐), 5th Army: Zhang Zhizhong (Chinese: 張治中) Commander: Yoshinori Shirakawa (白川義則code: ja is deprecated ), Chief of staff: Kanichiro Tashiro (田代皖一郎code: ja is depreca...

Dust explosion

Rapid combustion of fine particles suspended in the air Lab demonstration with burning lycopodium powder A dust explosion is the rapid combustion of fine particles suspended in the air within an enclosed location. Dust explosions can occur where any dispersed powdered combustible material is present in high-enough concentrations in the atmosphere or other oxidizing gaseous medium, such as pure oxygen. In cases when fuel plays the role of a combustible material, the explosion is known as a fue...

 

Hart of Dixie

Not to be confused with Heart of Dixie (film). American comedy-drama television series Hart of DixieGenre Comedy drama Created byLeila GersteinStarring Rachel Bilson Jaime King Cress Williams Wilson Bethel Scott Porter Tim Matheson Kaitlyn Black ComposerJeremy AdelmanCountry of originUnited StatesOriginal languageEnglishNo. of seasons4No. of episodes76 (list of episodes)ProductionExecutive producers Leila Gerstein Donald Todd Josh Schwartz Stephanie Savage Jason Ensler Len Goldstein Producers...

 

Truce of Yam-Zapolsky

1582 peace treaty between the Poland–Lithuania and Russia Stephen Báthory near Pskov. Painting by Jan Matejko, 1872. Truce of Yam-Zapolsky, orange indicates territories recovered by Polish–Lithuanian Commonwealth The Truce or Treaty of Yam-Zapolsky (Ям-Запольский) or Jam Zapolski, signed on 15 January 1582 between the Polish–Lithuanian Commonwealth and the Tsardom of Russia, was one of the treaties that ended the Livonian War.[1] It followed the successful Livonian ...

Cadillac Records

Cadillac RecordsPoster perilisanSutradaraDarnell MartinProduserSofia SondervanAndrew LackDitulis olehDarnell MartinPemeranAdrien BrodyBeyoncé KnowlesJeffrey WrightNaratorCedric the EntertainerPenata musikTerrence BlanchardSteve JordanSinematograferAnastas MichosPenyuntingPeter C. FrankPerusahaanproduksiSony Music FilmParkwood EntertainmentDistributorTriStar Pictures (AS)Tanggal rilis 05 Desember 2008 (2008-12-05) (AS) Durasi109 menitNegaraAmerika SerikatBahasaInggrisAnggaran$1...

 

Wheeling University

Catholic university in Wheeling, West Virginia, US Wheeling UniversityFormer namesWheeling College (1954–1987)Wheeling Jesuit College (1987–1996) Wheeling Jesuit University (1996–2019)MottoLuceat Lux Vestra (Latin)Motto in EnglishLet your light shineTypePrivate universityEstablished1954; 70 years ago (1954)Religious affiliationRoman CatholicAcademic affiliationsACCUNAICU CICEndowment$16.1 million[1]Academic staff77 full-time[2]Students1,289 (fall 2...

 

Paul Morton

American politician For other people named Paul Morton, see Paul Morton (disambiguation). Paul Morton36th United States Secretary of the NavyIn officeJuly 1, 1904 – June 30, 1905PresidentTheodore RooseveltPreceded byWilliam MoodySucceeded byCharles Bonaparte Personal detailsBorn(1857-05-22)May 22, 1857Detroit, Michigan, U.S.DiedJanuary 19, 1911(1911-01-19) (aged 53)New York City, New York, U.S.Political partyRepublicanChildrenPauline SabinParentJulius Sterling Morton (father)S...

Kenilworth

Town and civil parish in Warwickshire, England For other uses, see Kenilworth (disambiguation). Human settlement in EnglandKenilworthClock tower at the junction of The Square, Smalley Place and Abbey EndKenilworthLocation within WarwickshirePopulation22,538 (2021 Census)[1]OS grid referenceSP2971Civil parishKenilworthDistrictWarwickShire countyWarwickshireRegionWest MidlandsCountryEnglandSovereign stateUnited KingdomPost townKENILWORTHPostcode districtCV8...

 

Johann Hinrich Wichern

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (août 2017). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ». En pratique : Quelles sources sont attendues ? Com...

 

Felice Damiani

Pour les articles homonymes, voir Damiani. Cet article est une ébauche concernant un peintre italien. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Felice DamianiNaissance 1560GubbioDécès 1608Activité Peintremodifier - modifier le code - modifier Wikidata Crucifixion and saints, Sant'Agostino (Gubbio) Felice Damiani dit Felice da Gubbio est un peintre italien maniérisme, originaire de Gubbio, qui fut acti...

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。 约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

 

俄亥俄州

  「俄亥俄」重定向至此。关于其他用法，请见「俄亥俄 (消歧义)」。 俄亥俄州 美國联邦州State of Ohio 州旗州徽綽號：七葉果之州地图中高亮部分为俄亥俄州坐标：38°27'N－41°58'N, 80°32'W－84°49'W国家 美國加入聯邦1803年3月1日，在1953年8月7日追溯頒定（第17个加入联邦）首府哥倫布（及最大城市）政府 • 州长（英语：List of Governors of {{{Name}}}]]） •&...

 

中華民國—瑞士關係

  提示：此条目页的主题不是中國—瑞士關係。   關於中華民國與「瑞」字國家的外交關係，詳見中瑞關係 (消歧義)。 中華民國—瑞士關係 中華民國 瑞士 代表機構駐瑞士台北文化經濟代表團瑞士商務辦事處代表代表 黃偉峰 大使[註 1][4]處長 陶方婭[5]Mrs. Claudia Fontana Tobiassen 中華民國—瑞士關係（德語：Schweizerische–republik china Beziehungen、法�...

2005 State of Origin series

Australian rugby league contest 2005 State of Origin seriesWon by New South Wales (12th title)Series margin2-1Points scored140Attendance187,309 (ave. 62,436 per match)Player of the series Anthony MinichielloTop points scorer(s) Cameron Smith (18)Top try scorer(s) Matt Bowen Matt King (3) ← 2004 State of Origin series 2006 → The 2005 State of Origin series saw the 24th time that the annual three-game series between the Queensland and New South Wales representative rugby league footbal...

 

2005 FIFA Club World Championship final

Association football match Football match2005 FIFA Club World Championship finalOfficial programme of the tournamentEvent2005 FIFA Club World Championship São Paulo Liverpool 1 0 Date18 December 2005VenueInternational Stadium, Yokohama[1]RefereeBenito Archundia (Mexico)[1]Attendance66,821[1]← 2000 2006 → The 2005 FIFA Club World Championship final was an association football match played between São Paulo of Brazil, the CONMEBOL club champions, and Liverp...

 

I'm Not There

2007 film by Todd Haynes I'm Not ThereTheatrical release posterDirected byTodd HaynesScreenplay by Todd Haynes Oren Moverman Story byTodd HaynesProduced by Christine Vachon James D. Stern John Sloss John Goldwyn Starring Christian Bale Cate Blanchett Marcus Carl Franklin Richard Gere Heath Ledger Ben Whishaw Charlotte Gainsbourg David Cross Bruce Greenwood Julianne Moore Michelle Williams CinematographyEdward LachmanEdited byJay RabinowitzProductioncompanies Endgame Entertainment Killer Films...

Same-sex marriage in Jersey

Not to be confused with Same-sex marriage in New Jersey. Part of the LGBT rights seriesLegal status ofsame-sex unions Marriage Andorra Argentina Australia Austria Belgium Brazil Canada Chile Colombia Costa Rica Cuba Denmark Ecuador Estonia Finland France Germany Greece Iceland Ireland Liechtenstein* Luxembourg Malta Mexico Nepal Netherlands1 New Zealand2 Norway Portugal Slovenia South Africa Spain Sweden Switzerland Taiwan United Kingdom3 United States4 Uruguay Recognized Israel5 Civil union...

 

Serving the Servant

2019 non-fiction book by Danny Goldberg Serving the Servant: Remembering Kurt Cobain First edition (US)AuthorDanny GoldbergLanguageEnglishGenreMemoirPublisherEcco Press (US)Orion Books (UK)Publication dateApril 02, 2019[1]Publication placeUnited StatesPages304ISBN978-0062861504 Serving the Servant: Remembering Kurt Cobain is a book by Danny Goldberg, former music manager of Nirvana, and current president and owner of Gold Mountain Entertainment. It was published in April 2019, on the ...