Алгарытм дейкстры і яго рэалізацыя

У матэматычнай навуцы і інфарматыцы існуе асобны кірунак, званае тэорыяй графаў. У рамках яе ставяцца і вырашаюцца разнастайныя задачы, напрыклад, пра знаходжанне найкарацейшага шляху паміж вяршынямі. Адным з распаўсюджаных сярод матэматыкаў спосабаў вырашэння гэтай задачы даўно ўжо стаў алгарытм Дейкстры.

Што такое матэматычны граф

Лічыцца, што паняцце графа было ўведзена ва ўжытак у васемнаццатым Леанардам Эйлера. Менавіта ён агучыў пастаноўку і рашэнне адной з класічных задач гэтай тэорыі - аб сямі мастах Кенігсберга. Для таго каб растлумачыць аб'ект гэтай тэорыі, часцей за ўсё карыстаюцца такой аналогіяй, як рух паміж рознымі гарадамі. Тады граф на плоскасці будзе ўяўляць сабой усю схему маршрутаў, дзе вяршынямі стануць канкрэтныя пункты (напрыклад, горада), а рэбрамі - шляху з адной вяршыні ў іншую (аналаг дарогі паміж гарадамі). Алгарытм Дейкстры, акрамя іншых спосабаў, можа даць рашэнне гэтага пытання.

Знаходжанне найкарацейшага шляху

Адной з стандартных задач тэорыі графаў з'яўляецца тая, у якой трэба вызначыць аптымальны па выдатках шлях паміж двума кропкамі. Яе можна звесці на плоскасці да вырашэння графа, у якім вяршыні - гарады - звязаныя паміж сабой рэбрамі, што ўяўляюць сабой магчымыя дарогі. Прычым кожная дарога мае сваю даўжыню, такім чынам, на праезд па ёй прыйдзецца выдаткаваць пэўныя сродкі. Гэтая сума эквівалентная вазе рэбры на графе. Тады задачу на практыцы можна сфармуляваць так: як пракласці шлях з аднаго горада ў іншы, каб выдаткаваць на дарогу мінімальныя сродкі.

спосабы рашэння

Для вырашэння гэтай задачы былі прыдуманы некаторыя алгарытмы, якія сталі шырока вядомыя ў навуковым свеце. Напрыклад, алгарытм Флойда - Уоршелла, Форда - Беллмана. Класічным спосабам знаходжання рашэння з'яўляецца таксама алгарытм Дейкстры. Ён можа выкарыстоўвацца і для ўзважанага (вядомы вага кожнага рэбры) графа, і для разрэджанага. Для знаходжання канчатковага шляху трэба прарабіць некалькі крокаў.

алгарытм Дейкстры

Сэнс гэтага спосабу складаецца ў тым, што абыходзяцца ўсе вяршыні, пачынаючы з зададзенай, пры гэтым кожнай прысвойваецца пазнака з некаторым значэннем. Затым у вынік ўвойдуць тыя вяршыні, пазнакі якіх мінімальныя. На першым кроку зыходнай вяршыні прысвойваецца пазнака са значэннем 0. Затым разглядаюцца ўсе наступныя вяршыні, гэта значыць тыя, у якія можна трапіць з крынічнай. Ім прысвойваюцца пазнакі, значэнне якіх вызначаецца як сума зыходніка і вагі шляху. З вяршыняў наступнага кроку выбіраецца тая, што мае найменшае значэнне пазнакі, і вывучаюцца ўсе вяршыні, у якія з яе можна прайсці, не выкарыстоўваючы прамежкавых вяршыняў. Вызначаецца новае значэнне пазнакі, роўнае пазнацы вяршыні - зыходніка плюс вага шляху. Калі атрыманае значэнне менш, чым пазнака вяршыні, то пазнака змяняецца. У адваротным выпадку застаецца зыходнае значэнне. Пры гэтым у асобным масіве, памернасць якога роўная колькасці вяршыняў графа, захоўваецца вынік аптымізацыі, па якім і вызначаецца шлях. Для рэалізацыі такога спосабу, як алгарытм Дейкстры, Pascal прапануе вельмі зручныя сродкі. Алгарытм мае тое перавага, што лёгка можа быць пакладзены ў аснову праграмы, якая мае невялікі памер. Прыклады такіх праграмных прадуктаў лёгка знайсці ў сеткі Інтэрнэт.

Дле рашэння задачы знаходжанне аптымальнага шляху можна выкарыстоўваць розныя сродкі. Для такога рашэння, як алгарытм Дейкстры, Delphi дазволіць стварыць візуальную зручную форму ўводу зыходных дадзеных і вываду канчатковага выніку.