Алгоритъм на Дейкстра и неговото прилагане

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

Какво е математическа графика

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

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

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

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

За да се реши този проблем, ние са били изобретени от някои алгоритми, които са станали широко известни в света на науката. Например, Флойд алгоритъм - Uorshella, Ford - Белман. Класическият начин за намирането на решения също е Алгоритъм на Дейкстра. Тя може да се използва за претеглените (известен тегло на всеки край) на графиката, и да се разреди. За да намерите най-добрият начин, трябва да направите няколко стъпки.

Алгоритъм на Дейкстра

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

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