Doumeritm

Tupu ịmalite ịgụ isiokwu a, anyị na-adụ gị ọdụ ka ị mata ihe ị na-akọ banyere ụzọ dị ka Bellman - ford algorithm.

Mgbakwunye mmelite algorithm (gbanyụọ mmelite algorithm -Ihe) bụ otu n'ime algorithms abụọ a tụlere ebe a na mbụ ezubere maka mmejuputa ya na netwọkụ kesara. Ọ bụ ihe pụrụ iche na na ọ na-ewepụkwa ozi banyere mmezu na Topology dị na Nkwado nke Algorithm. Algorithms ndị ọzọ tụlere ebe a ịhapụ iwepụ ozi na ezi uche nke mmejuputa nke protocol, ma echebara echiche a nke ọrụ algorithm n'onwe ya.

Ka ọ na-erule 1993, a na-emejuputa bellman-ford na dijkstrated algorithms n'ọtụtụ usoro. Ahụmahụ ndị a nwetara n'ihi mmejuputa mmalite ndị a na-ebute "nke abụọ" nke nnyocha na nsogbu nke ngbanwe netwọọk, nke dugara n'ọdịdị nke ụzọ vector na-agbanwe.

Ebe ọ bụ na a na-emepụta Dual dị ka algorithm kesara, ọ kachasị mma ịkọwa ọrụ ya na netwọkụ. Maka ebumnuche a, ejiri onu ogugu 8 na 9. Ka a kọwapụta ihe atụ a, a ga-ahazi ihe nlereanya atọ, wee gbanwee mgbanwe na steeti ebe ị na-aga. N'emepụta nke mbụ, a ga-atụle ikpe ahụ mgbe e nwere ụzọ ọzọ, mana enweghị onye agbata obi na-adịghị ala ala, nke abụọ ga-atụle ihe ahụ mgbe ndị agbata obi ọzọ dị na ndagide.

Na eserese 8, na-amụ ihe d site na echiche nke:

1. A na-amụta ụzọ abụọ iji d:

1. A gaghị amata ụzọ nke B, n'ihi na b na-eji onye na-anọchi ya:
2. A na-atụnyere ụzọ dịnụ ma họrọ ụzọ dị mkpụmkpụ na-enweghị loops:
3. Na-enyocha ụzọ ndị fọdụrụ ụzọ iji chọpụta ma ọ nwere onye ọ bụla n'ime ndị agbata obi na-agbada:

A maara nke a n'ihi na C kwupụtara ụzọ iji nweta ihe na-eme ka ọ dị afọ 3.

Na-edobe ihe metric nke mpaghara C na tebụl Toplogy.

N'ihi ya, a maara uru mpaghara na C na uru mpaghara na A.

1. 3 (Akwụ ụgwọ na C) = 3 (na-eri na a), yabụ ụzọ a nwere ike ịbụ loop, yabụ, C anaghị emeju ọnọdụ ahụ ga-eme. CE na-edeghị ndị agbata obi.

A na-akpọ ndị agbata obi ndị agbata obi na-eme ihe ndị ọzọ nwere ike ịbịarute. Ka e were ya na ọwa [a, H] anaghị arụ ọrụ. Dual anaghị adabere na mmelite oge, yabụ na enweghị ike ichere maka mmelite ọzọ nwere ozi a pụrụ ịdabere na ya. Kama, a ga-agbaso ụzọ ọzọ. N'ihi ya, nke a bụ usoro nchọpụta nke ụzọ ọzọ. Ọ bụrụ na ọwa [a, H] adịghị arụ ọrụ, na-atụle naanị D:

1. Na-enyocha tebụl mpaghara gị maka ndị ga-anọchi anya ndị agbata obi (ndị na-agbadata).
2. Enweghị ndị ga-anọchi ga-enwerịrị ndị ga-anọchi ya, yabụ a ga-achọta ụzọ ọzọ na-enweghị loops na d (ma ọ bụrụ na ọ dị).
3. A na-ezigara onye agbata obi ọ bụla iji chọpụta ma enwere ụzọ ọzọ ọ bụla na-enweghị loops na D.
4. Na c:
5. Na B:
6. Azịza azịza ndị a:

Na eserese nke 9, a ga-eji ebe a na-aga na H ruo E. A ga-eji ya eme ihe nke abụọ.

N'ime ihe atụ a, enwere onye ga-aga n'ihu na onye agbata obi (onye agbata obi na-agbadata).

Mụọ D site na isi nke a:

1. A na-amụta ụzọ abụọ iji d:
2. A gaghị amata ụzọ ọ bụla site na b:
3. A na-atụnyere ụzọ dịnụ ma họrọ ụzọ dị mkpụmkpụ na-enweghị loops:
4. Na-enyocha ụzọ ndị fọdụrụ ụzọ iji chọpụta ma ọ nwere onye ọ bụla n'ime ndị agbata obi na-agbada:

Ọ bụrụ na ọwa [a, C] anaghị arụ ọrụ, na-atụle otu:

1. Na-enyocha tebụl ụlọ ọrụ dị na mpaghara ya maka onye na-eme ka onye nwere ike nwee ike.
2. Ọ ga - ekwe omume ịnọ na h.
3. Tebụl na-agbanwe agbanwe na-agbanwe agbanwe na h dị ka ụzọ kachasị mma.
4. A na-ezigara ndị agbata obi ya mmelite, na-achọpụta na ọnụ ahịa ya nke mmezu D agbanweela site na 3 ruo 4.

Dị ka ị pụrụ ịhụ, nhazi mgbe enwere onye ga-eme ka onye na-elekọta ya, ngwa ngwa ngwa ngwa ma dị mfe karịa ma ọ naghị eme ya. Na netwọk ebe a na-eji doctol na-eji doocol na-eji doal (ọkachasị, eigp), otu n'ime ebumnuche ndị isi ga-amachi ọkwa arịrịọ ọ bụla e mepụtara na enweghị onye ga-enwe onye na-emeju. Mpaghara arịrịọ bụ isi ihe bụ isi ihe bụ isi ihe bụ abụọ algorithm emechara ngwa ngwa ma, yabụ, kedu ngwa ngwa ngwa ngwa.

Ọgụgụ 10 na-egosi nnukwu igwe eji eme ihe.

Ihe gụnyere na ụzọ na-akawanye njọ (ngọdara nke ụzọ) nwere ike ịbụ:

• Ọdịda nke ọwa jikọrọ ma ọ bụ agbataobi
• Inweta mmelite maka uzo nwere meti
• Na-enweta ajụjụ sitere na onye na-elekọta ụlọ ugbu a
• Na-enweta ụzọ ọhụụ site n'aka onye agbata obi
• A hụrụ onye agbata obi ọhụrụ, yana ụzọ nke ọ ga - esi nweta
• Na-arịọ arịrịọ maka ndị agbata obi mgbe ụzọ na-akawanye njọ