
surballeyude algoritam

saidhaanthika computer shaasthrathilum network rootingilum, surballinte algoritam negatteevu allatha bharamullah directed graphil rund disjoyint pathakal kandethunnathinulla oru algorithamaanu, angane rund paathakalum ore jody konukale bandhippikkukayum kuranjathu motham neelavum undaayirikkukayum cheiyunnu. joonn dablyu aanu algoritam vibhavanam cheythath. surballe 1974ll prasidheekarikkappettathum. surballeyude algoritam oru vazhi kandethunnathinum graph arikukalude bharam parishkkarikkunathinum pinneedu dijkstrayude algoritam randaam thavana pravarthippikkunnathinum dijkstrayude algoritam upayogikkuka ennathaanu. eee rund paathakalum samyojippichum, paathakalaal ethir dishakaliloode sanjarikkunna arikukal upekshichu, sheshikkunna arikukal upayogichu rund paathakalum roopappeduthi auttputtaayi madangiyaanu algoritam roopappedunnathu.
bhaarangalilekkulla parishkkaranam jonsante algorithathile bharam parishkkaranatthinu samaanamaan, koodaathe bhaaratthinte negatteevu allaathathine samrakshikkukayum athesamayam dijkstrayude algorithathinte randaamathe udaaharanathe sariyaaya randaamathe paatha kandethaan anuvadikkukayum cheiyunnu.
kuranja bharamullah rund bhinna pathakal kandethunnathinulla prashnam minimum koost phloo prashnatthinte oru prathyeka kesai kaanaan kazhiyum, eee saahacharyathil "phloo" yude rund yoonittukalum nodukalkku yoonit "kappaasittiyum" undu. ettavum cheria vardhana paathayiloode saadhyamaaya paramavadhi ozhukk aavarthichu thallunna minimum koost phloo algorithathinte oru prathyeka kesai surballeyude algoritam kaanaan kazhiyum.
surballinte algoritam kandethiya aadya paatha prarambha (poojyam) ozhukkinulla ettavum cheria vardhana paathayaan, surballinte algoritam kandethiya randaamathe paatha aadya paathayiloode oru yoonit ozhukk thalliya sesham avasheshikkunna sheshikkunna graphinulla ettavum cheria vardhana paathayaan.
nirvachanangal.
vertex settum edju settum (chithram eiii) ulla oru waited directed graph ayirikkatte; oru niyukta uravida vertex ayirikkatte, oru niyukta lakshyasthana vertex ayirikkatte. sheershakam muthal sheershakam vareyulla oro attatthinum negatteevu allatha vila undayirikkatte.
(chithram sii) verukalulla ettavum cheria paathayile vrukshathil sheershakathil ninnu sheershakathilekkulla ettavum cheria paathayude vilayayi nirvachikkuka.
kurippu node vertex palappozhum parasparam upayogikkappedunnu.
algoritam.
surballeyude algoritam inipparayunna gattangal nirvahikkunnu
udaaharanam.
surballeyude algoritam "a" muthal "f" vareyulla ettavum cheria jody bhinna pathakal engane kandethunnuvennu inipparayunna udaaharanam kaanikkunnu.
chithram a oru bharamullah graph "g" chithreekarikkunnu.
a" muthal "f" ("a"-"b"-"d"-"f") vareyulla ettavum cheria paatha "p" 1 kanakkakkunnu.
a" yill veroonniya ettavum cheria paathu trea "t", "a" ll ninnu oro sheershakathilekkum () kanakkakkiya doorangal enniva chithram c chithreekarikkunnu.
oro attatthinteyum update cheytha chelavum paathayude arikukal "p" 1 vipareethavum ulla sheshikkunna graph "gt" chithram kaanikkunnu.
chithram e avasheshikkunna graph "gt" ("a"-"c"-"d"-"b"-"e"-"f") ll "p" 2 enna paatha kanakkakkunnu.
chithram f "p" 1, "p" 2 ennee paathakale chithreekarikkunnu.
p" 1, "p" 2 ennee paathakalude arikukal samyojippichu rund paathakalkkum ("b"-"d") edayilulla pothuvaaya vipareeta arikukal upekshichukondu chithram g ettavum cheria jody bhinna pathakal kandethunnu. thalphalamaayi, namukk rund ettavum cheria jody bhinna pathakal ("a"-"b"-"e"-"f"), ("a"-"c"-"d"-"f") labhikkunnu.
krithyatha.
parishkkaricha bhaara samvidaanathil ninnu mattethenkilum paathayude bharam yadhaartha graphile bhaarathinu thulyamaanu, mainus. athinaal, parishkkaricha thookkangalkku keezhilulla ettavum cheria rund verthirivukalkk vyathyastha bhaarangalundenkilum yadhaartha graphile ettavum cheria rund paathakalkk thulyamaanu.
rund muthal rund vareyulla motham ozhukkinte alavil minimum koost phloo kandethunnathinulla thudarchayaaya ettavum cheria paathakalude oru prathyeka kesai surballeyude algoritam kaanapedaam. bhaarangalilekkulla maattam eee reethi kandethiya paathakalude kramatthe baadikkilla, avayude bharam maathram. athinaal, thudarchayaaya ettavum cheria paathakalude reethiyude krithyathayil ninnaan algoritam pinthudarunnathu.
vishakalanavum pravartthana samayavum.
eee algorithathinu dijkstra algorithathinte rund aavarthanangal aavasyamaanu. fibonacci koombaarangal upayogichu, rund aavarthanangalum samaya soothravaakyathil nadatthaam, avide formula 2, formula 3 enniva yathaakramam konukaludeyum arikukaludeyum ennamaanu. athinaal, athe samayaparidhi surballinte algorithathinum baadhakamaan.
vyathiyanangal.
mukalil vivarichathupole surballeyude algorithathinte pathipp vichedikkappetta arikukalulla pathakal kandethunnu, pakshe athu shringangal pankidaam. oro sheershakathinum pakaram oru jodi aduthulla sheershakangal upayogichu, yadhaartha sheershakathinte ellah incoming saameepyangalodum koodiyathum, puratthekku pookunna ellah saameepyangalodum koodiyathumaaya ore algoritam upayogichu sheershaka-bhinna pathakal kandethaan kazhiyum. eee parishkaricha graphile rund edju-disjoyint pathakal yadhaartha graphile rund vertex-disjoyint paathakalumayi poruthappedunnu, thirichum, athinaal parishkaricha graphylake surballinte algoritam prayogikkunnathu yadhaartha graphile rund vertex-disjoyint paathakalude nirmmaanathinu kaaranamaakunnu. surballinte yadhaartha 1974 algoritam prashnatthinte vertex-disjoyint pathippinullathaayirunnu, 1984ll surballi, tarjan enniva edju-disjoyint pathippilekku vipuleekarichu.
graafukalile oro sheershakathilekkumulla dooram oresamayam kanakkaakkunna dijkstra algorithathinte parishkaricha pathipp upayogikkunnathiloode, thannirikkunna uravida sheershakathil ninnu graphile matellaa sheershakangalilekkum ulla ettavum cheria jody paathakalude motham dairkhyam dijkstra algorithathinte orotta udaaharanathinu aanupaathikamaaya samayathinullil kandethaanum kazhiyum.
shradhikkuka vibhajanathinte falamaayundaakunna aduthulla konukalude jody incoming muthal outgoing vare seero koost yooni-directional edju vazhi bandhippichirikkunnu. uravida sheershakam maarukayum lakshyasthana sheershakam maarukayum cheiyunnu.

