Dextra algorithm le ts'ebetsong ea eona

Ka saense ea lipalo le saense ea khomphutha ho na le tataiso e fapaneng, e bitsoang khopolo ea lirafi. Ka moralo oa eona, mesebetsi e fapa-fapaneng e behiloe 'me e rarolloe, mohlala, ka ho fumana tsela e khutšoanyane pakeng tsa lintlha. E 'ngoe ea mekhoa e tloaelehileng haholo ea ho rarolla bothata bona har'a litsebi tsa lipalo e bile nako e telele e le algorithm ea Dijkstra.

Sebopeho sa lipalo ke eng

Ho lumeloa hore khopolo ea graph e ile ea hlahisoa lekholong la bo18 la lilemo ke Leonard Euler. E ne e le eena ea ileng a bua ka ho thehoa le tharollo ea mathata a mang a khale a thuto ena - ka marokho a supileng a Koenigsberg. E le hore re hlalosetse sepheo sa khopolo ena, hangata re sebelisa papiso e kang ea mokhatlo pakeng tsa metse e sa tšoaneng. Joale graph e sefofane e tla emela morero oohle oa litsela, moo lintlha li leng lintlha tse tobileng (ka mohlala, metse), 'me metse ea eona ke litsela tse tsoang ho vertex e' ngoe ho ea ho e 'ngoe (e tšoanang le tsela e pakeng tsa metse). Algorithm ea Dijkstra, ho phaella mekhoeng e meng, e ka fana ka tharollo potso ena.

Ho fumana tsela e khutšoanyane

E 'ngoe ea mathata a tloaelehileng a thuto ea graph ke e' ngoe eo ho hlokahalang hore ho khethoe tsela e lekaneng ea litšenyehelo pakeng tsa lintlha tse peli. E ka fokotsoa ka sefofane ho ea ho tharollo ea graph, eo lihlopha-metse-li kopantsoeng ka likhopo, tse emelang litsela tse ka khonehang. 'Me tsela e' ngoe le e 'ngoe e na le bolelele ba eona, ka hona, ho tsamaea ka eona e tla tlameha ho sebelisa chelete e itseng. Kakaretso ena e lekanang le boima ba lehlakoreng la graph. Joale bothata bo sebetsanang le boits'oaro bo ka etsoa ka tsela e latelang: mokhoa oa ho tsamaisa tsela e tsoang motseng o mong ho ea ho o mong, ho qeta chelete e le 'ngoe tseleng.

Tharollo

E le ho rarolla bothata bona, ho na le liqapi tse ling tse qapiloeng, tse ileng tsa tsejoa haholo lefatšeng la saense. Ka mohlala, algorithm ea Floyd-Warshell, algorithm ea Ford-Bellman. Algorithm ea Dijkstra ke mokhoa oa khale oa ho fumana tharollo. E ka boela ea sebelisoa bakeng sa boima ba 'mele (boima bo tsejoang ba lehlakoreng le leng le le leng), le bakeng sa tse fokolang. E le hore u fumane tsela ea ho qetela, u lokela ho etsa mehato e seng mekae.

Algorithm ea Dijkstra

Tlhaloso ea mokhoa ona ke hore litekanyetso tsohle li fapane, ho qala ka e fanoeng, e mong le e mong o fuoa lebokose ka boleng bo itseng. Ebe sephetho se tla kenyelletsa maqiti ao lipampiri tsa bona li sa fokolang. Mohato oa pele, vertex ea pele e fuoa lebokose ka bohlokoa ba 0. Joale lintlha tsohle tse latelang li nkoa, ke hore, tse ka fumanoang ho tsoa mohloling oa vertex. Ke mangolo a ngolisitsoeng ao bohlokoa ba bona bo hlalosoang e le palo ea mohloli le boima ba tsela. Ho tloha lintlheng tsa mohato o latelang, o khethiloe o nang le bohlokoa bo fokolang ka ho fetisisa ba letšoao, mme litekanyetso tsohle tseo li ka tšeloang ho tsona ntle le ho sebelisa li-vertices li ntse li ithutoa. Ntho e ncha ea lebokose e hlalosoa, e lekanang le letšoao la vertex ea mohloli hammoho le boima ba tsela. Haeba phaello e hlahisoang e ka tlaase ho lebokose la vertex, joale letšoao lea fetoha. Ho seng joalo, boleng ba pele bo sala. Tabeng ena, ka karolong e fapaneng, e leng boholo ba eona bo lekanang le palo ea lihlopha tsa graph, phello ea ts'ebetso e bolokehile, moo tsela e behiloeng teng. Ho kenya ts'ebetsong mokhoa o kang algorithm ea Dijkstra, Pascal o fana ka lisebelisoa tse bonolo haholo. Algorithm e na le monyetla oo e ka o sebelisang habonolo e le motheo oa lenaneo le nang le boholo bo fokolang. Mehlala ea lihlahisoa tse joalo tsa software li fumaneha habonolo Inthaneteng.

Mekhoa e fapaneng e ka sebelisoa ho rarolla bothata ba ho fumana tsela e nepahetseng. Bakeng sa tharollo e kang algorithm ea Dijkstra, Delphi e tla iketsetsa foromo e loketseng ea ho kenya data ea pele le ho hlahisa liphello tsa ho qetela.