Den Dextra-Algorithmus a senger Ëmsetzung

An der Mathematik a Informatik ass et eng eenzeg Richtung, déi d'Diagramm vu Grafiken genannt gëtt. Am Kader sinn verschidden Aufgaben opgestallt a geléist ginn, zum Beispill, de kuerstste Wee tëscht de Scheiwen ze fannen. Ee vun de bekanntsten Methoden fir dës Problematik mat Mathematiker ze léisen ass scho laang den Dijkstra Algorithmus.

Wat ass en mathematesche Graf

Et gëtt ugeholl datt d'Konzept vum Graf dem 18. Joerhonnert vum Leonard Euler agefouert gouf. Et war deen, deen d'Formuléierung an d'Léisung vun enger vun de klassesche Problemer vun dëser Theorie huet - iwwert déi siwe Brécke vu Koenigsberg. Fir d'Saach vun dëser Theorie z'erklären, sinn am meeschten eng ähnlech Analogie wéi d'Bewegung tëscht verschiddene Stied. Dann de Graaff op der Flieger representéiert d'ganz Schema vun de Strecken, wou d'Heiser sinn spezifesch Punkten (zum Beispill Stied), an d'Kante sinn d'Weeër vun engem Scheff an engem aneren (analog zu der Strooss tëscht Stied). Den Algorithmus vum Dijkstra, zousätzlech zu anere Methoden, kann eng Léisung fir dës Fro ginn.

Den kuerstste Wee fannen

Ee vun de gemeinsam Aufgaben vun Offlaachung Theorie ass een an deem dir de optimal kascht Wee tëscht zwee Punkten ze bestëmmen brauchen. Et kann op der Fläch op d'Léisung vum Graaff reduzéiert ginn, an deem d'Eckwäerter - d'Stied - mat Rippen verbonne sinn, déi méiglech Weeër representéieren. A all Strooss huet eng eegent Längt, dofir, fir duerch dës Rees ze reesen, mussen bestëmmte Fongen ausginn. Dës Zomm ass entspriechend dem Gewiicht vun enger Rand op der Grafik. Duerfir kann d'Problem an der Praxis wéi folgend formuléiert ginn: Wéi kann de Wee vun enger Stad an en anert kréien, fir op der Strooss e Minimum vu Fongen ze verbréngen.

Léisungen

Fir dëst Problem ze léisen, sinn e puer Algorithmus erfonnt ginn, déi allgemeng an der wëssenschaftlecher Welt bekannt waren. Zum Beispill, de Floyd-Warshell Algorithmus, den Ford-Bellman Algorithmus. De Dijkstra Algorithmus ass och e klassesche Wee fir d'Léisung ze fannen. Et kann och benotzt ginn fir gewichtt (bekannten Gewiicht vun all Rand) Graf, a fir spar. Fir den definitiven Wee ze fannen, musst Dir e puer Schrëtt maachen.

Den Algorithmus vum Dijkstra

D'Bedeitung vun dëser Methode ass datt all Eckschrëften ëmgaang sinn, mat dem gefeiertene Begleedung, all e Label mat engem gewësse Wäert kritt. Dann wäert d'Resultat och dës Schecken, deenen hir Labels minimal sinn. Am éischte Schrëtt ass de ursprénglechen Eckpunkt e Label mat engem Wäert vun 0 zugewielt ginn. All ville folgende Eckpunkte gi berücksichtegt, dh déi, déi vu de Quelltexter ergräifen kënnen. Si ginn Etiketten déi hir Wäert definéiert sinn als d'Zomme vun der Quell an de Gewiicht vum Wee. Aus den Eckpunkten vum nächste Schrëtt ass ee gewielt, deen dee klengste Wäert vun der Etikett huet, an all déi Scheiwen, op déi hien kann ouni Duerchbroch duerch d'Mëttele vu vertrëtt ginn, studéiert. En neie Wäert vun der Etikett gëtt definéiert, gläich wéi d'Etikett vum Quellentoex plus de Gewiicht vum Wee. Wann de entsteetende Wäert méi kleng ass wéi den Eckpunkt, dann ännert d'Etikett. Sinn den urspréngleche Wäert. An dësem Fall ass an engem separaten Array, deem seng Dimensioun gläich ass wéi d'Zuelen vun der Gréisst vun der Grafik, d'Resultat vun der Optimiséierung gëtt behalen, sou wéi de Wee befaasst gëtt. Fir dës Method wéi den Dijkstra Algorithmus ze realiséieren, proposéiert Pascal ganz praktesch Tools. De Algorithmus huet den Avantage datt et einfach als Basis vun engem Programm mat enger gerénger Gréisst benotzt gëtt. Beispiller vu sou Softwareprodukter kënnen einfach am Internet fannen.

Verschidde Moyene kënnen benotzt ginn fir de Problem ze léisen fir den optimalen Wee ze fannen. Fir eng Léisung, wéi den Algorithmus vum Dijkstra, mécht Delphi e visuell bequem Form fir d'Input vun der Originaler ze maachen an d'Resultat auszeginn.