الگوریتمِ دایکسترا در گرافِ با وزنِ نامنفی، کمترینِ مجموعِ وزنِ مسیر از یک مبدأ به گره‌هایِ دسترس‌پذیر را پیدا می‌کند. کمترینِ تعدادِ یال الزاماً کمترینِ هزینه نیست. این راهنما دفترِ فاصله، اصلاحِ مسیر، parent و رکوردهایِ کهنهٔ صف را رویِ یک گرافِ کوچک واقعاً اجرا می‌کند.
وزن را پیش از نامِ الگوریتم تعریف کنیم
گرافِ جهت‌دارِ ما شش گره دارد. ازSبهAوزن۷، بهBوزن۲و بهGوزن۱۰داریم. ازBبهAوزن۱و بهCوزن۰؛ ازCبهAوزن۱و بهGوزن۸؛ و ازAبهGوزن۲است. Uهیچ ارتباطی ندارد. وزن‌ها عددِ صحیحِ آموزشی‌اند؛ صفر مجاز است و منفی نیست. زمانِ واقعی، قیمت یا وضعیتِ شبکه اندازه‌گیری نشده است.
برایِ هر گره، فاصلهٔ بهترینِ مسیرِ شناخته‌شده و parent را نگه می‌داریم. آغازِ Sفاصلهٔصفر دارد؛ برایِ بقیه هنوز مسیری نداریم. «ناشناخته» را فاصلهٔصفر قرار نمی‌دهیم. نام‌ها فقط شناسه‌اند و در تساویِ اولویت، شمارندهٔ ورود به صف تصمیم می‌گیرد.
Relaxation یعنی کدام مقدار را بهتر کنیم؟
وقتی گرهِ u با فاصلهٔdبرداشته می‌شود، برایِ یالِu→vبا وزنِw، نامزدِd+wرا می‌سازیم. اگر از بهترینِ قبلیِvکمتر باشد، فاصله و parent اصلاح و یک رکوردِ تازه واردِ heap می‌شود. اینجا فقط بهبودِ سخت‌گیرانه پذیرفته می‌شود؛ هزینهٔ برابر parent را عوض نمی‌کند. تابعِ ما همهٔ گره‌هایِ دسترس‌پذیر را تا خالی‌شدنِ صف بررسی می‌کند.
از فاصلهٔ۷ به فاصلهٔ۳ برسیم
| گرهِ نهایی‌شده در ترتیبِ اجرا | فاصله | اصلاحِ مهم |
|---|---|---|
| S | ۰ | A=۷، B=۲، G=۱۰ |
| B | ۲ | Aاز۷به۳ وCبه۲ |
| C | ۲ | نامزدِA=۳وG=۱۰ بهبودِ سخت‌گیرانه نیست |
| A | ۳ | Gاز۱۰به۵ |
| G | ۵ | یالِ خروجی ندارد |
یالِ صفرِB→C باعث می‌شود BوCفاصلهٔ یکسان داشته باشند. این تساوی به معنیِ یکی‌بودنِ دو گره یا حذفِ آن یال نیست. مسیرِ انتخاب‌شدهٔ Gاز parentها S→B→A→G است و جمعِ۲+۱+۲=۵را دارد. مسیرِ دیگری با همین هزینه ازCمی‌گذرد، اما قاعدهٔ تساویِ ما parentِ قبلی را حفظ کرده است.
رکوردِ کهنه را دوباره نهایی نکنیم
رکوردِ Aبا هزینهٔ۷هنوز در heap مانده، چون نسخهٔ سادهٔ ما decrease-key انجام نمی‌دهد. وقتی بعد ازAبا۳برداشته شود،۷با بهترینِ جاری۳برابر نیست و کنار گذاشته می‌شود. همین اتفاق برایِ Gبا۱۰در برابرِ۵رخ می‌دهد. کد هر دو stale pop را واقعاً ثبت و کنترل می‌کند؛ تنها دربارهٔ امکانِ آن حرف نزده است.
کمینه‌بودن به شرطِ وزن‌هایِ نامنفی و برداشتنِ رکوردِ معتبرِ کمینه مربوط است؛ نخستینِ «کشفِ» هدف کافی نیست. Gدر همان گامِSبا۱۰کشف شده بود، ولی جوابِ۵هنوز پیدا نشده بود. اگر جست‌وجویِ تک‌هدف می‌نویسید، قاعدهٔ توقف را با همین تمایز کنترل کنید.
چرا BFS در همین گراف جوابِ متفاوت دارد؟
یک BFSِ مستقل که وزن را نادیده می‌گیرد، S→Gرا با یک یال برمی‌گرداند؛ هزینهٔ آن۱۰است. مسیرِ دایکسترا سه یال و هزینهٔ۵دارد. پس «کوتاه‌ترین» بدونِ گفتنِ واحد مبهم است: تعدادِ یال یا جمعِ وزن؟ مقایسهٔ BFS وDFS مسئلهٔ گرافِ بی‌وزن و ترتیبِ بازدید را جدا توضیح می‌دهد.
برایِ کنترلِ مستقل، همهٔ مسیرهایِ سادهٔ گرافِ کوچک ازSبه هر مقصد شمرده و کمترینِ هزینه با دفترِ دایکسترا مقایسه شده است. مسیرِ هر مقصد هم دوباره رویِ یال‌ها قیمت‌گذاری می‌شود. این شمارش برایِ ورودیِ آموزشیِ کوچک است؛ روشِ سریعِ عمومی برایِ گرافِ بزرگ نیست.
گرهِ دسترس‌ناپذیر و وزنِ منفی
برایِU، فاصله و مسیر nullاست. parentِ Sهم nullاست، اما فاصلهٔصفر و مسیرِ[S]آن را ازUجدا می‌کند. بنابراین فقط یک فیلدِ parentبرایِ تصمیم دربارهٔ دسترسی کافی نیست. فایلِ خروجی، فاصله و مسیر را کنارِ هم دارد.
کد همهٔ یال‌ها را پیش از شروع کنترل می‌کند. اگر بهUیالِ منفیِU→Sبا وزنِ−۱اضافه کنیم، با آنکهUازSدسترس‌پذیر نیست، قراردادِ ورودی رد می‌شود. این انتخابِ اعتبارسنجیِ صریحِ ابزارِ ماست. یالِ موازی و وزنِ غیرصحیح هم خارج از قراردادِ فایل‌اند؛ این‌ها ممنوعیتِ تمامِ پیاده‌سازی‌هایِ کتابخانه‌ای نیستند. NetworkX اجرا نشده و بنچمارکِ زمان یا حافظه نداریم.
گرافِ داده با مسیرِ کمینه فرق دارد
گرافِ دانش مسیرِ رابطه و شناسه را بررسی می‌کند؛ داشتنِ یال به‌تنهایی وزنِ هزینهٔ معتبری نمی‌سازد. برایِ اثرِ تخمینِ باقی‌مانده، A* مکمل است. در نیازِ عملیِ پاسخ‌گویی، کار و خروجیِ قابلِ آزمون را در راهکارهایِ اپرا مشخص کنید؛ این تمرین مسیر‌یاب یا روشِ داخلیِ محصول را اعلام نمی‌کند.
فایل تمرین و منبع
فاصلهٔ همهٔ گره‌ها، parent و صفِ واقعی؛ Python · دفترِ بهبودها، دو رکوردِ کهنه و کنترلِ مستقلِ هزینه
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.