Dijkstra si algọridim na ya, mmejuputa iwu

E nwere a iche iche ebe a na-akpọ eserese ozizi na mgbakọ na mwepụ na kọmputa sayensị. Dị ka akụkụ nke ya set na-edozi iche iche nsogbu, dị ka na-achọta nke kasị nso ụzọ n'etiti vertices. Otu na-ahụkarị n'etiti mathematicians ụzọ idozi nsogbu a dịwo anya a Dijkstra si algọridim.

Gịnị bụ a mgbakọ na mwepụ eserese

Ọ na-kweere na echiche nke eserese e tinyere n'ime eji na nke iri na asatọ na narị afọ Leonardom Eylerom. Ọ bụ ya na-mara ọkwa na Nwa na ngwọta nke otu n'ime classic nsogbu a Ozizi - asaa àkwà mmiri nke Königsberg. Iji kọwaa ihe nke a ozizi na-eji nke a ntụnyere dị ka ije n'etiti dị iche iche n'obodo. Mgbe ahụ eserese na ụgbọelu ga-ihe dum ụzọ esereese, ebe vertices ibu kpọmkwem ihe (e.g., n'obodo), na n'ọnụ - ụzọ si onye vertex ọzọ (analọg ụzọ n'etiti obodo). Dijkstra si algọridim, na mgbakwunye na ụzọ ndị ọzọ, nwere ike inye a ngwọta a nke.

Ịchọta nke kasị nso ụzọ

Otu n'ime ndị nkịtị ihe aga-eme nke eserese Ozizi bụ onye na nke gị mkpa iji chọpụta na ezigbo eri ụzọ n'etiti abụọ ihe. Ọ bụ ike belata ụgbọelu na mkpebi nke eserese nke vertices - n'obodo - ibe ọgịrịga, nke bụ a ga-ekwe omume ụzọ. Onye ọ bụla ụzọ nwere ya n'ogologo, ya mere, ije na ya ga na-eji ego. A ego bụ Ẹkot arọ nke n'ọnụ na eserese. Mgbe nsogbu na omume nwere ike chepụtara dị ka ndị a: otú kpuchie ụzọ site na otu obodo ọzọ, na-nọrọ n'okporo ụzọ kacha nta n'aka.

ụzọ dozie

Iji dozie nsogbu a, anyị na e mepụtakwara site ụfọdụ algọridim na aghọwo a maara na nkà mmụta sayensị na ụwa. Ka ihe atụ, Floyd algọridim - Uorshella, Ford - Bellman. Kpochapụwo ụzọ ịchọta ihe ngwọta na-Dijkstra si algọridim. Ọ ga-eji na dara nha (mara arọ nke ọ bụla onu) nke eserese, na itughari. Iji chọta ndị kacha ụzọ ị ga-eme ọtụtụ nzọụkwụ.

Dijkstra si algọridim

N'ókè nke usoro a dabeere n'eziokwu na niile vertices nke na-eri, na-amalite na a nyere, nke ọ bụla mkpado na-kenyere a ụfọdụ uru. Mgbe ahụ n'ihi ga-agụnye vertices onye kpọọ bụ ntakiri. On top nke mbụ mbụ nzọụkwụ ga-akpado na a uru nke 0. Mgbe ahụ, ndị a niile ọnụ ọnụ na-atụle, ya bụ, ndị na pụrụ ruru si iyi. Ha na-kpọrọ, uru nke na-kpebisiri ike dị ka nchikota nke ndị isi koodu na ibu ibu nke ụzọ. Site n'elu nzọụkwụ ọzọ, họrọ onye nwere kasị nta uru nke labelụ ma mụọ niile vertices na na site na ya na anyị nwere ike ịga na-enweghị iji n'etiti ọnụ. Dee a ọhụrụ labelụ hà labelụ n'elu - iyi koodu plus arọ nke ụzọ. Ọ bụrụ na uru bụ obere karịa n'elu labelụ labelụ gbanwere. Ma ọ bụghị ya, ọ na-anọgide na mbụ uru. N'otu oge ahụ na a iche iche n'usoro, onye akụkụ bụ hà ọnụ ọgụgụ nke vertices, ọ na-echekwa n'ihi nke njikarịcha, nke na kpebisiri ụzọ. Mejuputa a usoro dị ka Dijkstra si algọridim, onwa awade a nnọọ adaba n'aka. The algọridim nwere uru na ya pụrụ n'ụzọ dị mfe ịbụ ihe ndabere maka usoro ihe omume nke nwere a obere size. Ihe Nlereanya nke ndị dị otú ahụ software ngwaahịa mfe na Internet.

Dle ngwọta dị iche iche ngwaọrụ i nwere ike iji ọrụ iji chọta ezigbo ụzọ. Ihe ngwọta dị otú ahụ dị ka Dijkstra si algọridim, Delphi ga-ike adaba ụdị nke visual data ọsọ ọsọ na-mmepụta ikpeazụ N'ihi.