Алгоритам Dijkstra и неговото спроведување

Постои посебна област наречена графикон теорија во математика и информатика. Како дел од својата група и за решавање на различни проблеми, како наоѓање на најкраткиот пат помеѓу темињата. Една заедничка меѓу математичари начини за решавање на овој проблем одамна е алгоритам Dijkstra е.

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

Се верува дека идејата за графиконот беше пуштена во употреба во осумнаесеттиот век Leonardom Eylerom. Тоа беше тој кој ја објави формулирање и решавање на еден од класичните проблемите на оваа теорија - седум мостови на Кенигсберг. Со цел да се објасни целта на оваа теорија често ја користите оваа аналогија како движење меѓу различни градови. Потоа графиконот на авионот ќе биде целата шема на патишта, каде што врвовите ќе бидат одредени предмети (на пример, градот), и ребра - патот од едно теме на друг (аналоген на патот меѓу градовите). алгоритам Dijkstra, во прилог на други методи, може да обезбеди решение за ова прашање.

Наоѓање на најкратката патека

Една од заедничките задачи на графикон теорија е онаа во која треба да се утврди оптималната патека на трошоците помеѓу две точки. Тоа е можно да се намали авионот на одлуката на графикон во кој темињата - градови - се меѓусебно поврзани ребра, што е можно патот. Секој пат има своја должина, па затоа, патуваат за тоа ќе треба да поминат некои пари. Оваа сума е еднаква на тежината на рабовите во графиконот. Тогаш проблемот во пракса може да се формулира на следниот начин: како да го отвори патот од еден град во друг, да бидат потрошени на патот минимални средства.

начини да се реши

За да се реши овој проблем, ние сме биле измислени од страна на некои алгоритми, кои станаа познати во научниот свет. На пример, Флојд алгоритам - Uorshella, Форд - Bellman. Класичниот начин на наоѓање на решенија е, исто така, алгоритам Dijkstra е. Може да се користи за пондерираната (позната маса на секој раб) на графика, и да се разреди. Да се најде најдобар начин мора да направите неколку чекори.

алгоритам Dijkstra е

Поентата на овој метод е дека цената на сите темиња од даден, со секој доделен етикета со одредена вредност. Тогаш резултатот ќе содржи темиња чии етикети се минимални. На врвот на првата почетна чекор ќе бидат означени со вредност 0. Потоа, сите од следниве врвови се смета, дека е, оние кои може да се стигне од изворот. Тие се означени, чија вредност се утврдува како збир на изворниот код и тежината на патеки. Од врвот на следниот чекор, изберете оној кој има најмала вредност од етикета, а студирал сите темиња во дека од него може да оди без помош на средно јазли. Одредете нова етикета еднаква на етикетата блузи - изворниот код плус тежината на патот. Ако вредноста е помала од врвот на етикета, на етикетата се менува. Инаку, таа и понатаму останува на оригиналната вредност. Во исто време во посебен низа, чија димензија е еднаков на бројот на темиња, таа ги зачувува резултатот на оптимизација, во кои и пропишан начин. За спроведување на метод, како што е алгоритам Dijkstra, Паскал нуди многу практично средство. Алгоритмот има предност во тоа што лесно може да биде основа за програма со која има мала големина. Примери за такви софтверски производи лесно да се најде на интернет.

Dle решенија на различни алатки можете да го користите задача да се најде оптималната патека. За решенија како што е алгоритам Dijkstra, Делфи ќе се создаде удобен форма на визуелна внес на податоци и излез на конечниот резултат.