پیدا کردن کوتاه ترین مسیر بین دو نقطه در گراف – بازگشتی (Shortest path)

shortest distance4

پیدا کردن کوتاه ترین مسیر بین دو نقطه در یک گراف اهمیت خیلی زیادی در علوم مختلف مانند الگوریتم  ٫ ریاضی ٫ حمل و نقل ٫تجارت و …. دارد .

ده ها است که روی این مسیله کار شده است و  الگوریتم های متفاوت و با هزینه های مختلفی از آن ساخته شده است.

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

۱- الگوریتم به روش بازگشتی (Recursion) : که شامل تقسیم و حل و انواع روش های سرچ می شود. که در این پست ما فضای حالتمان را سرچ کرده ایم.

۲-  الگوریتم به روش برنامه نویسی پویا (Dynamic programming ) : معروف به فلوید

۳- الگوریتم به روش حریصانه  (Greedy ) :معروف به دایکسترا

ما در این پست الگوریتم بازگشتی را بررسی می کنیم و دو الگوریتم دیگر را در پست هایی جداگانه بررسی خواهیم کرد.

فرض کنید گراف زیر را دارید و می خواهید کوتاه ترین فاصله بین دو نقطه دلخواه را پیدا کنید ، ما حل سوال را با این مثال ادامه می دهیم:

graph همین طور که در بالا می بینید گراف دارای راس های v0 – v1- v2-v3-v4  است و راه های موجود بین راس ها با یال های که از آن راس خارج شده و به راس دیگر وارد شده است مشخص شده است و فاصله بین دو نقطه برابر با  عددی است که روی یال نوشته شده است.

ما برای پیدا کردن کوتاه ترین مسیر ها باید گراف را پردازش کنیم برای این کار گراف را به صورت ماتریس مجاورت در می آوریم ، ماتریس مجاورت گراف بالا به صورت زیر است :
فشذمثدر گراف قبل از راس سه به یک راهی وجود نداشت به همین خاطر در ماتریس بالا جاهایی که یالی وجود ندارد مقدار بینهایت (Infinity) گذاشتم .

فرض کنید می خواهیم کوتاه ترین مسیر از گره شماره ۲ را به گره شماره یک پیدا کنیم ، ابتدا گره ی مقصد  را که همان گره ی شماره یک است را در نظر می گیریم و شروع به عقب آمدن می کنیم تا به مبدا حرکت برسیم که اینجا گره شماره دو است  و از میان تمام راه های ممکن کوتاه ترین راه را  انتخاب می کنیم.

به ستون  زیر گره ی شماره یک نگاه کنید که  پنج خانه در زیرش قرار دارد که می گویند :

خانه اول : اگر از نود صفر به یک برویم طول مسیر برابر یک است

خانه دوم : اگر از نود یک به به نود یک برویم طول مسیر برابر صفر است

خانه سوم : اگر از نود دو به نود یک برویم طول مسیر بی نهایت است یعنی در واقع مسیری وجود ندارد

خانه چهارم : اگر از نود سوم به نود یک برویم هزینه بی نهایت است

خانه پنجم : اگر از نود چهار به نود یک برویم هزینه بی نهایت است

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

حالا صورت سوال را تغییر می دهیم:

   کوتاه ترین مسیر از نود دو به یک  = کوتاه ترین مسیر از نود دو به نود صفر + فاصله نود صفر تا نود یک

 که حالا همین کار را برای کوتاه ترین مسیر از نود دو به نود صفر می کنیم، همین طور که می بینید دو مسیر داریم که به نود صفر منتهی می شود یکی نود یک به نود صفر که طولی برابر نه دارد و دیگری مسیر نود چهار به نور صفر که طولی برابر سه دارد پس کوتاه تریم مسیر از نود دو به نود صفر اینگونه محاسبه می شود

کوتاه ترین مسیر از نود شماره دو به نود صفر = min( کوتاه ترین مسیر از نود دو به نود یک به علاوه نه ، ک.تاه ترین مسیر از نود شماره دو به نود شماره چهار به علاوه سه)

و همین کار را تا آخر ادامه می دهیم .

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

کد زیر تابع مربوط به حل بازگشتی مساله است

  int ** table :  ماتریس مجاورت است که به صورت اشاره گر به تابع فرستاده می شود

n : تعداد راس های موجود در گراف است

p: راس مبدا  است

q: راس مقصد است

z: تعداد راس های موجود در مسیر طی شده است

کد زیر یک مثال از کد بالاست که  دارای main  است و برای نمونه مثالی را که بررسی کردیم  را به تابع  فرستادم که مقدار یازده را به عنوان جواب بازگرداند:

 

