Алгоритъмът dextra и неговото изпълнение

В математиката и информатиката има отделна посока, наречена теорията на графиките. В своята рамка са зададени и решавани различни задачи, например, за намиране на най-краткия път между върховете. Един от най-разпространените методи за решаване на този проблем сред математиците отдавна е алгоритъмът Dijkstra.

Какво представлява математическа графика

Смята се, че концепцията за графиката е въведена през осемнадесети век от Леонард Ойлер. Той беше този, който изрази формулировката и решаването на един от класическите проблеми на тази теория - за седемте моста на Koenigsberg. За да обяснят предмета на тази теория, най-често използват такава аналогия като движението между различните градове. Тогава графиката в равнината ще представлява цялата схема на маршрутите, където върховете ще бъдат специфични точки (например градове), а краищата - пътят от един връх на друг (аналогичен на пътя между градовете). Алгоритъмът на Dijkstra, в допълнение към други методи, може да даде решение на този въпрос.

Намиране на най-краткия път

Една от стандартните задачи теория на графиките е тази, в която е необходимо да се определи разходната оптимална пътека между две точки. Тя може да бъде намалена в равнината до решаването на графика, в която върховете - градове - са свързани помежду си с ръбове, които представляват възможни пътища. И всеки път има своя собствена дължина, следователно, за да пътувате през него ще трябва да похарчите определени средства. Тази сума е равна на теглото на ръба на графиката. Тогава проблемът на практика може да бъде формулиран по следния начин: как да проправи път от един град в друг, да похарчи на пътя минимални средства.

начини за решаване на

За да се реши този проблем, бяха изобретени някои алгоритми, които станаха широко известни в научния свят. Например алгоритъмът Floyd - Warshell, Ford - Bellman. Алгоритъмът Dijkstra също е класически начин за намиране на решението. Тя може да се използва и за претеглена (теглото на всеки ръб е известно) графика, и за слабо. За да намерите последния път, трябва да направите няколко крачки.

Дижкстра алгоритъм

Значението на този метод е, че всички върхове се заобикалят, започвайки от дадения, всеки от които получава етикет с определена стойност. Тогава резултатът ще включва тези върхове, чиито етикети са минимални. В първата стъпка, на първоначалния връх е присвоен етикет със стойност 0. След това се вземат предвид всички следващи върхове, т.е. тези, които могат да бъдат достъпни от изходния връх. На тях се приписват етикети, чиято стойност се определя като сумата на източника и теглото на пътя. От върховете на следващата стъпка се избира една, която има най-малката стойност на етикета, и се изследват всички върхове, на които може да се пресекат, без да се използват междинни върхове. Създадена е нова стойност на етикета, равна на етикета на изходния връх плюс теглото на пътя. Ако резултантната стойност е по-малка от етикета на върха, тогава етикетът се променя. В противен случай остава първоначалната стойност. В този случай в отделен масив, чийто размер е равен на броя върхове на графиката, се запазва резултатът от оптимизацията, по който се определя пътят. За да приложи такъв метод като алгоритъма Dijkstra, Pascal предлага много удобни инструменти. Алгоритъмът има предимството, че може лесно да се използва като основа на програма с малък размер. Примери за такива софтуерни продукти са лесни за намиране в интернет.

За да се реши проблемът с намирането на оптималния път, могат да се използват различни средства. За такова решение като алгоритъма на Dijkstra, Delphi ще създаде визуална удобна форма на въвеждане на първоначалните данни и изхода на крайния резултат.