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