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

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

1.Алгоритм

Illustration of Dijkstra's algorithm search for finding path from a start node (lower left, red) to a goal node (upper right, green) in a robot 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|) болгож сайжруулна. Чиглэл нь тодорхой бус график зурган дээр хамгийн богино замыг шугаман хугацаанд олох боломжтой, оройнуудыг хамгийн богино хугацаанд бага зам туулхаар тооцоолон бодохдоо математикийн дүрмийн боловсруулалтыг ашигладаг.

Эшлэл

• Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390. {{cite journal}}: Invalid |ref=harv (help)
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw–Hill. pp. 595–601. ISBN 0-262-03293-7.
• (1984) "Fibonacci heaps and their uses in improved network optimization algorithms" in 25th Annual Symposium on Foundations of Computer Science.: 338–346, IEEE. doi:10.1109/SFCS.1984.715934.  Fibonacci heaps and their uses in improved network optimization algorithms (Memento 11. Аравдугаар сар 2012 цахим архивт)
• Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874. {{cite journal}}: Invalid |ref=harv (help)
• Zhan, F. Benjamin; Noon, Charles E. (1998). "Shortest Path Algorithms: An Evaluation Using Real Road Networks". Transportation Science. 32 (1): 65–73. doi:10.1287/trsc.32.1.65. {{cite journal}}: Unknown parameter |month= ignored (help)
• Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.; Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology. {{cite book}}: Invalid |ref=harv (help)
• Knuth, D.E. (1977). "A Generalization of Dijkstra's Algorithm". Information Processing Letters. 6 (1): 1–5.

Холбоос

 Commons: Dijkstra's algorithm – Викимедиа зураг, бичлэг, дууны сан

• 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