نمایش مبدأ برای الگوریتم دایکسترا

{{جعبه اطلاعات الگوریتم
| کلاس           = [[الگوریتم جستجو]]
| تصویر         = [[پرونده:Dijkstra Animation.gif|اجرا الگوریتم دایکسترا]]
| زیرنویس تصویر = اجرا الگوریتم دیکسترا
| داده‌ها        = [[گراف (ساختار داده)|گراف]]
| زمان بدترین   = <math>O(|E| + |V| \log|V|)</math>
| زمان بهترین   =
| زمان متوسط    =
| پیچیدگی فضایی =
}}
در [[نظریه گراف]]، '''الگوریتم دایکسترا''' {{به انگلیسی|Dijkstra's algorithm}} یکی از [[الگوریتم‌های پیمایش گراف]] است که توسط دانشمند هلندی [[علوم رایانه]]، [[ادسخر دایکسترا|اِدْسْخِر دیْکْسْترا]] در سال [[۱۹۵۹ (میلادی)|۱۹۵۹]] ارائه شد.

این الگوریتم یکی از [[الگوریتم‌های پیمایش گراف]] است که [[مسئلهٔ کوتاه‌ترین مسیر]] از مبدأ واحد را برای [[گراف وزن‌دار|گراف‌های وزن‌داری]] که یال با وزن منفی ندارند، حل می‌کند و در نهایت با ایجاد [[درخت کوتاه‌ترین مسیر]]، کوتاه‌ترین مسیر از مبدأ به همهٔ [[رأس (نظریه گراف)|رأس‌های]] [[گراف]] را به دست می‌دهد. همچنین می‌توان از این الگوریتم برای پیدا کردن کوتاه‌ترین مسیر از مبدأ تا رأس مقصد به این ترتیب بهره جست که در حین اجرای الگوریتم به محض پیداشدن کوتاه‌ترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد.

الگوریتم دایکسترا یکی از الگوریتم‌های مورد استفاده برای محاسبه کوتاه‌ترین مسیر تک منبع (single-source shortest path) است و مشابه الگوریتم پریم می‌باشد در صورتی که گراف یال با وزن منفی داشته باشد، این الگوریتم درست کار نمی‌کند و می‌بایست از الگوریتم‌های دیگر نظیر [[الگوریتم بلمن-فورد]] که [[پیچیدگی زمانی]] آن‌ها بیشتر است استفاده کنیم.

خط مشی الگوریتم دایکسترا، مشابه با [[الگوریتم حریصانه|روش حریصانهٔ]] استفاده شده در [[الگوریتم پریم]] برای پیدا کردن [[زیر درخت فراگیر بهینه]] است.

== نام‌گذاری ==
نام این الگوریتم بر اساس نام ارائه‌دهنده هلندی آن، یعنی [[ادسخر دایکسترا|اِدسخِر دایکسترا]] انتخاب شده‌است. در منابع فارسی آن را به شکل‌های دِیکسترا، دکسترا، دایکسترا، دایجسترا، دیجسترا، دایجکسترا و دیجکسترا هم نوشته شده‌است، ولی جیمِ آن در تلفظ هلندی آن تلفظ نمی‌شود، لذا دو مورد اول صحیح هستند.

== روند ==
''روند الگوریتم دایکسترا'' مطابق زیر می‌باشد:

۱- انتخاب راس مبدا

{{الگوریتم پیمایش درخت}}

۲- مجموعهٔ S، شامل رئوس گراف، معین می‌شود. در شروع، این [[مجموعه تهی]] بوده و با پیشرفت الگوریتم، این مجموعه رئوسی که کوتاه‌ترین مسیر به آن‌ها یافت شده‌است را در بر می‌گیرد.

۳- راس مبدأ با اندیس صفر را در داخل S قرار می‌دهد.

۴- برای رئوس خارج از S، اندیسی معادل، طول یال + اندیس راس قبلی، در نظر می‌گیرد. اگر راس خارج از مجموعه دارای اندیس باشد، اندیس جدید کمترین مقدار از بین اندیس قبلی و طول یال + اندیس راس قبل، می‌باشد.

۵- از رئوس خارج مجموعه، راسی با کمترین اندیس انتخاب شده و به مجموعهٔ S اضافه می‌گردد.

۶- این کار را دوباره از مرحلهٔ ۴ ادامه داده تا راس مقصد وارد مجموعهٔ S شود.

در پایان اگر راس مقصد دارای اندیس باشد، اندیس آن نشان دهندهٔ مسافت بین مبدأ و مقصد می‌باشد. در غیر این صورت هیچ مسیری بین مبدأ و مقصد موجود نمی‌باشد.

همچنین برای پیدا کردن مسیر می‌توان اندیس دیگری برای هر راس در نظر گرفت که نشان دهندهٔ راس قبلی در مسیر طی شده باشد. بدین ترتیب پس از پایان اجرای الگوریتم، با دنبال کردن رئوس قبلی از مقصد به مبدا، کوتاه‌ترین مسیر بین دو نقطه نیز یافت می‌شود.

== این الگوریتم چگونه کار می‌کند؟ ==
در حین اجرای الگوریتم دو چیز به‌طور ضمنی نگهداری می‌شود. یکی مجموعهٔ <math>S</math> از رأس‌هایی که وزن کوتاه‌ترین مسیر از مبدأ تا آن‌ها مشخص شده و دیگری دنبالهٔ <math>d</math> که برای هر رأس <math>v</math>، مقدار <math>d_v</math> برابر وزن کوتاه‌ترین مسیر از مبدأ تا <math>v</math> است به شرطی که تمام رأس‌های این مسیر به جز <math>v</math> از رئوس داخل <math>S</math> باشند. <math>S</math> در ابتدا تهی و مقادیر <math>d</math> برای همهٔ رئوس به غیر از مبدأ بی‌نهایت است و مقدار آن برای مبدأ صفر گذاشته می‌شود. الگوریتم در هر مرحله رأسی خارج <math>S</math> را که <math>d</math> برای آن کمترین است انتخاب و به مجموعهٔ <math>S</math> اضافه می‌کند و سپس مقادیر <math>d</math> را برای رئوس همسایهٔ آن رأس به‌روز می‌نماید. در صورتی که نیاز به تشکیل درخت کوتاه‌ترین مسیر باشد، الگوریتم می‌بایست دنبالهٔ <math>\pi</math> را که <math>\pi_v</math> پدر رأس <math>v</math> در درخت کوتاه‌ترین مسیر است، به همراه دنبالهٔ <math>d</math> به‌روز کند.

== الگوریتم ==
در پیاده‌سازی، برای اینکه مشخص کنیم چه رئوسی در مجموعهٔ <math>S</math> هستند، در هر مرحله رأسِ وارد شده به <math>S</math> را برچسب می‌زنیم.

=== پیاده‌سازی ===
یک پیاده‌سازی نوعی به این شرح است:
{{چپ‌چین}}
  1 '''Algorithm''' Dijkstra(G,s)
  2 '''Input''': G=(V,E), s(the source vertex)
  3 '''Output''': two sequence d and <math>\pi</math>
  4 '''begin'''
  5 '''for''' all vertices w '''do'''
  6 <math>d_w </math> = <math>\infty </math>
  7 <math>\pi_w </math> = '''NULL'''
  8 <math>d_s </math> = ۰
  9 '''while''' there exists an unmarked vertex '''do'''
 10 let w be an unmarked vertex such that <math>d_w </math> is minimum
 11 mark w
 12 '''for''' all edge (w,z) such that z is unmarked '''do'''
 13 '''if''' <math>d_w + weight(w,z) <d_z </math> '''then'''
 14 <math>d_z </math> = <math>d_w + weight(w,z)</math>
 15 <math>\pi_z</math> = w
 16 '''end'''
{{پایان چپ‌چین}}

=== پیچیدگی زمانی ===
در ساده‌ترین پیاده‌سازی الگوریتمِ دایکسترا، داده‌ها در [[آرایه]] یا [[لیست پیوندی]] ذخیره می‌شوند که بدین ترتیب [[مینیمم]] مقدار <math>d</math> برای رئوس خارج <math>S</math> با الگوریتمی خطی یافت می‌شود. در این حالت پیچیدگی زمانی <math>O(|V|^2+|E|)</math> خواهد بود، چراکه در [[گراف بدون جهت]] هر یال دقیقاً دو بار و در [[گراف جهت‌دار]] هر یال دقیقاً یک بار پیمایش می‌شود و همچنین پیدا کردن مینیمم، <math>(|O(|V</math> زمان می‌خواهد که این مینیمم پیدا کردن <math>|V|</math> بار تکرار خواهد شد.

الگوریتم دایکسترا با نگهداری گراف در [[فهرست مجاورت]] و استفاده از [[هرم دودویی]] یا [[درخت جستجوی دودویی خود-متوازن]] (برای پیدا کردن مینیمم) با پیچیدگی زمانی <math>O((|V|+|E|)log|V|)</math> پیاده‌سازی می‌شود. در صورت استفاده از [[هیپ فیبوناتچی]] به جای صف اولویت‌دار، پیچیدگی زمانی با [[آنالیز استهلاکی]] ([//en.wikipedia.org/wiki/Amortized_analysis Amortized analysis]) به <math>O(|E|+|V|log|V|)</math> بهبود می‌یابد.

== کاربردها ==
از جمله مهم‌ترین کاربردهای این روش می‌توان به محاسبهٔ کوتاه‌ترین فاصلهٔ دو نقطه در یک شهر از طریق راه‌های زمینی اشاره نمود.
برای محاسبهٔ کوتاه‌ترین مسیر بین دو نقطه باید نقاط مورد نظر در یک نقشه را علامت‌گذاری کرد و با استفاده از مشخصات نقاط (طول، عرض و ارتفاع) فاصلهٔ دو نقطه را در هر بار عملیات محاسبه نمود. توجه داریم که در ترافیک سرعت خودروها به شدت پایین آمده و این امر می‌تواند در انتخاب کوتاه‌ترین مسیر تأثیرگذار باشد چرا که ممکن است بین دو نقطه a,b راه‌های ۱و۲ موجود باشد که راه ۱ اتوبان و از خارج شهر و راه ۲ از داخل شهر عبور می‌کند.
فرض کنید فاصلهٔ a,b از طریق راه ۱ حدود ۱۰ کیلومتر و از طریق راه ۲ حدود ۷ کیلومتر باشد ولی راه ۲ علی رقم فاصلهٔ کمتر دارای ترافیک سنگین است در نتیجه می‌توان انتظار داشت که در ساعات شلوغی استفاده از راه ۱ بهتر باشد. از آن جا که اساس محاسبات در این روش بر پایهٔ فاصله بین دو نقطه است می‌توان کاهش سرعت را با افزایش فواصل هم ارز نمود چرا که اگر رابطهٔ سرعت و فاصله را خطی در نظر بگیریم (D=V.T)تاثیر کاهش سرعت و افزایش مسافت یکسان است. از این رو لازم است تا ضرایب تعدیلی در فواصل بین نقاط ضرب شده و این مسائل را در محاسبات لحاظ کرد.
از جمله مهم‌ترین این ضرایب می‌توان به ۳ مورد زیر اشاره نمود:
۱-ضریب ترافیک و شلوغی
۲-ضریب عرض معبر
۳-ضریب شیب که نشانگر افت سرعت در سر بالایی هااست.
گرچه تعیین این ضرایب برای نقاط مختلف شهر نیازمند کارشناسان متخصص ترافیک و بررسی‌های آماری دقیق می‌باشد ولی می‌توان انتظار داشت که در اکثر موارد این ضرایب بین مقادیر ۱ تا ۲ بسته به شرایط تغییر کنند.
* [[مسیریابی]] ([[:w:en:Routing|Routing]])

== منابع ==
{{پانویس}}
{{چپ‌چین}}
* [[:w:en:Thomas H. Cormen|Thomas H. Cormen]], [[:w:en:Charles E. Leiserson|Charles E. Leiserson]], [[:w:en:Ronald L. Rivest|Ronald L. Rivest]], and [[:w:en:Clifford Stein|Clifford Stein]]. ''[[:w:en:Introduction to Algorithms|Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, ۲۰۰۱. {{ISBN|0-262-03293-7|en}}.
* [[:w:en:Udi Manber|Udi Manber]]. ''Introduction to Algorithms — A Creative Approach''. MIT Press and Addison-Wesley, ۱۹۸۹. {{ISBN|0-201-12037-2|en}}.
* [[:w:en:Knuth|Donald E. Knuth]]. ''[http://www-cs-faculty.stanford.edu/~knuth/taocp.html The Art Of Computer Programming Vol ۱.]'', Third Edition. Addison-Wesley, ۱۹۹۷. {{ISBN|0-201-89683-4|en}}.
* Douglas B. West. ''Introduction to Graph Theory'', Second Edition. Prentice Hall, ۲۰۰۱. {{ISBN|0-13-014400-2|en}}.
{{پایان چپ‌چین}}

== پیوند به بیرون ==
* [https://shaazzz.github.io/FarsiCP/wiki/algorithm/graph/Dijkstra آموزش الگوریتم دکسترا برای مسابقات برنامه نویسی]
{{چپ‌چین}}
* C/C++
** [https://web.archive.org/web/20141231054104/http://www.rawbytes.com/dijkstras-algorithm-in-c/ Dijkstra's Algorithm in C Programming Language]
** [https://github.com/xtaci/algorithms/blob/master/include/dijkstra.h Dijkstra's Algorithm in C++]
** [http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/dijkstra_shortest_paths.html Implementation in Boost C++ library]
* Java
** [https://web.archive.org/web/20071019032022/http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html Applet by Carla Laffra of Pace University]
** [https://web.archive.org/web/20150307205448/http://www.stackframe.com/software/PathFinder A Java library for path finding with Dijkstra's Algorithm and example Applet]
** [https://web.archive.org/web/20070929091541/http://www.unf.edu/~wkloster/foundations/DijkstraApplet/DijkstraApplet.htm Dijkstra's Algorithm Applet]
** [https://github.com/graphhopper/graphhopper/tree/90879ad05c4dfedf0390d44525065f727b043357/core/src/main/java/com/graphhopper/routing Dijkstra's algorithm as bidirectional version in Java]
** [http://www.hipster4j.org Hipster: An Open-Source Java Library for Heuristic Search with Dijkstra's algorithm and examples]
** [http://code.google.com/p/annas/ Open Source Java Graph package with implementation of Dijkstra's Algorithm]
** [https://web.archive.org/web/20070927234553/http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml Shortest Path Problem: Dijkstra's Algorithm]
** [http://students.ceid.upatras.gr/~papagel/english/java_docs/minDijk.htm Visualization of Dijkstra's Algorithm]
* C#/.Net
** [http://www.codeproject.com/KB/recipes/ShortestPathCalculation.aspx Dijkstra's Algorithm in C#] {{Webarchive|url=https://web.archive.org/web/20081202152613/http://www.codeproject.com/KB/recipes/ShortestPathCalculation.aspx |date=2 دسامبر 2008 }}
** [http://www.codeproject.com/KB/recipes/FastHeapDijkstra.aspx Fast Priority Queue Implementation of Dijkstra's Algorithm in C#] {{Webarchive|url=https://web.archive.org/web/20111229201146/http://www.codeproject.com/KB/recipes/FastHeapDijkstra.aspx |date=29 دسامبر 2011 }}
** [http://quickgraph.codeplex.com/ QuickGraph, Graph Data Structures and Algorithms for .NET] {{Webarchive|url=https://web.archive.org/web/20180121140629/http://quickgraph.codeplex.com/ |date=۲۱ ژانویه ۲۰۱۸ }}
* [https://web.archive.org/web/20141220002741/http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo.html Dijkstra's Algorithm Simulation]
* [http://purl.umn.edu/107247 Oral history interview with Edsger W. Dijkstra], [[Charles Babbage Institute]] University of Minnesota, Minneapolis.
* [http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html Animation of Dijkstra's algorithm]
* [http://hansolav.net/sql/graphs.html Implementation in T-SQL]
* [http://www.mathworks.com/matlabcentral/fileexchange/20025-advanced-dijkstras-minimum-path-algorithm A MATLAB program for Dijkstra's algorithm] {{Webarchive|url=https://web.archive.org/web/20121218050306/http://www.mathworks.com/matlabcentral/fileexchange/20025-advanced-dijkstras-minimum-path-algorithm |date=۱۸ دسامبر ۲۰۱۲ }}
* [http://www.turb0js.com/a/Dijkstra%27s_Algorithm Step through Dijkstra's Algorithm in an online JavaScript Debugger]
{{پایان چپ‌چین}}
{{ویکی‌انبار-رده|Dijkstra's algorithm}}
{{الگوریتم‌های بهینه‌سازی}}
{{ادسخر دیکسترا}}
[[رده:ادسخر دیکسترا]]
[[رده:الگوریتم‌های جستجو]]
[[رده:الگوریتم‌های گراف]]
[[رده:الگوریتم‌های مسیریابی]]
[[رده:بهینه‌سازی ترکیبیاتی]]
[[رده:علوم رایانه در ۱۹۵۹ (میلادی)]]
[[رده:اختراع‌های هلندی]]