الگوریتم های مسیریابی – بخش سوم (الگوریتم بلمن فورد)

الگوریتم مسیریابی بلمن فورد (Bellman-Ford)

در حالت کلی الگوریتم بلمن فورد قادر است، کوتاه ترین مسیر را در گراف هایی که دارای یال منفی نیز می باشند، به دست آورد. این الگوریتم نیز بسیار شبیه به الگوریتم دیکسترا بوده با این تفاوت که از یک راس شروع شده و به تمامی نقاط مجاور اندیس می دهد. با ادامه ی این روند و نگه داشتن اندیس های کوچکتر ، کوتاه ترین فاصله از راس مبدا به تمامی نقاط گراف محاسبه می شود و در نتیجه کوتاه ترین فاصله بین راس مبدا و مقصد نیز مشخص می گردد.

به مثال زیر توجه کنید:

گرافی مطابق شکل داریم، می خواهیم کوتاه ترین فاصله ی راس S تا تمامی نقاط رل به دست آوریم. مطابق الگوی زیر عمل می کنیم:

7 thumb الگوریتم های مسیریابی   بخش سوم (الگوریتم بلمن فورد)

ابتدا فاصله ی راس S تا نقاط مجاور را محاسبه می کنیم.

8 thumb الگوریتم های مسیریابی   بخش سوم (الگوریتم بلمن فورد)

 

سپس از ریوس مجاور حرکت نموده و کوتاه ترین فواصل را بدست می آوریم.

9 thumb الگوریتم های مسیریابی   بخش سوم (الگوریتم بلمن فورد)

 

در نهایت به شکل زیر می رسیم.

10 thumb الگوریتم های مسیریابی   بخش سوم (الگوریتم بلمن فورد)

Контекстная реклама  — размещение текстово-графических рекламных материалов рядом с результатами поиска на сайтах, предлагающих пользователю функцию поиска topodin, Что входит в продвижение сайта? Мы нацеливаемся только на результат: сайт будут посещать люди, заинтересованные в Ваших товарах и услугах, для этого мы выведем его на лидирующие позиции в поисковой выдаче (Яндекс + Google) по основным ключевым словам

مطالب مرتبط

7 نظر

  1. ایمان

    سلام
    برای نوشتن برنامه مورد استفاده در جی ای اس بوسیله انجین و در محیط دسکتاپ با ارک کدام زبان برنامه نویسی بهتر و سرعت بالاتری در اجرا داره از کجا شروع کنم و چه منابعی رو بخونم
    و کلا برای نوشتن برنامه های از این دست کدام نرم افزار بهتره و بازار کاری بیشتری داره
    با تشکر : ایمان مهندسی محیط زیست

    پاسخ
    1. ادمین

      سلام
      ۱- تفاوتی بین زبان های برنامه نویسی آرک آبجکت (ArcObjects) و آرک انجین (ArcEngine) وجود نداره. با هرکدوم که راحت ترید برنامه نویسی کنید.
      ۲- فعلا تنها یک منبع فارسی هست که توی این لینک معرفی شده. متاسفانه هنوز منبع انگلیسی برای آرک آبجکت با انجین ۱۰ وجود نداره، چه برسه به فارسی. باید از همون help و سمپل های توب اون استفاده کنید. کتاب فارسی مهندس هاشمی هم تا حد زیادی کمکم می کنه.
      ۳- کدوم نرم افزار؟ خب همین آرک آبجکت و آرک انجین
      موفق باشید

      پاسخ
  2. سروش

    خیلی ممنون. این قدر استادمون این مطلب ساده رو پیچیده و الگوریتمی گفته بود، هیچی نمی فهمیدم. با این ۴ تا شکل ساده قشنگ فهمیدم. موفق باشید

    پاسخ
  3. هدیه

    سلام خسته نباشید
    من پروژه ایی دارم که الگوریتم بلمن فورد برای یک گراف مشخص باید در سی شارپ پیاده سازی کنم که در نهایت ماتریس های خروجی هر گره تا گره خروجی رو بگه.
    من نمیدونم فقط با نوشتن گراف امکان پذیره ؟؟؟
    از کجا باید شروع کنم ؟؟
    ممنون

    پاسخ

نظر بدهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *