توضیح کامل الگوریتم دایکجسترا به همراه کد به زبان

کد الگوریتم دیکسترا همراه توضیحات و پیچیدگی زمانی
 
در نظریه گراف، الگوریتم دیکسترا (به انگلیسی: Dijkstra’s algorithm)‏ یکی از الگوریتم‌های پیمایش گراف است که توسط دانشمند هلندی علوم رایانه، اِدْسْخِر دِیْکْسْترا در سال ۱۹۵۹ ارایه شد.
روند الگوریتم دیکسترا مطابق زیر می باشد :
۱- انتخاب راس مبدا
۲- مجموعه ی S ، شامل رئوس گراف ، معین می شود. در شروع، این مجموعه تهی بوده و با پیشرفت الگوریتم، این مجموعه رئوسی که کوتاه ترین مسیر به آن ها یافت شده است را در بر می گیرد.
۳- راس مبدا با اندیس صفر را در داخل S قرار می دهد.
۴- برای رئوس خارج از S ، اندیسی معادل ، طول یال + اندیس راس قبلی ، در نظر می گیرد . اگر راس خارج از مجموعه دارای اندیس باشد، اندیس جدید کمترین مقدار از بین اندیس قبلی و طول یال + اندیس راس قبل ، می باشد.
۵- از رئوس خارج مجموعه، راسی با کمترین اندیس انتخاب شده و به مجموعه ی S اضافه می گردد.
۶- این کار را دوباره از مرحله ی ۴ ادامه داده تا راس مقصد وارد مجموعه ی S شود.
در پایان اگر راس مقصد دارای اندیس باشد، اندیس آن نشان دهنده ی مسافت بین مبدا و مقصد می باشد. در غیر این صورت هیچ مسیری بین مبدا و مقصد موجود نمی‌باشد.
همچنین برای پیدا کردن مسیر می توان اندیس دیگری برای هر راس در نظر گرفت که نشان دهنده ی راس قبلی در مسیر طی شده باشد. بدین ترتیب پس از پایان اجرای الگوریتم، با دنبال کردن رئوس قبلی از مقصد به مبدا، کوتاه ترین مسیر بین دو نقطه نیز یافت می شود.
ر حین اجرای الگوریتم دو چیز به طور ضمنی نگهداری می‌شود. یکی مجموعهٔ  از رأس‌هایی که وزن کوتاه‌ترین مسیر از مبدأ تا آن‌ها مشخص شده و دیگری دنبالهٔ  که برای هر رأس  ، مقدار  برابر وزن کوتاه‌ترین مسیر از مبدأ تا  است به شرطی که تمام رأس‌های این مسیر به جز  از رئوس داخل  باشند.  در ابتدا تهی و مقادیر  برای همهٔ رئوس به غیر از مبدأ بی‌نهایت است و مقدار آن برای مبدأ صفر گذاشته می‌شود. الگوریتم در هر مرحله رأسی خارج  را که  برای آن کمترین است انتخاب و به مجموعهٔ  اضافه می‌کند و سپس مقادیر  را برای رئوس همسایهٔ آن رأس به‌روز می‌نماید. در صورتی که نیاز به تشکیل درخت کوتاه‌ترین مسیر باشد، الگوریتم می‌بایست دنبالهٔ  را که  پدر رأس  در درخت کوتاه‌ترین مسیر است، به همراه دنبالهٔ  به‌روز کند.
پیچیدگی زمانی
در ساده‌ترین پیاده‌سازی الگوریتمِ دیکسترا، داده‌ها در آرایه یا لیست پیوندی ذخیره می‌شوند که بدین ترتیب مینیمم مقدار  برای رئوس خارج  با الگوریتمی خطی یافت می‌شود. در این حالت پیچیدگی زمانی  خواهد بود، چراکه در گراف بدون جهت هر یال دقیقاً دوبار و در گراف جهت‌دار هر یال دقیقاً یک بار پیمایش می‌شود و هم‌چنین پیدا کردن مینیمم،  زمان می‌خواهد که این مینیمم پیدا کردن  بار تکرار خواهد شد. برای گراف‌های پراکنده (یعنی گراف‌هایی که خیلی کمتر از مجذور  یال دارند) الگوریتم دیکسترا با نگهداری گراف در فهرست مجاورت و استفاده از صف اولویت‌دار (Priority-Queue) (برای پیدا کردن مینیمم) با پیچیدگی زمانی  پیاده‌سازی می‌شود. در صورت استفاده از نگهدارندهٔ فیبوناتچی (Fibonacci heap) به جای صف اولویت‌دار، پیچیدگی زمانی با تحلیل جمعی (Amortized analysis) به  بهبود می‌یابد.
کاربردها
ز جمله مهمترین کاربرد های این روش می توان به محاسبه ی کوتاه ترین فاصله ی دو نقطه در یک شهر از طریق راه های زمینی اشاره نمود. برای محاسبه ی کوتاه ترین مسیر بین دو نقطه باید نقاط مورد نظر در یک نقشه را علامت گذاری کرد و با استفاده از مشخصات نقاط(طول، عرض و ارتفاع) فاصله ی دو نقطه را در هر بار عملیات محاسبه نمود.توجه داریم که در ترافیک سرعت خودرو ها به شدت پایین آمده و این امر می تواند در انتخاب کوتاه ترین مسیر تاثیر گذار باشد چرا که ممکن است بین دو نقطه a,b راه های ۱و۲ موجود باشد که راه ۱ اتوبان و از خارج شهر و راه ۲ از داخل شهر عبور می کند. فرض کنید فاصله ی a,b از طریق راه ۱ حدود ۱۰ کیلومتر و از طریق راه ۲ حدود ۷ کیلومتر باشد ولی راه ۲ علی رقم فاصله ی کمتر دارای ترافیک سنگین است در نتیجه می توان انتظار داشت که در ساعات شلوغی استفاده از راه ۱ بهتر باشد.از آن جا که اساس محاسبات در این روش بر پایه ی فاصله بین دو نقطه است می توان کاهش سرعت را با افزایش فواصل هم ارز نمود چرا که اگر رابطه ی سرعت و فاصله را خطی در نظر بگیریم (D=V.T)تاثیر کاهش سرعت و افزایش مسافت یکسان است.از این رو لازم است تا ضرایب تعدیلی در فواصل بین نقاط ضرب شده و این مسائل را در محاسبات لحاظ کرد. از جمله مهم ترین این ضرایب می توان به ۳ مورد زیر اشاره نمود: ۱-ضریب ترافیک و شلوغی ۲-ضریب عرض معبر ۳-ضریب شیب که نشانگر افت سرعت در سر بالایی هااست. گرچه تعیین این ضرایب برای نقاط مختلف شهر نیازمند کارشناسان متخصص ترافیک و بررسی های آماری دقیق می باشد ولی می توان انتظار داشت که در اکثر موارد این ضرایب بین مقادیر ۱ تا ۲ بسته به شرایط تغییر کنند.

 
الگوریتم های مسیر یابی در شبکه و شبکه های GSM

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

