الگوریتم جدیدی برای یافتن کوتاهترین مسیرها در شبکهها
پژوهشگران الگوریتمی طراحی کردهاند که سریعتر از الگوریتم کلاسیک دایجسترا عمل میکند. این روش مانع مرتبسازی را شکسته و برای گرافهای جهتدار و بدون جهت کاربرد دارد.
الگوریتم جدید برای یافتن کوتاهترین مسیرها
پژوهشگران علوم کامپیوتر الگوریتمی طراحی کردهاند که مانع مرتبسازی را در مسئله یافتن کوتاهترین مسیرها شکسته است. این الگوریتم که توسط ران دوآن و تیمش توسعه یافته، سریعتر از الگوریتم کلاسیک دایجسترا عمل میکند و برای هر دو نوع گراف جهتدار و بدون جهت کاربرد دارد.
- الگوریتم جدید از تکنیکهای خوشهبندی و الگوریتم بلمن-فورد استفاده میکند
- این روش گرههای تأثیرگذار را شناسایی و مسیرها را بهطور غیرترتیبی مییابد
- اجرای الگوریتم نیازمند هماهنگی دقیق بین چندین مؤلفه است
«این نتیجه شگفتانگیز است» - رابرت تارجان، دانشمند کامپیوتر دانشگاه پرینستون «نویسندگان در فکر شکستن این مانع جسور بودند» - میکل توروپ، دانشگاه کپنهاگ
با شکسته شدن مانع مرتبسازی، راه برای توسعه الگوریتمهای حتی سریعتر هموار شده است.