۲۵ دیدگاه

  • واقعا از تون متشکرم.خیلی عالی بود.خدا خیرتون بده

  • خیلی راهتر هم میشه نوشتش و از مدل بازگشتی هم استفاده نکرد.
    من نوشتمش ولی خیلی روش فکر کردم.

    • فرهاد دلیرانی

      بله می شود – من به صورت بازگشتی نوشته ام تا در یک پست دیگر آن را داینامیک کنم و غیر بازگشتی بنویسم

  • سلام:)
    ممنون از پست مفیدتون 🙂
    اردر(O)این الگوریتم از چیه؟؟
    میشه بگید لطفا؟
    تشکر. (:

    • فرهاد دلیرانی

      سلام اوردر این برنامه خیلی بده بیشتر پیاده سازی کردم اینو برای دید پیدا کردن تا بعدا با روش های بهتری پیاده سازی اش کنیم 🙂 یک جورایی n! است !

      • سلام، ولی ۲ به توان n که خیلی کمتر از اینه که!!!
        یعنی بررسی تمامی حالات بهتر از روش بازگشتیه؟؟؟
        مگه میشه؟؟!! مگه داریم؟!! D:
        (:

        • فرهاد دلیرانی

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

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

          یک روش خوب روش دایکسترا است که هزینه ی مناسبی هم دارد

          • ممنون. 🙂
            «شما چطوری با دو به توان n می خواهید این مسیله را حل کنید؟»
            -منظورم راه حل نبود، باتوجه به این که بررسی تمام حالات یعنی غیر بهینه ترین ، این رو گفتم.
            –این روش دایکسترا هر قدر خوندم، نتونستم درکش کنم.
            –میشــه روش دایکسترا رو توضیح بدیــــد؟
            ممنون:)

          • فرهاد دلیرانی

            حتما این کار را می کنیم

  • سلام.:)
    خیلی ممنون. مفید بود واقعا.
    اردر این الگوریتم(Order) از چیه؟:?

    همچنان منتظر الگوریتم دایکسترا…

  • سلام من کدی رو که شما نوشتید رو وارد میکنم اما این خطاها رو میده کجا اشتباه میکنم؟؟لطفا کمکم کنید
    unresolved external symbol_main refrenced __tmainCRTstartup
    ۱unresolved external

  • با سلام ، ببخشید میشه کد برای کوتاهترین مسیر بین دو نود در گراف های بدون وزن هم بگذارید.

  • دست شما درد نکنه خیلی خوب بود فقط یک سوال داشتم اون اینه که به عنوان مثال اگربخواهیم بین گره ۴و۲ کوتاه ترین مسیر را بیابیم مقدار zرا چه عددی می بایست بگذاریم ایا امکان دارد که به اینجانب کمک نمایید با کمال تشکر

    • فرهاد دلیرانی

      z هنگام فراخوانی تابع همیشه صفر است .

      • با سلام خدا خیرتان دهد که پاسخ دادید خیلی گیر افتاده بودم حالا اگر بین همان گره شماره ۲و۴ که مقدار کوتاه ترین مسیر ۷ می شود بخواهیم کوتاه ترین مسیر را نمایش دهیم یعنی مسیر بهینه رابرنامه نشان دهدv2-v3-v4 یعنی برنامه به ما بگوید که از مسیر شماره دو تا مسیر شماره ۴ از گره شماره ۲ شروع می شود واز گره شماره ۳می گذرد وبه گره شماره ۴ ختم می شود که مقدار کوتاه ترین مسیر می شود ۷
        همچنین اگر بخواهیم بلند ترین مسیر را بیابیم چه تغییری در کل برنامه ایجاد می شود من خیلی دنبال برنامه بلند ترین مسیر گشتم ولی متاسفانه موفق به یافتن ان نشدم خیلی خیلی از جنابعالی معذرت می خواهم که این قدر سوال پرسیدم ووقت شما را گرفتم اگر امکان دارد پاسخ این دوسوال اینجانب را هم بدهید باتشکر از وقتی که می گذارید و پاسخ می دهید خدا خیرتان دهدخداوکیلی کمکم کنید

  • سلام:خدایش دستت درد نکنه ایول داری اما من مفهومه #define inf 2000000000 رو خوب نفهمیدم:میشه کمک کنید

    • فرهاد دلیرانی

      من مسیر ها رو با یک گراف نشان داده ام که ممکن است بین دو نقطه از گراف هیچ مسیری نیاشد که آن را با inf نشان داده ام.

  • دمت گرم خیلی سالاری

نظر خود را بنویسید.

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