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

Дижикстрагийн алгоритм, Dijkstra –ийн алгоритмыг 1956 онд Нидерландын компьютерын эрдэмтэн судлаач Edsger Dijkstra үүсгэн томъёолсон ба 1959 онд нийтлүүлсэн. Графийн хайлтийн алгоритм бөгөөд нэг эхтэй богино замын бодлогыг шийдвэрлэдэг. Графийн ирмэгүүд нь сөрөг биш утгатай нэг эхтэй богино замын бодлогыг шийдсэн бөгөөд хамгийн богино замын модыг гаргаж өгдөг. Энэ алгоритм нь хамгийн бага замыг олохдоо эхний цэгээс  графын зангилаа бүрээр дайрдаг. Алгоритм нь нэг зангилаанаас өөр нэг зангилаа очих хамгийн  богино замыг олохоор ажиллах ба хамгийн дөт замыг олмогц програм зогсоно. Жишээлбэл: Дижикстрагийн алгоритм нь  нэг хотоос  өөр нэг хотруу холбосон  эхлэлийн цэг болон төгсгөлийн цэгийн хоорондох зай  хамгийн богино  байхаар тооцон олдог. Улмаар , хамгийн эхний богино зам бол сүлжээний шугамын протоколуудад өргөн ашигладаг, тухайлбал IS-IS ба OSPF(нээлттэй хамгийн эхний богино зам) юм. 
Дижикстрагийн  анхны алгоритмийн бага эрэмбийг олох дараалалд  O(|V2|) –ийг хэрэглэдэггүй.  V нь координатын босоо тэнхлэг дэх тоо. Энэ алгоритмын санааг Leyzorek  бас дэвшүүлж байсан. Бага эрэмбэтэй дараалал дээр суурилсан Fibonacci-ийн овоолго байдлаар  O(|E|+|V|log|V|) томёонд хэрэгжүүлсэн.  E- эрмэгийн тоо  Энэ нь  шинж тэмдэггүй ,сөрөг биш утгагай, нэг эхтэй ,богино замаа хамгийн хурдан мэдэх алгоритм юм.  

 1.Алгоритм 

Бид одоо анхны гэж нэрлэгдсэн зангилаанаас эхэлнэ.  Заннгилааны зайг Y үсгээр тэмдэглэнэ. Анхны зангилаанаас Y хүртэлхийг зай гэдэг. Дижикстрагийн алгоритмаар зарим анхдагч зайн утгуудыг оноож өгдөг, алхам алхмаар сайжруулдаг. 
1.	Эхлээд бүх зангилаандаа анхны утгыг олгоно:
Тэр нь манай анхны зангилаанаас бусад зангилаанд тодорхойгүй буюу  тэг гэдэг утга өгнө. 
2.	Анхдагч зангилааг тухайн зангилаа болгож авна. Бүх зангилааг агуулсан зочлоогүй зангилаануудын олонлогыг үүсгэнэ. 
3.	Тухайн зангилааны хувьд хөрш зангилаануудад анхааран тэдрээрийг урьдчилан бодож тооцоолно. Одоогийн а зангилаа 6-ийн урттай гэж тэмдэглэгдсэн, түүний b хөрш  зангилаатай холбогдсон ирмэгийн урт нь 2 бол b хүртэлх урт нь (6+2=8) болно. Хэрэв энэ зай нь өмнө b хүртэлх урьдчилсан зайнаас бага бол түүнийг дарж бичнэ. Шалгаж үзсэн ч гэсэн (зочилсон ) гэж тэмдэглээгүй бол тэр зангилаа зочлоогүй олонлогт байсаар байна. 
4.	Тухайн зангилааны бүх хөршүүдийг авч үзсэний дараа тухайн зангилааг зочилсон гэж тэмдэглээд зочлоогүй олонлогоос хасна. Зочилсон зангилааг дахин хэзээ ч шалгахгүй. 
5.	Хэрвээ очих ёстой эцсийн зангилааг зочилсон гэж тэмдэглэсэн бол (2 зангилааны хоорондох зам) тодорхойлогдсон, хэрэв зочлоогүй олонлог дахь зангилаануудын урьдчилсан хамгийн бага зай нь тодорхойгүй бол (төлөвлөгдсөн нэвтрэлт дууссан эсвэл анхны зангилаа болон үндсэн зочлоогүй зангилааны хооронд холбоо байхгүй байна). Тэгээд алгоритм дуусна. 
6.	Хамгийн бага урьдчилсан зайтай зочлоогүй зангилааг шинэ тухайн зангилаа болгоод 3-р алхам руу буцаана.

 Тайлбар/description/ 
