آزمایشگاه آزاد؛ بدون نیاز به ورود
کوتاه‌ترین مسیر رو با وزن جاده‌ها پیدا کن
کوتاه‌ترین راه همیشه کمترین تعداد جاده رو داره؟ وزن‌ها رو عوض کن و فاصلهٔ کل مسیر رو از تعداد گام‌ها جدا بسنج.
آزمایش رو شروع کناز وزن‌های شروع استفاده کن: مسیر پیش‌فرض از شروع به گره ۲ و بعد پایان می‌ره. وزن جادهٔ دوم رو زیاد کن و ببین مسیر محاسبه‌شده چطور عوض می‌شه.
آزمایشگاه در حال آماده شدنه…
حالا خودت امتحان کن
هر بار فقط یک چیز رو تغییر بده تا اثرش رو ببینی. قبل از اجرا، نتیجه رو حدس بزن.
گرون شدن جادهٔ مستقیم
وزن‌ها رو روی ۴، ۲، ۵، ۱ و ۳ بذار؛ وزن جادهٔ دوم، یعنی یال مستقیم از شروع به گره ۲، رو از ۲ به ۲۰ برسون.
حدست چیه؟ با گران شدن اون جاده، مسیر با کمترین فاصله عوض می‌شه؟
توضیح نتیجه رو ببین
در حالت اول فاصله ۵ و تعداد گام‌ها ۲ه. بعد از زیاد کردن وزن جادهٔ دوم، مسیر محاسبه‌شده از گره‌های ۱، ۳ و ۲ می‌گذره؛ فاصله ۱۳ و تعداد گام‌ها ۴ می‌شه. در نمودار ممکنه یال مستقیم شروع تا گره ۲ هم رنگی دیده بشه، با این‌که مسیر محاسبه‌شده از اون رد نمی‌شه.
جاده‌های بیشتر، فاصلهٔ کمتر
همهٔ وزن‌ها رو روی ۱ بذار؛ بعد فقط وزن جادهٔ دوم رو از ۱ به ۱۰ تغییر بده. فاصلهٔ کل و تعداد گام‌ها رو مقایسه کن.
حدست چیه؟ ممکنه مسیر چهارگامی از یک مسیر دوگامی کوتاه‌تر باشه؟
توضیح نتیجه رو ببین
وقتی همهٔ وزن‌ها ۱ هستن، مسیر مستقیم دو جاده داره و فاصله‌اش ۲ه. با وزن ۱۰ برای جادهٔ مستقیم، مسیر چهار جاده‌ای با فاصلهٔ ۴ انتخاب می‌شه؛ مسیر دوگامی فاصلهٔ ۱۱ داشت. الگوریتم مجموع وزن‌ها رو کمینه می‌کنه، نه تعداد جاده‌ها رو.
وزن یکی از جاده‌های مسیر
وزن‌ها رو روی ۴، ۲، ۵، ۱ و ۳ بذار؛ بعد وزن جادهٔ پنجم، از گره ۲ تا پایان، رو از ۳ به ۱۰ برسون.
حدست چیه؟ فاصلهٔ مسیر و تعداد جاده‌ها هر دو عوض می‌شن؟
توضیح نتیجه رو ببین
فاصله از ۵ به ۱۲ می‌رسه، اما مسیر هنوز دو جاده داره. جادهٔ پنجم توی مسیر کوتاه اولیه بود و با گران‌تر شدنش، همون مسیر ۷ واحد طولانی‌تر می‌شه.
پشت این حرکت چه خبره؟
گره‌ها و یال‌های وزن‌دار
نقطه‌ها گره‌ان و جاده‌های بینشون یال. هر یال یک وزن مثبت داره که در این مدل مثل طول یا هزینهٔ عبور حساب می‌شه. وزن‌ها رو با یک واحد فرضی مقایسه کن؛ این‌ها کیلومتر واقعی نیستن.
دیکسترا چطور مسیر رو پیدا می‌کنه؟
الگوریتم از شروع آغاز می‌کنه، نزدیک‌ترین گرهِ هنوز بررسی‌نشده رو برمی‌داره و فاصلهٔ راه‌های تازه به همسایه‌ها رو مقایسه می‌کنه. با وزن‌های غیرمنفی، این روش کوتاه‌ترین فاصله رو پیدا می‌کنه.
فاصله با تعداد جاده‌ها فرق داره
فاصلهٔ مسیر جمع وزن جاده‌هاست؛ تعداد گام‌ها فقط می‌گه چند یال از مسیر رد شده. ممکنه یک راه جاده‌های بیشتری داشته باشه، ولی مجموع وزنش کمتر باشه.
پنج وزن ثابت، چند مسیر ممکن
در این گراف پنج‌گرهی، وزن‌ها روی پنج جاده تغییر می‌کنن و الگوریتم مسیر شروع تا پایان رو می‌سنجه. با تغییر یک وزن، مسیر بهینه ممکنه عوض بشه یا همون مسیر با فاصلهٔ تازه باقی بمونه.
سؤالت رو بپرس، جوابش رو هم ببین
وقتی توی چت دربارهٔ یک مفهوم درس می‌خونی، دستیار هوش مصنوعی می‌تونه شبیه‌سازی مرتبط رو کنار توضیحش نشون بده. پارامترها رو تغییر می‌دی و با کمک توضیح بعدی، نتیجه رو بهتر می‌فهمی.
شروع یادگیری با چتبرای ادامه در چت، وارد مسیر شروع و ورود می‌شی. نتیجهٔ این آزمایش به چت منتقل نمی‌شه.
نمونهٔ نمایشی از آموزش در چت
چرا مسیر چهار جاده‌ای از مسیر دو جاده‌ای کوتاه‌تر شد؟
چون الگوریتم مجموع وزن‌ها رو مقایسه می‌کنه، نه تعداد جاده‌ها رو. در آزمایش، مسیر چهارگامی وزن کل ۴ داشت و مسیر دوگامی وزن کل ۱۱؛ برای همین راه طولانی‌تر از نظر گام، فاصلهٔ کمتری داشت.
سؤال‌های رایج
الگوریتم دیکسترا چه چیزی رو کمینه می‌کنه؟
مجموع وزن یال‌های مسیر رو از گرهٔ شروع تا گرهٔ پایان کمینه می‌کنه؛ این لزوماً کمترین تعداد یال نیست.
تفاوت فاصله و تعداد گام‌ها چیه؟
فاصله جمع وزن جاده‌هاست. تعداد گام‌ها فقط می‌شمره از چند جاده عبور می‌کنی.
وزن جاده حتماً باید فاصله باشه؟
نه، می‌تونه هزینه یا زمان هم باشه؛ فقط همهٔ وزن‌ها در این الگوریتم باید غیرمنفی باشن. مدل این صفحه وزن فرضی و مثبت داره.
می‌تونم وزن منفی وارد کنم؟
نه، کنترل‌ها وزن‌های صحیح از ۱ تا ۲۰ می‌گیرن. دیکسترا برای وزن منفی مناسب نیست.
چرا خطی که رنگی شده جزو مسیر نیست؟
در بعضی حالت‌ها شکل گراف ممکنه یک جادهٔ اضافه بین دو گرهٔ مسیر رو هم رنگی کنه. فاصله و تعداد گام‌ها رو هم ببین؛ اونا از مسیر محاسبه‌شده میان.