Dijkstra ның алгоритм және оны жүзеге асыру

математика және информатика графтар теориясы деп аталатын жеке ауданы бар. оның жиынтығының бір бөлігі ретінде және осындай шыңы арасындағы қысқа жолды табу сияқты түрлі мәселелерді шешу үшін. Бұл мәселені шешу математиктер жолдары арасында ортақ бір ұзын Dijkstra берушінің алгоритм болды.

математикалық график қандай

Ол Графиктің ұғымы он сегізінші ғасырда Leonardom Eylerom пайдалану берілді деп саналады. Кенигсберг жеті көпірлер - Бұл теория классикалық мәселелерінің бірін қою және шешу жариялады кім ол. Бұл теорияның нысанды түсіндіру мақсатында жиі әр түрлі қалалар арасындағы қозғалысы ретінде осы ұқсастығы пайдаланыңыз. бір шыңдары жылғы жолы (қалалар арасындағы аналогтық жол) - Содан кейін ұшаққа графтар шыңдары нақты заттар (мысалы, қала), және жиектер болуға бүкіл маршрут схемасы, болады. Dijkstra ның алгоритмі, басқа әдістермен қатар, осы мәселе шешімін қамтамасыз ете алады.

қысқа жолды табу

ортақ міндеттерінің бірі графтар теориясы , сіз екі нүктелер арасындағы оңтайлы құны жолын анықтау керек, ол бірі болып табылады. Қалалар - - мүмкін жол болып табылады өзара байланысты қабырғалары, болып ол шыңдары онда графиктің шешіміне ұшақ төмендетуге болады. Әрбір жол өз ұзындығы, сондықтан, оған туристік кейбір ақша жұмсауға болады. Бұл сома диаграммада шетінен салмағы тең. бір қаладан жол салуы қалай жол минималды құралдарына жұмсалады, мынадай: Содан кейін іс жүзінде мәселе тұжырымдауға болады.

шешу жолдары

Бұл мәселені шешу үшін, біз ғылыми әлемде кеңінен белгілі болды, кейбір алгоритмдер ойлап тапты. Мысалы, Флойд алгоритм - Uorshella, Форд - Беллмана. шешімін табу классикалық жолы, сондай-ақ Dijkstra ның алгоритмі болып табылады. Ол Графиктің сараланған (әрбір шетіне белгілі салмағы) үшін пайдаланылуы мүмкін, және сұйылту үшін. Егер бірнеше қадамдар жасауға тиіс түпкі жолын таба.

Dijkstra ның алгоритмі

Осы әдістің нүкте әрбір тег белгілі бір мәнді белгілейді, онда берілген бастап, құнын барлық шыңдары фактісі, жатыр. Содан кейін нәтижесі кімнің жапсырмалар аз шыңдары қамтиды. Бірінші бастапқы қадамда жоғарғы туралы мынадай шыңдары барлық қарастырылады, Содан кейін 0. мәнімен тегтелген болады, яғни көзден жетуге болады сол болып табылады. Олар құны жолдарын бастапқы коды және салмағы сомасы ретінде анықталады, таңбаланған. Келесі қадамда жоғарғы жағынан, жапсырманың ең аз мәні бар біреуін таңдаңыз, және біз аралық түйіндерді пайдаланбай баруға болады оған деген барлық шыңдары оқыды. бастапқы коды плюс жолмен салмағы - жапсырма шыңдарды тең жаңа белгісін көрсетіңіз. мән жоғарғы жапсырмасында кем болса, жапсырма өзгереді. Әйтпесе, ол бастапқы құны болып қалады. өлшемі биіктерге санының тең жеке алапта, Сонымен қатар, ол онда мен бел жолы, оңтайландыру нәтижесінде сақтайды. Мұндай Dijkstra ның алгоритм ретінде іске әдісі, Паскаль өте ыңғайлы құралдарын ұсынады. алгоритм ол оңай шағын мөлшері бар бағдарлама үшін негіз бола алады деп артықшылығы бар. Интернетте оңай таба осындай бағдарламалық өнімдерді мысалдары.

Dle шешімдер Оңтайлы жолын табу үшін тапсырманы пайдалануға болады түрлі құралдар. Мұндай Dijkstra ның алгоритм ретінде шешімдер үшін, Delphi визуалды деректерді енгізу және шығару түпкілікті нәтиженің ыңғайлы нысанын жасайды.