Та хотын газрын зургаас нэг газарт хүрэх хамгийн богино замыг олохын тулд анх эхлэх газар болон  явах замаа тодорхойлох хэрэгтэй. Явах замаа тодорхойлохдоо: эхлэх цэгээс очих газар хүртлээ шулуунаар холбоно.  Үүнийг хязгааргүй орон зайд ашиглах боломжгүй гэхдээ очоогүй газруудаа хаяглалгүй үлдээдэг....

 Ажиллах, гүйцэтгэх хугацаа 
Дижикстрагын алгоритмын дээд хугацааг тооцоолохдоо төгсгөлийн тоо/E/ ба оройн тоо/V/ дүрсэлж болох ба функцээр илэрхийлэхэд |E|, |V| гэж тэмдэглэдэг. Ямарч oройн Q олонлогийн явах хугацаа О(|E|*dkq + |V|*emq) dkq ба emq нь хамгийн цөөн үйлдэл ба бага хугацаа зарах үйлдлүүд юм.
Хамгиин хялбар Дижикстрагын алгоритмын хэрэглээ бол Q-г жирийн хэлхээтэй жагсаалт эсвэл цуваанд хадгалж, хамгийн бага хугацааг гаргах бол Q дэх оройнуудаас шугаман хайлт хийх юм. Энэ тохиолдолд явах хугацаа О(|E|+|V|^2)=O(|V|^2).
Сийрэг граф-д Дижисктрагын алгоритмыг холбоост листэнд хийж хоёртын модны хайлт, хоёртын овоолго эсвэл фибонакын овоолгын анхдагч дарааллаар ашиглаж хамгийн бага хугацаа олохыг хурдан болгож алгоритмаа үр дүнтэйгээр шийдвэрлэсэн. Хоёртын модны хайлт эсвэл , хоёртын овоолго хэрэглэж хугацааг О((|E|+|V|)log|V|) олно. Энэ нь O(|E|log|V|)-ээр граф холбоостой үед дийлэгддэг.
Энгийн хоёртын овоолго дээр О(|V|)хугацааг хэмнэхийн тулд oрой болгоны заагчийг овоолгын заагчтай хамт санах хэрэгтэй (бас анхны дараалал Q өөрчлөгдөхөд хугацаа хоцрогдолгүй  байх ).
Тэгэхлээр зөвхөн O(lov|V|)цаг авна. Фибонакын овоолго үүнийг O(|E|+|V|log|V|) болгож сайжруулна.  Чиглэл нь тодорхой бус график зурган дээр хамгийн богино замыг шугаман хугацаанд олох боломжтой, оройнуудыг хамгийн богино хугацаанд бага зам туулхаар тооцоолон бодохдоо математикийн дүрмийн боловсруулалтыг ашигладаг.  

Тэмдэглэл

 Эшлэл 








 Холбоос 

 C/C++
 Dijkstra's Algorithm in C++
 Implementation in Boost C++ library
 Dijkstra's Algorithm in C Programming Language
 Java
 Applet by Carla Laffra of Pace University
 Visualization of Dijkstra's Algorithm
 Shortest Path Problem: Dijkstra's Algorithm
 Dijkstra's Algorithm Applet
 Open Source Java Graph package with implementation of Dijkstra's Algorithm
 A Java library for path finding with Dijkstra's Algorithm and example Applet
 Dijkstra's algorithm as bidirectional version in Java
 C#/.Net
 Dijkstra's Algorithm in C#
 Fast Priority Queue Implementation of Dijkstra's Algorithm in C#
 QuickGraph, Graph Data Structures and Algorithms for .NET
 Dijkstra's Algorithm Simulation
 Oral history interview with Edsger W. Dijkstra,  Charles Babbage Institute University of Minnesota, Minneapolis.
 Animation of Dijkstra's algorithm
 Haskell implementation of Dijkstra's Algorithm on Bonsai code
 Implementation in T-SQL
 A MATLAB program for Dijkstra's algorithm
 Step through Dijkstra's Algorithm in an online JavaScript Debugger

Ангилал:Оновчлолын алгоритм
Ангилал:Граф хайлтын алгоритм
Ангилал:Routing
Ангилал:Аялал ба маршрутын төлөвлөлт