Algorithm Dijkstra kunye nokwenziwa kwayo

Kukho indawo eyahlukileyo ebizwa theory igrafu kwimathematika nenzululwazi yekhompyutha. Njengenxalenye isethi yayo kunye nokusombulula iingxaki eziliqela, njengokukhetha umendo imfutshane phakathi eziphezulu. Enye phakathi zezibalo iindlela zokusombulula le ngxaki iye algorithm a Dijkstra kaThixo elide.

Yintoni igrafu zezibalo

Kukholelwa ukuba umba igrafu ezifakwa ukusetyenziswa kwinkulungwane elinesibhozo Leonardom Eylerom. Yaba nguye lowo wabhengeza ekucaciseni isisombululo enye yeengxaki ezaziwa le ngcamango - i iibhulorho ezisixhenxe Königsberg. Ukuze achaze injongo yale theory basoloko ukusebenzisa lo mfanekiso njengokuba intshukumo phakathi izixeko ezahlukahlukeneyo. Ngoko ke igrafu-moya iza kuba mzobo yonke indlela, apho eziphezulu babe izinto ezithile (umz, imizi), kwaye ezinemiphetho - indlela ukusuka enekona enye ukuya kwenye (indlela analog phakathi izixeko). algorithm Dijkstra kaThixo, ukongeza kwezinye iindlela, uyakwazi ukunika nesisombululo kulo mcimbi.

Ukufumana indlela enqamulelayo

Omnye wemisebenzi eziqhelekileyo kwethiyori grafu yenye apho ufuna ukuqonda indlela iindleko kangangoko phakathi kweendawo ezimbini. Kuyenzeka ukunciphisa-moya ukuya isigqibo igrafu apho eziphezulu - imizi - ezi iimbambo oqhagamshelwano phakathi, nto ke leyo indlela kunokwenzeka. indlela nganye ubude yayo, ke ngoko, ukuhamba kuwo kuza kufuneka ukuba uchithe imali. Esi sixa kulingana ngexabiso ubunzima kungqameko kwi grafu. Ke ingxaki kunokuzisa kwenziwa ngolu hlobo lulandelayo: ukuhlahlela indlela ngendlela ukusuka isixeko enye kwenye, ukuba kusetyenziswa elona endleleni iindlela.

iindlela zokusombulula

Ukusombulula le ngxaki esiye ezaqanjwa ngabanye ubuchule sezisaziwa kwi lesayensi ngokubanzi. Umzekelo, Floyd algorithm - Uorshella, Ford - Bellman. Indlela ezaziwa ekufumaneni izisombululo kwakhona algorithm Dijkstra kaThixo. Ingasetyenziswa xa kulinganiselwa (ubunzima ezaziwayo ekupheleni ngalinye) kuzo igrafu, kwaye yaze yangxenga ifuthe lomanyano. Ukuze ufumane indlela ultimate kufuneka wenze amanyathelo aliqela.

algorithm Dijkstra kaThixo

Ingongoma yale ndlela kuxhomekeke yokuba zonke eziphezulu yeendleko, eqalela ngqalelo, apho tag ngamnye wabelwe ixabiso ethile. Emva koko ke kuya kuquka eziphezulu yabo iilebhile sakugcina. On top of inyathelo lokuqala lokuqala ziya ithegi ezixabisa 0. Ngoko, zonke iincopho zilandelayo zithathwa, oko kukuthi, abo ifikeleleka ngendlea ukusuka kumthombo. Bona enombhalo, ixabiso apho umiselwa umdibaniso ikhowudi yemvelaphi kwaye ubunzima kweendlela. Ukususela phezulu inyathelo elilandelayo, khetha leyo eye ixabiso zincinane kwilebhile, waza wafunda zonke eziphezulu ukuba kuyo sikwazi ukuya ngaphandle kokusebenzisa iindawo eziphakathi. Khankanya zichaze omtsha elingana iincopho ileyibhile - ikhowudi yemvelaphi kunye ubunzima endleleni. Ukuba ixabiso lingaphantsi kwe-ileyibhile phezulu, ileyibhile kutshintshwe. Kungenjalo, lona luhlala ixabiso lokuqala. Ngelo xesha inye uluhlu eyahlukileyo, ogama icala lilingana nenani eziphezulu, igcina ziziphumo ifoun, apho indlela ezimisele. Ukuze kuphunyezwe indlela ezifana algorithm Dijkstra kaThixo, Pascal inika indlela elula kakhulu. I algorithm unalo inzuzo ukuba kungaba lula kuba sisiseko inkqubo othe ubukhulu encinane. Imizekelo iimveliso software lula ukufumana kwi Internet.

izisombululo kulu- izixhobo ezahlukeneyo ungasebenzisa umsebenzi ukufumana indlela kangangoko. Kuba izisombululo ezifana algorithm Dijkstra kaThixo, Ugcino iza kudala uhlobo elula input data olubonakalayo kunye neziphumo isiphumo lokugqibela.