المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر

ترکیبیات,برنامه نویسی,گراف,الگوریتم , و کلا کامپیوتر

المپیاد کامپیوتر

الگوریتم های گراف

يكشنبه, ۱۳ اسفند ۱۳۹۱، ۱۱:۰۹ ب.ظ

به نام خدا

سلام و درود .
در این پست قصد داریم یکی از مسائل مهم توی گراف و الگوریتم های گراف به نام
« کوتاه ترین مسیر » را بررسی کنیم.
لطفا برای مطالعه ی بیشتر به ادامه مطلب مراجعه نمایید.



همان طور که گفته شد قرار است الگوریتم های کوتاه ترین مسیر را در یک گراف تشریح کنیم.

کتاب « clrs » این بحث را به دو قسمت تقسیم کرده است :
 ۱-الگوریتم کوتاه ترین مسیر ها از مبدا واحد

 ۲-الگوریتم کوتاه ترین مسیر ها از هر راس به راس دیگر


"کوتاه ترین مسیر ها از مبدا واحد " :
اولین الگوریتمی که بررسی خواهیم کرد ، الگوریتم « دایکسترا » نام دارد.

این الگوریتم یکی از الگوریتم‌های پیمایش گراف است که مسئلهٔ کوتاه‌ترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که یال با وزن منفی ندارند، حل می‌کند و در نهایت با ایجاد درخت کوتاه‌ترین مسیر، کوتاه‌ترین مسیر از مبدأ به همهٔ رأس‌های گراف را به دست می‌دهد.

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

به نظر من بهترین راه برای یادگیری این الگوریتم ، بهره گیری از شکل زیر است :

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

بقیه الگوریتم هارو توی پست های بعدی بررسی خواهیم کرد.

نظرات (۴)

واقعا وبلاگ عالی داره میشه برای آموزش !!!
هیچ وقت دلسرد نشو... اینجور پیش بری یک وبلاگ شاخ میشه
پاسخ:
واقعا انگیزمون بیشتر میشه وقتی این نظر هارو می خونیم.چشم سعی می کنم زودتر مطلب بذارم ممنون
salam
matalebeton kheili khobe 
lotfan gozashtan javabaie project euler ro edame bedin
ba tashakor
پاسخ:
ممنون از نظرتون.
چشم حتما.
آخه یه چند روزیه به خاطر مدرسه سرم شلوغه حتما در اسرع وقت ادامه می دم!!
بازم ممنون!! :D
سلام.میشه توضیح بدید گراف چیه؟اینا یعنی چی؟من اول دبیرستانم.اصلا گراف برای المپیاد کامپیوتر لازمه؟لطفا سریع پاسخ بدید.ممنون.
سلام 
می خواستم ازتون خواهش کنم که مباحث گراف رو به صورت متنی و به همراه شکل توضیح بدین چون این تنها پستی از گراف بود که من فهمیدم و اون هم به این دلیل بود که قبلا خونده بودمش 
ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی