- Bala amabanga amancane phakathi kwawo wonke ama-node kumagrafu anesisindo usebenzisa uhlelo oluguquguqukayo.
- Buyekeza i-matrix yebanga ngokuphindaphinda phezu kwama-node aphakathi ukuze uthole imizila emifushane engaqondile.
- Yamukela izisindo ezingezinhle, ivumela ukubala lapho i-Dijkstra yehluleka khona, kodwa ithola futhi ayixazululi imijikelezo engezinhle.
- Isebenza kahle kumagrafu amancane noma aminyene; ubunzima bayo be-O(n³) bukhawulela ukusetshenziswa kwayo kumagrafu amakhulu kakhulu.
I -algorithm ye -Floyd-Warshall iyithuluzi elinamandla kwisayensi yamakhompyutha kanye nezibalo, ikakhulukazi eliwusizo kulabo abasebenza ngamagrafu nezinkinga zokwenza ngcono inethiwekhi . Le algorithm ikuvumela ukuthi uthole indlela emfushane phakathi kwazo zonke izibhangqwana zama-node kugrafu enesisindo, ukuxazulula ngempumelelo izinkinga eziyinkimbinkimbi.
Kulesi sihloko, sizohlola ngokujulile ukuthi i-algorithm isebenza kanjani, ukusetshenziswa kwayo, izinzuzo, kanye nokuqaliswa kwayo kwesinyathelo ngesinyathelo. Uma uke wazibuza ukuthi le-algorithm ingakusiza kanjani ngezinkinga zansuku zonke noma amaphrojekthi athuthuke kakhulu, qhubeka funda. Ake sikuhlukanise konke ukuze uqonde kalula.
Iyini i-algorithm ye-Floyd-Warshall?
I -algorithm ye-Floyd-Warshall iyindlela esetshenziswa ukubala amabanga amafushane kakhulu phakathi kwawo wonke ama-node kugrafu enesisindo. Iwusizo kakhulu ezinkingeni lapho amagrafu enesisindo esibi , njengoba ingazisingatha ngempumelelo, ngokungafani namanye ama-algorithm afana ne -algorithm kaDijkstra , angenawo.
Le nqubo isebenzisa indlela yokuhlela enamandla ukuze ibuyekeze ngokuphindaphindiwe i-array equkethe amabanga amafushane phakathi kwama-node. Ekupheleni kokuphindaphinda, i-array ibonisa izindlela ezimfushane phakathi kwanoma yimaphi ama-vertice amabili.
Isebenza kanjani i-algorithm
I-algorithm isekelwe ku- matrix eseduze kwegrafu yokufaka. Ibe isisebenzisa izihibe ezintathu ezihlanganisiwe ukuhlola zonke izindlela ezingenzeka phakathi kwama-node, ibuyekeza amabanga uma indlela engaqondile imfushane kuneleyo eqondile. Le nqubo yenziwa ngokuphindaphindiwe kuze kube yilapho zonke izinhlanganisela zendlela sezihloliwe.
Isibonelo esiyisisekelo sendlela lokhu okusebenza ngayo kungaba ukucabangela igrafu enama-vertices anezinombolo bese uhlola ukuthi ibanga elisuka ku-A liye ku-C nge-B lingaphansi kwebanga eliqondile elisuka ku-A liye ku-C. Ngokwenza lokhu ngenhlanganisela ngayinye yama-vertices, umphumela wokugcina uba yi-matrix ekhombisa amabanga amancane phakathi kwawo wonke ama-node.
Ukuqaliswa kwePython
Kulabo abafuna ukusebenzisa le algorithm kumaphrojekthi abo, ikhodi ye-Python iyindlela enhle kakhulu. Indlela eyisisekelo ichazwe ngezansi:
ukungenisa ama-sys INF = sys.maxsize def Floyd_Warshall(igrafu): n = len(igrafu) dist = yomugqa kugrafu] for k in range(n): for i in range(n): for j in range(n): dist = min(dist, dist + dist) return dist graph = , , , ] result = Floyd_Warshall(igrafu) print(umphumela)
Kulesi sibonelo, i-matrix yokufaka iqukethe amabanga phakathi kwamanodi. Inani le-'INF' limelela amapheya wamanodi angaxhumekile ngokuqondile. Uma selufakiwe, uhlelo lubuyisela i-matrix entsha enamabanga amancane abaliwe.
Izicelo ze-Floyd-Warshall Algorithm
Le algorithm ayilona nje ilukuluku lezibalo; Isebenza ezindaweni ezahlukahlukene:
- Idizayini yenethiwekhi yezokuthutha: Khomba imizila elungile phakathi kwamadolobha noma izindawo zokuthutha.
- Ukuxhumana namanethiwekhi: Bala imizila emifushane kumasistimu ezokuxhumana.
- Ukuthuthukisa isifunda: Dala amasekhethi asebenza kahle kakhulu ukuze unciphise izindleko nezikhathi.
Izinzuzo Nemikhawulo
I-algorithm ye-Floyd-Warshall inezinzuzo eziningana . Phakathi kwazo ikhono layo lokusebenza ngamagrafu anesisindo esingesihle , into engavamile kuma-algorithm amaningi. Ngaphezu kwalokho, kulula ukuyisebenzisa nokuyiqonda, okwenza ifinyeleleke ngisho nakubantu abasha ensimini.
Kodwa-ke, futhi inemikhawulo . Ubunzima bayo yi-O(n³), okusho ukuthi ayilungele amagrafu amakhulu kakhulu. Ezimweni ezinjalo, ezinye izindlela ezifana nama-algorithms asakazwe noma i-algorithm kaJohnson zingase zifaneleke kakhulu.
Amaphuzu Abalulekile Okufanele Uwakhumbule
Lapho uhlola ukuthi ingabe i-algorithm ye-Floyd-Warshall ikulungele yini ukuxazulula inkinga, cabangela lokhu okulandelayo:
- Ilungele amagrafu aphelele lapho izindlela zidinga ukubalwa phakathi kwawo wonke amapheya wamanodi.
- Isebenza kahle ngezisindo ezingezinhle, kodwa ayisekeli imijikelezo engalungile.
- Idinga i-matrix yokufaka emelela kahle ukuxhumana nezisindo phakathi kwamanodi.
I-algorithm ye-Floyd-Warshall iyithuluzi eliguquguqukayo nelinamandla lokuxazulula izinkinga zegrafu eziyinkimbinkimbi, ukusuka ebangeni elincane ukuya ekuthuthukisweni komzila. Ukuqonda ukuthi isebenza kanjani kuzokuvumela ukuthi uyisebenzise ngempumelelo ezimeni eziningi nasezimbonini eziningi.