سیکل مسیریابی به شرح زیر دنبال باید گردد:
تولید مسیر 
مسیرها را مطابق با اطلاعات جمع آوری و توزیع شده از وضعیت شبکه تولید می کند.
انتخاب مسیر 
مسیرهای مناسب را بر اساس اطلاعات وضعیت شبکه انتخاب می کند.
ارسال داده به جلو : ترافیک کاربر را در امتداد مسیر انتخاب شده به جلو ارسال می کند.
نگهداری مسیر 
که مسئول نگهداری مسیر انتخاب شده می باشد. 
تعریف مسیر یابی 
مکانیزمی است که به وسیله آن ترافیک کابر به صورت مستقیم یا با واسطه شبکه از مبدا به مقصد هدایت شود.
 پارامترهای مسیر یابی 
تعداد گام
تاخیر
توان عملیاتی
 نرخ ریزش
 استحکام
و هزینه و ...
دسته بندی الگوریتم های مسیر یابی
ایستا 
الگوریتمهایی که هیچ اعتنایی به شرایط توپولوژی شبکه و ترافیک ندارند.
پویا 
الگوریتمهایی که طبق آخرین شرایط توپولوژی شبکه و ترافیک مسیر یابی می کنند.
 مسیریابی
این فرآیند شامل انتخاب مسیر در شبکه‌است و می‌تواند در ارسال داده‌ها نقش داشته باشد. مسیریابی برای چندین شبکه عملی است. مانند شبکه تلفن، اینترنت و انتقال. این مسیریابی می‌تواند عامل ارسال بسته‌های منطقی از مبدا به مقصد باشد. ابزار سخت‌افزاری به نام مسیر یاب، پل، دریچه، دیوار آتش و سوئچ معروف هستند. کامپیوترهایی که کارت شبکه دارنند می‌توانند بسته‌ها را ارسال کنند. این روند عامل ارسال براساس جداول می‌باشد و می‌تواند ثبت‌ها را در مقصد نگه داری کند. تشکیل این جداول در حافظه عملی است. این مسیریابی به طول کل عامل متضاد با تولید یک ارتباط می‌باشد. آدرس شبکه نیز به شکل خاص طراحی می‌شود. چون آدرس ساختار یافته می‌تواند در ورودی جدول استفاده شود یک گروه ابزار وجود دارند که می‌توانند آدرس‌ها را تغییر دهند علی رغم این که محیط موضعی است.
الگوریتم مسیریابی مناسب است که 6 ویژگی ذیل  را داشته باشد:
صحت عملکرد
سادگی
قابلیت اطمینان
پایداری
عدالت
بهینگی
بدیهی است که الگوریتمی بهتر است که صحت عملکرد بالایی داشته باشد و در عین حال ساده باشد، اما چه الگوریتمی قابلیت اتکای خوبی دارد؟ الگوریتمی مناسب است که در گذشت زمان، با تغییر نرم‌افزارها و سخت‌افزارهای شبکه و تغییر پروتکل‌ها، همچنان مسیریابی درستی ارائه دهد. همچنین مهم است که بعد از یک مدت زمان خاص، الگوریتم مسیریابی به حالتی پایدار برسد و همزمان با آن، مسیریابی بهینه‌ای داشته باشد و در ارسال بسته‌ها عدالت را رعایت کند.
الگوریتم سیل‌آسا
در این روش، هر بسته ورودی که به یک مسیریاب می‌رسد، از تمام کانال‌های خروجی مسیریاب خارج می‌شود. بدین‌ترتیب تعداد زیادی بسته تکراری وجود خواهد داشت و عملا میزان آن بی‌نهایت خواهد بود. بنابراین باید برای خاتمه این تعداد بسته‌ها راهکاری اندیشید. راهکارهای پیشنهادی برای این روش، استفاده از یک شمارنده گام است. بدین صورت که در سرآیند(9) هر بسته یک شمارنده بگذاریم و در هر گام یک شماره از آن کم کنیم تا به صفر برسد و بسته حذف شود.
در این صورت مبدا باید طول شبکه را بداند و در بدترین حالت، طول شبکه را طولانی‌ترین فاصله در نظر بگیرد.یک روش دیگر، استفاده از حالتی نیمه‌منطقی است. مسیریاب در این روش، بسته را به تمام کانال‌های خروجی نمی‌فرستد. بلکه به کانال‌هایی می‌فرستد که احتمال رسیدن آنها به مقصد وجود دارند. در این صورت اگر بسته‌ای به سمت غرب بخواهد برود، نبایستی از کانال‌های شرقی مسیریاب استفاده کرد، مگر اینکه مسیریاب از ساختار شبکه مطلع باشد و بداند که این کانال‌ها به کجا منتهی می‌شوند.
الگوریتم سیل‌آسا به جز چند مورد خاص، از جمله سیستم‌های توزیعی که عملکردهای موازی در آنها نیاز است، کاربرد علمی دیگری ندارد.
الگوریتم بردار فاصله
در این الگوریتم از الگوریتم bellman – ford استفاده می‌شود و می‌توان یک رقم و هزینه را برای هر لینک بین گروه‌های شبکه تعیین نمود. گره‌ها می‌توانند اطلاعات را از A به B بفرستند. و این از طریق مسیر کم هزینه عملی است. این الگوریتم خیلی ساده عمل می‌کند. ابتدا باید راه اندازی انجام شود.
بخش‌های همجوار نیز باید شناخته شوند. هر گره به طور منظم می‌تواند هزینه کل را به مقصد بفرستد. گره‌های همجوار به بررسی اطلاعات و مقایسه یافته‌ها می‌پردازند. این عامل پیشرفت در جداول مسیریابی خواهد بود. تمام گره‌ها بهترین حلقه را کشف می‌کنند.
وقتی یکی از گره‌ها کاهش یافت آنهایی که در همجوار هستند می‌توانند ورودی را خالی کنند و به مقصد بروند. به این طریق اطلاعات جدول ارائه خواهند شد. آنها می‌توانند اطلاعات را در اختیار گره‌های مجاور قرار دهند. در نهایت اطلاعات ارتقا یافته دریافت می‌شوند و مسیر جدید شناخته خواهد شد.
در این روش، مسیریاب‌ها در خود جدولی (برداری) ذخیره می‌کنند با عنوان بردار فاصله که در آن بهترین فاصله تا هر مسیریاب دیگر در شبکه را ذخیره می‌کنند. در این صورت، تصمیم‌گیری بهتری هنگام مسیریابی اتخاذ می‌شود. این جدول‌ها با اطلاعات مسیریاب‌های همسایه به‌روز می‌شود. هر یک از عناصر این جدول‌ها یک درایه دوبخشی دارند که یکی از آنها نشانگر خط خروجی مناسب برای رسیدن به مسیریاب مورد نظر و دیگری تخمین فاصله زمانی تا آن مسیریاب است.
الگوریتم حالت لینک
مسیریابی بردار فاصله مسیریابی خوبی بود و حتی در شبکه آرپانت(10) تا سال 1979 نیز عملیاتی بود، اما دو مشکل اساسی داشت. نخست اینکه معیار تاخیر در این الگوریتم، طول صفی از مسیریاب‌ها بود و دوم اینکه پهنای باند هر یک از خطوط در محاسبات دخالت داده نمی‌شد. بنابراین حتی اگر جای فاصله را با پهنای باند در جداول مسیریاب عوض می‌کردند، زمان همگرایی این مسیریاب‌ها به یک نتیجه درست، به بی‌نهایت میل می‌کرد.
وقتی از این الگوریتم استفاده می‌شود هر گره از داده‌های اصلی در الگوی شبکه‌ای استفاده خواهد نمود. در این شرایط تمام گره‌ها وارد شبکه می‌شوند و اطلاعات با یکدیگر در ارتباط خواهند بود. این گره‌ها می‌توانند اطلاعات را وارد نقشه کنند. به این طریق هر مسیریاب تعیین کننده مسیر کم هزینه به سمت دیگر گره‌ها خواهد بود. در نهایت یک الگوریتم با کوتاهترین مسیر به وجود می‌آید. این درخت می‌تواند ماحصل ترکیب این گره‌ها باشد. در این شرایط بهتر است این درخت در طراحی جدول استفاده شود و حلقه بعدی گره نیز مشخص گردد.

