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

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

## 1.Алгоритм 
 motion planning problem. Open nodes represent the "tentative" set. Filled nodes are visited ones, with color representing the distance: the greener, the farther. Nodes in all the different directions are explored uniformly, appearing as a more-or-less circular wavefront as Dijkstra's algorithm uses a heuristic identically equal to 0.]]

Бид одоо анхны гэж нэрлэгдсэн зангилаанаас эхэлнэ.  Заннгилааны зайг 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
Ангилал:Аялал ба маршрутын төлөвлөлт