Dijkstra se algoritme en die implementering daarvan

Daar is 'n aparte area genoem grafiekteorie in wiskunde en rekenaarwetenskap. As deel van sy versameling en om verskeie probleme, soos om die kortste pad tussen die hoekpunte op te los. Een algemeen onder wiskundiges maniere van die oplossing van hierdie probleem is al lank 'n Dijkstra se algoritme.

Wat is 'n wiskundige grafiek

Daar word geglo dat die idee van die grafiek in die agtiende eeu Leonardom Eylerom in gebruik gestel. Dit was hy wat die formulering en oplossing van een van die klassieke probleme van hierdie teorie aangekondig - die sewe brûe van Königsberg. Ten einde die doel van hierdie teorie te verduidelik gebruik dikwels hierdie analogie as beweging tussen verskillende stede. die pad van een hoekpunt na 'n ander ( 'n analoog van die pad tussen die stede) - dan die grafiek op die vliegtuig sal 'n hele skema van roetes, waar die toppe sal wees spesifieke items (bv stad), en ribbes wees. Dijkstra se algoritme, bykomend tot ander metodes, kan 'n oplossing vir hierdie probleem te verskaf.

Dit vind van die kortste pad

Een van die algemene take van grafiekteorie is een waarin jy nodig het om die optimale koste pad bepaal tussen twee punte. Dit is moontlik om die vliegtuig te verminder om die besluit van die grafiek waarin die hoekpunte - stede - met mekaar verbind ribbes, wat 'n moontlike pad. Elke pad het sy eie lengte, dus, reis op dit sal hê om 'n bietjie geld te spandeer. Hierdie bedrag is gelykstaande aan die gewig van die kante in die grafiek. hoe om die weg te baan van die een stad na die ander, word bestee aan die minimum pad beteken: dan is die probleem in die praktyk kan soos volg geformuleer word.

maniere om op te los

Om hierdie probleem wat ons het is uitgevind deur 'n paar algoritmes wat wyd in die wetenskaplike wêreld bekend het op te los. Byvoorbeeld, Floyd algoritme - Uorshella, Ford - Bellman. Die klassieke manier om oplossings is ook Dijkstra se algoritme. Dit kan gebruik word vir geweeg (bekend gewig van elke rand) van die grafiek, en om te verdun. Om die uiteindelike manier moet jy 'n paar stappe te doen kry.

Dijkstra se algoritme

Die punt van hierdie metode lê in die feit dat al die hoekpunte van koste, wat begin met 'n gegewe, waarin elke tag 'n sekere waarde is opgedra. Dan sal die resultaat sluit die hoekpunte wie se etikette is minimaal. In die eerste stap is die aanvanklike toppunt n etiket met 'n waarde van 0 toegeken Dan beskou ons al die volgende pieke, dit wil sê diegene wat bereik kan word uit die bron. Hulle is gemerk, waarvan die waarde word bepaal as die som van die bron-kode en gewig van die paaie. Van die top van die volgende stap, kies die een wat die kleinste waarde van die etiket het, en bestudeer al die hoekpunte in wat daaruit kan ons gaan sonder die gebruik van die intermediêre nodusse. Spesifiseer 'n nuwe etiket gelyk aan die etiket tops - bronkode plus die gewig van die pad. As die waarde minder as die top-etiket is, is die etiket verander. Anders, bly dit die oorspronklike waarde. Terselfdertyd in 'n aparte skikking, wie se dimensie is gelyk aan die aantal hoekpunte, dit slaan die gevolg van optimalisering, waarin en vasberade manier. 'N metode te implementeer soos Dijkstra se algoritme, Pascal bied 'n baie maklike manier. Die algoritme het die voordeel dat dit maklik die basis vir 'n program wat 'n klein grootte het kan wees. Voorbeelde van sulke sagteware produkte maklik om te vind op die internet.

DLE oplossings verskillende tools wat jy kan die taak gebruik om die optimale pad te vind. Vir oplossings soos Dijkstra se algoritme, sal Delphi gerieflike vorm van visuele data toevoer en afvoer die finale uitslag te skep.