الگوریتم حالت لینک، ساده است و می‌توان به‌صورت زیر آن را بیان کرد:
هر مسیریاب باید همسایه‌های خود را شناسایی کرده و آدرس‌های شبکه‌شان را داشته باشد.
. میزان هزینه و یا تاخیر همسایه‌های خود را بداند.
اطلاعاتی که از همسایه‌ها بدست آورده است را برای تمام مسیریاب‌های دیگر بفرستد.
کوتاه‌ترین مسیر برای رسیدن به دیگر مسیریاب‌ها را محاسبه کند.
شناسایی همسایه‌ها به‌این صورت انجام می‌گیرد که پس از راه‌اندازی مسیریاب )بوت‌شدن) یک بسته سلام(11) به تمام همسایه‌ها ارسال می‌شود. مسیریاب‌های همسایه مشخصات خود را برای این مسیریاب می‌فرستند.
برای تخمین هزینه و تاخیر همسایه‌ها، از بسته‌ای به نام Echo استفاده می‌شود. وقتی مسیریاب این بسته را برای همسایه می‌فرستد، آن مسیریاب فورا باید پاسخ آن را ارسال کند، پس از محاسبه زمان رفت و برگشت و تقسیم آن بر عدد 2، میزان نسبی تاخیر بدست می‌آید. سپس این اطلاعات را در قالب بسته‌ای برای دیگر مسیریاب‌ها ارسال می‌کند تا آنها نیز از وضعیت این مسیریاب مطلع باشند.
بدین ترتیب هر مسیریاب با دریافت اطلاعات کامل از تمام مسیریاب‌های شبکه، می‌تواند همواره بهترین مسیر را انتخاب کند و کوتاه‌ترین مسیر ممکن را برای ارسال بسته‌ها در نظر بگیرد و شش شرط یک الگوریتم را رعایت کند. 
پروتکل بردار مسیر
مسیریابی حالت لینک و بردار فاصله پروتکل غالب می‌باشند. آنها از سیستم ناشناخته درونی استفاده می‌نمایند ولی بین سیستم‌های ناشناخته نمی‌باشند. این دو نوع پروتکل می‌توانند در شبکه‌های بزرگ مسیریابی شوند و به این طریق مسیریابی درون حوزه‌ای عملی خواهد شد. مسیریابی حالت لینک می‌تواند اطلاعات زیادی را وارد جدول کند، این عامل تشکیل ترافیک بزرگ می‌باشد. مسیریابی بردار برای درون حوزه‌ها استفاده می‌شود و مانند بردار راه دور است. در این جا یک گره در هر سیستم ناشناخته وجود دارد که به عنوان کل سیستم عمل خواهد کرد. این گره از نوع سخنگو است. این گره جدول مسیریابی را تولید کرده و به گره‌های همجوار می‌فرستد. در این شرایط فقط گره‌های سخنگو در هر سیستم با یکدیگر ارتباط برقرار می‌کنند. این گره می‌تواند در مسیر پیش رود و در سیستم ناشناخته فعال شود.
مقایسه الگوریتم مسیریابی
پروتکلهای مسیریابی بردار-فاصله در شبکه‌های کوچک، ساده و کارآمد بوده و به مدیریت اندکی نیازمند هستند. با این وجود آلگوریتمهای اولیه بردار-فاصله از نظر مقیاس پذیری خوب نیستند و قابلیتهای همگرایی آنها ضعیف است که این امر منجر به توسعه الگوریتمهای پیچیده تر با مقیاس پذیری بهتر جهت شبکه‌های بزرگ شده‌است. بدین جهت اغلب پروتکلهای مسیریابی درونی از پروتکل‌های وضعیت لینک مانند OSPF و IS-IS استفاده می‌کنند. یکی از توسعه‌های اخیر در پروتکل‌های بردار فاصله، قابلیت بدون حلقه یا loop-free می‌باشد که بطور مثال در EIGRP پیاده سازی شده‌است. این پروتکل ضمن داشتن تمام قابلیتهای پروتکلهای بردار فاصله، مشکل count-to-infinity را حل کرده و از این جهت زمان همگرایی پروتکل را بهبود بخشیده‌است.
انتخاب مسیر
یک اصل مسیریابی توسط آلگوریتم مسیریابی معرفی شده‌است که تعیین کننده عملکرد آنها است. این اصول می‌توانند مربوط به پهنای باند، تاخیر، تعداد حلقه‌ها، هزینه مسیر بار و MTU، اعتبار پذیری و هزینه ارتباطی باشند. این جداول عامل ذخیره بهترین مسیرها هستند ولی پایگاه‌های حالت لینک و توپولوژیکی نیز نقش ذخیره دارند. وقتی اصل مسیر یابی در یک پروتکل خاص استفاده شود مسیریاب‌های چند پروتکلی از یک روش اکتشافی خارجی استفاده می‌کنند و به این ترتیب مسیرهای آموخته شده را انتخاب خواهند کرد. به عنوان مثال مسیریاب Cisco یک ارزش به صورت فاصله اجرایی دارد. در این فاصله مسیرها می‌توانند پروتکل معتبر تولید کنند.
الگوریتم کوتاه‌ترین مسیر
ساده‌ترین روش مسیریابی، روش کوتاه‌ترین مسیر است. هدف اصلی از این الگوریتم، این است که گراف‌ زیرشبکه را طوری تشکیل بدهیم که در آن هر گره را یک مسیریاب فرض کنیم و هر یال را یک خط ارتباطی میان دو مسیریاب. در این حالت، هر یال یک وزن خواهد داشت و با توجه به الگوریتم کوتاه‌ترین مسیر دایجسترا(8) می‌توان کوتاه‌ترین مسیر ممکن را محاسبه کرد.
من جمله مسائل اصلی در تئوری شبکه های هندسی در جی.آی.اس مسئله مسیریابی یعنی یافتن کوتاهنرین مسیر بین دو نقطه است. در سال های اخیر، با استفاده از متدهای هوش مصنوعی روشهای مدرنی برای پیدا کردن کوتاه ترین مسیر ارایه شده است. در گذشته برای حل این مسیله الگوریتم هایی مانند دیکسترا، A*، بلمن فورد، فلوید وارشال، جانسون و … ارایه شده است. این الگوریتم ها از روش های کلاسیک برای پیدا کردن کوتاه ترین مسیر می باشند. در سال های اخیر استفاده از روش های هوش مصنوعی مانند الگوریتم های ژنتیک در تعیین بهترین مسیر اهمیت خاصی یافته است.
توزیع توپولوژی
شبکه‌های کوچک دارای جداول دستی هستند. شبکه‌های بزرگ توپولوژی پیچیده دارند. و به سرعت تغییر می‌کنند. به این طریق ساختار جداول غیرقابل طراحی خواهد شد. بیشتر این شبکه‌های تلفنی کلیدی (pstn) از این جداول استفاده می‌کنند و نقایص در مسیر این سیستم شناخته و رفع خواهند شد. مسیر یابی دینامیکی تلاشی برای حل مسئله و تشکیل ساختار خودکار جداول است. این براساس اطلاعات پروتکل مسیریابی عملی است. به این طریق شبکه‌ها از هر نقص ایمن خواهند شد. این دینامیک در اینترنت نقش فعال دارد. طراحی پروتکل‌ها به یک تماس ماهرانه نیاز دارد. نباید فرض کرد که شبکه سازی به نقطه اتوماسیون کامل رسیده‌است.
طراحی الگوریتم
اصول عملکرد
روترها از الگوریتمهای مسیریابی،برای یافتن بهترین مسیر تا مقصد استفاده مینمایند هنگامی که ما در مورد بهترین مسیر صحبت میکنیم،پارامترهایی همانند تعداد hopها (مسیری که یک بسته از یک روتر دیگر در شبکه منتقل میشود).زمان تغییر و هزینه ارتباطی ارسال بسته را در نظر میگیریم.
مبتنی بر اینکه روترها چگونه اطلاعاتی در مورد ساختار یک شبکه جمع آوری مینمایند و نیز تحلیل آنها از اطلاعات برای تعیین بهترین مسیر،ما دو الگوریتم مسیر یابی اصلی را در اختیار داریم:الگوریتم مسیر یابی عمومی و الگوریتمهای مسیر یابی غیر متمرکز.
در الگوریتم های مسیر یابی غیر متمرکز،هر روتر اطلاعاتی در مورد روترهایی که مستقیما به آنها متصل میباشند در اختیار دارد. در این روش هر روتر در مورد همه روتر های موجود در شبکه،اطلاعات در اختیار ندارد.این الگوریتمها تحت نام الگوریتمهای (DV (distance vectorمعروف هستند.در الگوریتمهای مسیریابی عمومی،هر روتر اطلاعات کاملی در مورد همه روترهای دیگر شبکه و نیز وضعیت ترافیک شبکه در اختیار دارد.این الگوریتمها تحت نام الگوریتمهای(LS(Link state معروف هستند.
الگوریتمهای LS
در الگوریتم های LS ،هر روتر می بایست مراحل ذیل را به انجام رساند:
روترهای را که به لحاظ فیزیکی به آنها متصل میباشد را شناسایی نموده و هنگامی که شروع به کار میکند آدرسهایIP آنها بدست آورد. این روتر ابتدا یک بسته HELLO را روی شبکه ارسال میکند. هر روتری که این بسته را دریافت میکند از طریق یک پیام که دارای آدرس IP خود این روتر میباشد به پیام HELLO پاسخ میدهد.
زمان تاخیر مربوط به روترهای مجاور را اندازه گیری نماید(یا هر پارامتر مهم دیگری از شبکه همانند ترافیک متوسط)برای انجام این کار ،روترها بسته های echo را روی شبکه ارسال میکنند. هر روتری که این بسته ها را دریافت میکند با یک بسته echo reply به آن پاسخ میدهد.
با تقسیم زمان مسیر رفت و برگشت به دو،روترها میتوانند زمان تاخیر را محاسبه کنند.(زمان مسیر رفت و برگشت،سنجشی از تاخیر فعلی روی یک شبکه میباشد)توجه داشته باشید که این زمان شامل زمانهای ارسال و پردازش میباشد.
اطلاعات خود را در مورد شبکه،برای استفاده سایر روترها منتشر نموده و اطلاعات روترهای دیگر را دریافت کند.
در این مرحله همه روترها دانش خود را با روتر های دیگر به اشتراک گذاشته و اطلاعات مربوط به شبکه را با یکدیگر مبادله میکنند.
با این روش هر روتر میتواند در مورد ساختار و وضعیت شبکه اطلاعات کافی بدست آورد.با استفاده از این الگوریتم مناسب،بهترین مسیر بین هر دو گره از شبکه راشناسایی کند.در این مرحله،روترها بهترین مسیر تا هر گره را انتخاب میکنند.آنها این کار را با استفاده از یک الگوریتم همانند الگوریتم کوتاهترین مسیر Dijkstra انجام میدهند.در این الگوریتم،یک روتر مبتنی بر اطلاعاتی که از سایر روترها جمع آوری نموده است،گرافی از شبکه را ایجاد مینماید.این گراف مکان روترهای موجود در شبکه و نقاط پیوند آنها را به یکدیگر نشان میدهد.
هر پیوند با یک شماره به نام Costیاweight مشخص میشود.این شماره تابعی از زمان تاخیر،متوسط ترافیک و گاهی اوقات تعداد hopهای بین گره ها میباشد.برای مثال اگر دو پیوند بین یک گره و مقصد وجود داشته باشد،روتر پیوندی با کمترین Weight را انتخاب میکند.
الگوریتم Dijkstra دارای مراحل ذیل می باشد:
روتر گرافی از شبکه را ایجاد نموده و گره های منبع و مقصد(برای مثال V1 وV2)را شناسایی میکند.سپس یک ماتریس به نام ماتریس adjacency را میسازد.در این ماتریس یک مختصه مبین Weight میباشد.برای مثال[i,j]،وزن یک پیوند بین Viو Vj میباشد.در صورتی که هیچ پیوند مستقیمی بین Vi وVj وجود نداشته باشد این وزن (ویت) بصورت infinity در نظر گرفته میشود.
روتر یک مجموعه رکورد وضعیت را برای هر گره روی شبکه ایجاد مینماید این رکورد دارای سه فیلد میباشد:
فیلد Predecessor:اولین فیلدی که گره قبلی را نشان میدهد.
فیلد Length:فیلد دوم که جمع وزنهای از منبع تا آن گره را نشان میدهد.
فیلد Label:آخرین فیلد که وضعیت گره را نشان میدهد.هر گره میتواند دارای یک مود وضعیت باشد:tentative یا permanent
روتر،پارامترهای مجموعه رکورد وضعیت برای همه گره ها را آماده سازی اولیه نموده و طول آنها را در حالت infinity و Labelآن را در وضعیت tentative قرار میدهد.
روتر،یک گره T را ایجاد میکند.برای مثال اگر V1 میبایست گره T منبع باشد،روتر برچسب V1را در وضعیت permanent قرار میدهد.هنگامی که یک Label به حالت permanent تغییر میکند دیگر هرگز تغییر نخواهد کرد. یک گره T در واقع یک agent میباشد.
روتر،مجموع رکورد وضعیت مربوط به همه گره های Tentative را که مستقیما به گره T منبع متصل هستند،روز آمد مینماید.
روتر همه گره های Tentative را بررسی نموده و گرهای را که وزن آن تا V1 کمترین مقدار را دارد انتخاب میکند.سپس این گره،گره Tمقصد خواهد بود
اگر این گره،V2 نباشد(گره مقصد)روتر به مرحله 5باز میگردد.
اگر این گره V2 باشد،روتر گره قبلی آن را از مجموع رکورد وضعیت استخراج نموده و این کار را انجام میدهد تا به V1 برسد،این فرست از گره ها،بهترین مسیر از V1تاV2را نشان میدهد.
این مراحل بصورت یک فلوچارت در شکل نشان داده شده است ما از این الگوریتم بعنوان یک مثال در ادامه مقاله استفاده خواهیم نمود.
مثال
الگوریتم Dijkstra
در اینجا ما میخواهیم بهترین مسیر بین گره های A و E را پیدا کنیم همانطور که میبینید 6 مسیر بین A و E وجود دارد.(ACDBE ،ABDCE ، ACDE، ABDE، ACE،ABE)و واضح است که ABDEبهترین مسیر میباشد زیرا کمترین وزن را دارد اما همیشه به این سادگی نیست و برخی موارد پیچیده وجود دارد که در آن ما مجبوریم از الگوریتم هایی برای یافتن بهترین مسیر استفاده کنیم.
همانطور که در تصویر ذیل مشاهده میکنید،گره منبع(A)بعنوان گره Tانتخواب شده و بنابراین برچسب آن، Permanent میباشد. (ما گره های Permanent را با دایره های تو پر و گره های Tرا با یک پیکان نشان میدهیم)در این مرحله شما میبینید که مجموع رکورد وضعیت گره های Tentative که مستقیما به گره(T (C،Bمتصل شده اند،تغییر یافته است.
همچنین از آنجایی که گره Bکمترین وزن را دارد،بعنوان گره T انتخاب شده و برچسب آن به حالت Permanent تغییر کرده است.در این مرحله همانند مرحله قبل دو مجموعه رکورد وضعیت گره هایی که Tentative دارای اتصال مستقیم به گره T میباشد(E،D)تغییر کرده است.
همچنین از آنجایی که گره D وزن کمتری دارد،بعنوان گره T انتخاب شده و برچسب آن به وضعیت Permanent تغییر کرده است.در این مرحله ما هیچ گره Tentative نداریم بنابراین فقط گره T بعدی را شناسایی میکنیم.از آنجایی که Eدارای کمترین وزن میباشد بعنوان گرهTانتخاب میشود.
E گره مقصد بوده بنابر این کار ما در اینجا تمام میشود.اکنون ما کار شناسایی مسیر را به انتها رسانده ایم.گره قبلی Eگره D،گره B میباشد و گره قبلی B،گره A میباشد.بنابر این بهترین مسیر ABDE است در این مورد وزن کل مسیر،(1+2+1)4میباشد.با وجودی که این الگوریتم بخوبی کار میکند اما آنقدر پیچیده است که زمان پردازش آن برای روتر طولانی بوده و راندمان شبکه را کاهش میدهد.همچنین اگر یک روتر اطلاعات غلطی را به روترهای دیگر بدهد،همه تصمیمات مسیر یابی نادرست خواهد بود.
الگوریتمهای DV
الگوریتمهای DVبا نامهای الگوریتمهای مسیریابی Bellman-Ford و ford-fulkerson نیز یاد میشوند.در این الگوریتمها،هر روتر دارای یک جدول مسیریابی میباشد که بهترین مسیر تا هر مقصد را نشان میدهد.
یک گراف معمولی و جدول مسیریابی مربوط به روتر G .همانطور که در جدول مشاهده میکنید،اگر روتر G بخواهد بسته هایی را به روتر D ارسال کند،میبایست آنها را به روتر H ارسال نماید.هنگامی که بسته ها به روتر H رسیدند،این روتر جدول خود را بررسی نموده و روی چگونگی ارسال بسته ها به D تصمیم گیری می کند.

Destination    Weight    Line
A    8    A
B    20    A
C    28    I
D    20    H
E    17    I
F    30    I
G    18    H
H    12    H
I    10    I
J    0    -
K    6    K
L    15    K

در الگوریتمهای DV،هر روتر میبایست مراحل ذیل را انجام دهد
وزن لینکهای مستقیما متصل به آن را اندازه گرفته و این اطلاعات را در جدول خود ذخیره کند.
در یک دوره زمانی خواص،روتر جدول خود را به روترهای مجاور ارسال نموده و جدول مسیریابی هر یک از روترهای مجاور خود را دریافت میکند.
مبتنی بر اطلاعات بدست آمده از جداول مسیریابی روترهای مجاور،جدول خود را روز آمدسازی مینماید.
یکی از مهمترین مشکلات،هنگام کار با الگوریتمهای DV،مشکل Count to infinity اجازه بدهید این مشکل را با ذکر یک مثال روشن کنیم.
همانطور که در قسمت ذیل نشان داده شده است یک شبکه را در ذهن خود تصور کنید.همانطور که در این جدول میبینید،فقط یک پیوند بین A و سایر بخشهای شبکه وجود دارد.در اینجا شما میتوانید،این گراف و جدول مسیریابی همه گره ها را مشاهده کنید:

    A    B    C    D
A    0,-    1,A    2,B    3,D
B    1,B    0,-    2,C    3,D
C    2,B    1,C    0,-    1,C
D    3,B    2,C    1,D    0,-

اکنون تصور کنید که پیوند بین A و B قطع شود.در این هنگام، B جدول خود را تصحیح میکند بعد از یک مدت زمان خاص،روترها جداول خود را مبادله نموده و بنابراین B جدول مسیریابی C را دریافت میکند. از آنجایی که C نمیداند چه اتفاقی برای پیوند بین A و B رخ داده است این اطلاعات را حفظ میکند.B این جدول را دریافت نموده و فکر میکند که یک پیوند جداگانه بین Cو A وجود دارد،بنابراین جدول خود را تصحیح نموده مقدار infinity را به 3 تغییر میدهد.به همین شکل دوباره روترها جداول خود را مبادله میکنند.هنگامی که C،جدول مسیریابی B را دریافت میکند،مشاهده میکنید که B وزن پیوند خود تا A را از 1به 3 تغییر داده است،بنابراین C ،جدول خود را روزآمد نموده و وزن پیوند خود تا Aرا به 4 تغییر میدهد.این پروسه تکرار میشود تا همه گره ها وزن پیوند خود را تا A در وضعیت infinity قرار دهند.این وضعیت در جدول زیر نشان داده شده است.

    B    C    D
Sum of weight to A after link cut    ∞,A    2,B    3,C
Sum of weight to B after 1st updating    3,C    2,B    3,C
Sum of weight to A after 2nd updating    3,C    4,B    3,C
Sum of weight to A after 3rd updating    5,C    4,B    5,C
Sum of weight to A after 4th updating    5,C    6,B    5,C
Sum of weight to A after 5th updating    7,C    6,B    7,C

در این روش متخصصین میگویند،الگوریتمهای DV دارای یک سرعت همگرایی پایین هستند.یک روش برای حل این مشکل در مورد روترها،ارسال اطلاعات فقط به روترهایی میباشد که دارای پیوند انحصاری تا مقصد نیستند.برای مثال در این مورد،C نمیبایست هیچ اطلاعاتی را به گره B در مورد A ارسال کند زیرا B فقط یک مسیر تا A را در اختیار دارد.
مسیریابی سلسله مراتبی
همانطور که شما میبینید،در هر دو الگوریتم LS و DV،هر روتر مجبور به ذخیره نمودن اطلاعات مربوط به روترهای دیگر میباشد.هنگامی که اندازه شبکه رشد میکند،تعداد روترهای شبکه افزایش می یابد در نتیجه اندازه جداول مسیریابی نیز افزایش می یابد و روترها نمیوانند ترافیک شبکه را به طور موثر کنترل کنند.ما از مسیریابی سلسله مراتبی برای برطرف کردن این مشکل استفاده میکنیم.اجازه بدهید این موضوع با ذکر یک مثال روشن کنیم:
ما از الگوریتمهای DV برای یافتن بهترین مسیر بین گره ها استفاده میکنیم در وضعیت نشان داده شده در ذیل،هر گره از شبکه مجبور به نگهداری یک جدول مسیریابی با 17 رکورد میباشد.در اینجا یک گراف معمولی و جدول مسیریابی مربوط به A ارائه شده است

Destination    Line    Weight
A    -    -
B    B    1
C    C    1
D    B    2
E    B    3
F    B    3
G    B    4
H    B    5
I    C    5
J    C    6
K    C    5
L    C    4
M    C    4
N    C    3
O    C    4
P    C    2
Q    C    3

در مسیریابی سلسله مراتبی،روترها در گروههایی به نام regions طبقه بندی میشوند.هر روتر دارای اطلاعاتی فقط در مورد روترهایی که در region آنها قرار دارد در اختیار داشته و هیچ گونه اطلاعاتی در مورد region های دیگر ندارند.
در این مثال ما شبکه خود را به پنج region تقسیم میکنیم.اگر A بخواهد بسته ها را به هر روتر در region2 ارسال کند،آنها را به B ارسال میکند و الی آخر.

Destination    Line    Weight
A    -    -
B    B    1
C    C    1
Region 2    B    2
Region 3    C    2
Region 4    C    3
Region 5    C    4

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

در شبکه‌های کوچک، و در نقاطی که انتقال اطلاعات معمولا مستقیم است، مسیریابی چندان جدی گرفته نمی‌شود. اما هنگامی که شبکه‌ها از حالت‌های ایستگاه‌های کاری خارج می‌شوند و کمی پیچیده‌تر می‌شوند، در این حالت، مسیریابی و انتخاب مسیر بهینه برای ارسال بسته‌های اطلاعاتی، به یک امر مهم بدل می‌شود. در شبکه‌های بزرگ، دستگاه‌هایی به‌عنوان مسیریاب (1)  وجود دارند که عمل مسیریابی را انجام می‌دهند
الگوریتم مسیریابی دیکسترا (Dijkstra)
این الگوریتم در سال ۱۹۵۹ توسط یک دانشمند هلندی ارایه شد. این الگوریتم بهترین مسیر را بین دو راس در یک گراف پیدا می کند. بهترین مسیر می تواند کوتاه ترین ، ارزان ترین یا سریع ترین مسیر در نظر گرفته شود که بستگی به نحوه ی انتخاب طول یال های گراف دارد.
روند الگوریتم دیکسترا مطابق زیر می باشد :
انتخاب راس مبدا
مجموعه ی S ، شامل ریوس گراف ، معین می شود. در شروع، این مجموعه تهی بوده و با پیشرفت الگوریتم، این مجموعه ریوسی که کوتاه ترین مسیر به آن ها یافت شده است را در بر می گیرد.
راس مبدا با اندیس صفر را در داخل S قرار می دهد.
برای رئوس خارج از S ، اندیسی معادل ، طول یال + اندیس راس قبلی ، در نظر می گیرد  اگر راس خارج از مجموعه دارای اندیس باشد، اندیس جدید کمترین مقدار از بین اندیس قبلی و طول یال + اندیس راس قبل ، می باشد.
از رئوس خارج مجموعه، راسی با کمترین اندیس انتخاب شده و به مجموعه ی S اضافه می گردد.
این کار را دوباره از مرحله ی ۴ ادامه داده تا راس مقصد وارد مجموعه ی S شود.
در پایان اگر راس مقصد دارای اندیس باشد، اندیس آن نشان دهنده ی مسافت بین مبدا و مقصد می باشد. در غیر این صورت هیچ مسیری بین مبدا و مقصد موجود نمی باشد.
همچنین برای پیدا کردن مسیر می توان اندیس دیگری برای هر راس در نظر گرفت که نشان دهنده ی راس قبلی در مسیر طی شده باشد. بدین ترتیب پس از پایان اجرای الگوریتم، با دنبال کردن ریوس قبلی از مقصد به مبدا، کوتاه ترین مسیر بین دو نقطه نیز یافت می شود.

برنامه الگوریتم مسیر یابی فلوید

#include stdio.h
#include conio.h
#include iostream.h

int minimum(int m, int n)
{
  //return (m>n?n:m);
  if (n    return n;
  else
    return m;
}

void floyd(int n, const int w[6][6], int d[6][6])
{
    int x, y;
    int i, j, k;
    for (x=1;x<=5;x++)
        for(y=1;y<=5;y++)
        d[x][y]=w[x][y];
    for (k=1; k<=n; k++)
      for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
          d[i][j] = minimum(d[i][j], d[i][k]+d[k][j]);

    return;
}

int main()
{       int i, j;
    int d[6][6], b[6][6];
    for (i=1; i<=5; i++)
      for (j=1; j<=5; j++)
        cin >> d[i][j];
    floyd(5, d, b);

    cout << "result is : " << endl;
    for (i=1; i<=5; ++i)
    {
      for (j=1; j<=5; ++j)
        cout << b[i][j] << "  ";
      cout << endl;
    }
    getch();

    return 0;
}

 الگوریتم مسیریابی فلوید وارشال (Floyd-Warshall)

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

منبع:http://blackandwite.blogfa.com