Algoritmul dextra și implementarea acestuia

În știința matematică și informatică există o direcție separată, numită teoria grafurilor. În cadrul său, sunt stabilite și rezolvate diverse sarcini, de exemplu, despre găsirea celei mai scurte căi între vârfuri. Una dintre metodele cele mai comune pentru rezolvarea acestei probleme în rândul matematicienilor a fost mult timp algoritmul Dijkstra.

Ce este un grafic matematic

Se crede că conceptul graficului a fost introdus în secolul al XVIII-lea de Leonard Euler. El a exprimat formularea și soluționarea uneia dintre problemele clasice ale acestei teorii - despre cele șapte poduri ale lui Koenigsberg. Pentru a explica obiectul acestei teorii, folosesc cel mai adesea o astfel de analogie ca mișcarea între diferitele orașe. Apoi, graficul din avion va reprezenta întreaga schemă de rute, unde vârfurile vor fi puncte specifice (de exemplu, orașe), iar marginile - calea de la un vârf la altul (analog celui dintre orașele). Algoritmul lui Dijkstra, pe lângă alte metode, poate da o soluție la această întrebare.

Găsirea celei mai scurte căi

Una dintre sarcinile standard teoria graficelor este cea în care este necesar să se determine calea optimă a costurilor între două puncte. Acesta poate fi redus pe un avion până la soluția unui grafic în care vertexele-orașe - sunt interconectate de margini, care reprezintă drumuri posibile. Și fiecare drum are propria lungime, prin urmare, de a călători prin acesta va trebui să cheltuiască anumite fonduri. Această sumă este echivalentă cu greutatea unei margini din grafic. Apoi, problema în practică poate fi formulată după cum urmează: cum să deschidem drumul dintr-un oraș în altul, să cheltuiți pe drum un minim de fonduri.

moduri de a rezolva

Pentru a rezolva această problemă, au fost inventați niște algoritmi, care au devenit cunoscuți în lumea științifică. De exemplu, algoritmul Floyd - Warshell, Ford - Bellman. Algoritmul Dijkstra este, de asemenea, un mod clasic de găsire a soluției. De asemenea, poate fi folosit pentru ponderare (greutatea fiecărei margini este cunoscută) grafic și pentru rar. Pentru a găsi calea finală, trebuie să faceți câțiva pași.

Algoritmul Dijkstra

Semnificația acestei metode este că toate nodurile sunt ocolite, începând de la cel dat, fiecăruia li se dă o etichetă cu o anumită valoare. Apoi rezultatul va include acele noduri ale căror etichete sunt minime. Pe partea de sus a primului pas inițial va fi etichetat cu o valoare de 0. Apoi, sunt luate în considerare toate din următoarele vârfuri, adică, cei care se poate ajunge de la sursa. Acestea sunt atribuite etichete a căror valoare este definită ca suma sursei și greutatea căii. Din partea de sus a pasul următor, selectați cel care are cea mai mică valoare a etichetei, și a studiat toate nodurile din care de la ea putem merge fără a utiliza nodurile intermediare. Se definește o nouă valoare a etichetei, egală cu eticheta vertexului sursă plus greutatea căii. Dacă valoarea rezultată este mai mică decât eticheta de vârf, atunci eticheta se modifică. În caz contrar, valoarea inițială rămâne. În același timp, într-o matrice separată, a cărei dimensiune este egal cu numărul de noduri, se stochează rezultatul de optimizare, în care și mod hotărât. Pentru a implementa o astfel de metodă ca algoritmul Dijkstra, Pascal oferă instrumente foarte convenabile. Algoritmul are avantajul că poate fi folosit cu ușurință ca bază a unui program care are o dimensiune mică. Exemple de astfel de produse software sunt ușor de găsit pe Internet.

Pentru a rezolva problema găsirii căii optime, pot fi utilizate diferite mijloace. Pentru o astfel de soluție ca algoritmul lui Dijkstra, Delphi va crea o formă convenabilă vizuală de intrare a datelor inițiale și de ieșire a rezultatului final.