Algoritmu Dijkstra u l-implimentazzjoni tagħha

Hemm żona separata msejħa teorija graff fil-matematika u x-xjenza tal-kompjuter. Bħala parti mill-set tagħha u biex isolvu problemi varji, bħall-konstatazzjoni tal-iqsar rotta bejn il-punti. Wieħed komuni fost matematiċi modi biex tissolva din il-problema ilha algoritmu ta Dijkstra s.

X'inhu graff matematika

Huwa maħsub li l-kunċett tal-graff tpoġġa fis-użu fis-seklu tmintax Leonardom Eylerom. Kien hu li ħabbar il-formulazzjoni u s-soluzzjoni ta 'wieħed mill-problemi klassiċi ta' din it-teorija --seba 'pontijiet ta' Königsberg. Sabiex tispjega l-għan ta 'din it-teorija spiss jużaw din l-analoġija kif moviment bejn bliet differenti. Imbagħad il-graff fuq il-pjan se jkun dijagramma kollu rotta, fejn vertiċi isiru partiti speċifiċi (eż, l-ibliet), u t-truf - passaġġ minn vertiċi wieħed għall-ieħor (triq Analog bejn l-ibliet). algoritmu Dijkstra, magħdud ma 'metodi oħra, jistgħu jipprovdu soluzzjoni għal din il-kwistjoni.

Sib l-passaġġ iqsar

Wieħed mill-kompiti komuni ta 'teorija graff huwa wieħed fejn għandek bżonn biex jiddeterminaw il-passaġġ spiża ottimali bejn żewġ punti. Huwa possibbli li jitnaqqsu l-pjan għad-deċiżjoni tal-graff li fih il-punti - ibliet - huma kustilji interkonnessi, li hija triq possibbli. Kull triq għandha tul tagħha stess, għalhekk, l-ivvjaġġar fuqha se jkollu jonfoq xi flus. Dan l-ammont huwa ekwivalenti għall-piż tat-truf fil-graff. Allura l-problema fil-prattika jistgħu jiġu fformulati kif ġej: kif biex iwittu t-triq minn belt għall-oħra, li jintefqu fuq il-mezzi minimi triq.

modi biex tissolva

Biex issolvi din il-problema aħna ġew ivvintati minn xi algoritmi li saru magħrufa fid-dinja xjentifika. Per eżempju, Floyd algoritmu - Uorshella, Ford - Bellman. Il-mod klassiku ta jinstabu soluzzjonijiet hija wkoll algoritmu Dijkstra s. Hija tista 'tintuża għall peżati (piż magħruf ta' kull tarf) tal-graff, u biex jiddilwixxu. Biex issib l-mod aħħari li inti trid tagħmel diversi passi.

algoritmu Dijkstra s

Il-punt ta 'dan il-metodu tinsab fil-fatt li l-punti ta' spejjeż, li jibda bil mogħtija, fejn kull tikketta huwa assenjat ċertu valur. Allura r-riżultat se jinkludi l-punti li t-tikketti huma minimi. Fuq il-quċċata ta 'l-ewwel pass inizjali se jiġu ttikkettati b'valur ta 0. Imbagħad, kollha tal-qċaċet li ġejjin huma meqjusa, jiġifieri, dawk li jista' jintlaħaq mis-sors. Dawn huma ttikkettjati, il-valur tiegħu huwa ddeterminat bħala s-somma tal-kodiċi sors u l-piż tal-mogħdijiet. Mill-quċċata tal-pass li jmiss, tagħżel il-wieħed li għandu l-iżgħar valur tat-tikketta, u studjat l-vertiċi li minnha nistgħu mmorru mingħajr l-użu l-lymph intermedji. Speċifika tikketta ġdida ugwali għall-uċuħ tikketta - source code flimkien mal-piż tal-mod. Jekk il-valur huwa inqas mill-tikketta ta 'fuq, it-tikketta tinbidel. Inkella, jibqa l-valur oriġinali. Fl-istess ħin fil-firxa separat, li l dimensjoni hija ugwali għan-numru ta 'vertiċi, huwa jaħżen ir-riżultat tal-ottimizzazzjoni, li fihom u b'mod determinat. Biex timplimenta metodu bħal algoritmu Dijkstra, il Pascal joffri mezz konvenjenti ħafna. L-algoritmu għandha l-vantaġġ li tista 'faċilment tkun il-bażi għal programm li għandu daqs żgħir. Eżempji ta 'tali prodotti ta' softwer faċli li ssib fuq l-Internet.

soluzzjonijiet dle għodod differenti tista 'tuża l-kompitu biex isibu t-triq ottimali. Għal soluzzjonijiet bħal algoritmu Dijkstra, il Delphi se toħloq forma konvenjenti ta 'input tad-data viżwali u joħroġ il-riżultat finali.