در این قسمت تیم کدگیت سورس الگوریتم دایکسترا در پایتون را تهیه کرده است. اگر بخواهیم درون گراف به جستجو بپردازیم و کوتاهترین مسیر را بین دو گره (Node) پیدا کنیم از دایکسترا استفاده میکنیم. این الگوریتم کوتاهترین مسیر بین همه گرههای یک گراف (از یک نقطه شروع مشخص شده) را به شما نشان خواهد داد. در این سورس کد علاوه بر الگوریتم دایکسترا، گراف وزن دار و صف اولویت دار نیز پیاده سازی گردیده است. با ما همراه باشید تا این سورس کد جذاب را به شما معرفی کنیم. همچنین پیشنهاد میکنیم از دیگر سورسهای ما دیدن فرمایید(همگی سورسهای پایتون هستند):
سورس الگوریتم دایکسترا در پایتون
دایکسترا الگوریتمی برای پیمایش یک گراف است. گراف باید وزن دار باشد و وزنهای آن نباید منفی باشد تا الگوریتم دایکسترا بدرستی کار کند. این الگوریتم مسئله کوتاهترین مسیر از گره مبدأ را برای گرافهای وزنداری که یال با وزن منفی ندارند، بدست میآورد و در نهایت یک درخت کوتاهترین مسیر یا MST، از مبدأ به همه گرههای گراف را پیدا میکند. سورس الگوریتم دایکسترا در پایتون در این قسمت تهیه نمودهایم. این سورس با دریافت گراف در خروجی کوتاهترین مسیر بین مبدا و همه گرههای گراف را بدست میآورد.
نحوه اجرا
زبان برنامه نویسی سورس دایکسترا پایتون بوده و فرمت فایل .py است. بعد از تهیه سورس از سایت کدگیت فایلی با فرمت zip در اختیار شما قرار میگیرد. فایل را از حالت zip خارج کرده تا بتوانید سورس کد را ببینید. فایل اصلی برنامه با نام main.py میباشد. این فایل را اجرا کنید تا برنامه اجرا شود. پس از اجرا خروجی زیر را مشاهده خواهید کرد:
0 -> 0: 0
0 -> 1: 0 -> 4 (0.38) -> 5 (0.73) -> 1 (1.05)
0 -> 2: 0 -> 2 (0.26)
0 -> 3: 0 -> 2 (0.26) -> 7 (0.60) -> 3 (0.99)
0 -> 4: 0 -> 4 (0.38)
0 -> 5: 0 -> 4 (0.38) -> 5 (0.73)
0 -> 6: 0 -> 2 (0.26) -> 7 (0.60) -> 3 (0.99) -> 6 (1.51)
0 -> 7: 0 -> 2 (0.26) -> 7 (0.60)
گرافی که به عنوان ورودی در الگوریتم دایکسترا استفاده گردیده است در تصویر زیر میبینید. شامل 8 راس و 15 یال می باشد. نقطه شروع را گره صفر قرار دادهایم و در خروجی کوتاهترین مسیر بین این گره و مابقی گرههای گراف چاپ گردیده است.

وزن یالهای گراف در زیر آورده شده است:

نقد و بررسیها
هنوز بررسیای ثبت نشده است.