الگوریتم مسیر یابی کوتاه ترین مسیر در شبکه
الگوریتم مسیر یابی کوتاه ترین مسیر در شبکه
یک راه اندازه گیری طول مسیر ، تعداد جهش ها است، معیار دیگر فاصله جغرافیایی به کیلومتر است .
علاوه بر جهش ها و فاصله فیزیکی ، معیار های دیگری نیز قابل استفاده اند . به عنوان مثال ، هر یال می تواند با میانگین تاخیر صف بندی و انتقال برای بعضی از بسته های آزمایشی ، برچسب گذاری شود . با این برچسب گذاری ، کوتاه ترین مسیر (به جای مسیری با کمترین یال یا فاصله)، سریع ترین مسیر است .
در حالت کلی ، برچسب های یال ها باید به صورت تابعی از فاصله ، پهنای باند ، میانگین ترافیک ، هزینه ارتباط ، میانگین طول صف ، تاخیر اندازه گیری شده ، و سایر عوامل محاسبه شود . با تغییر تابع وزنی ، الگوریتم ، "کوتاه ترین "مسیر وزن دار را براساس هر یک از معیار های فوق یا ترکیبی از آن ها محاسبه می کند .
الگوریتم های متعددی برای محاسبه الگوریتم مسیر یابی کوتاه ترین مسیر در شبکه بین دو گره گرا ف شناسایی شده اند .یکی از این الگوریتم ها به دیکسترا(1995)نسبت داده می شود . هر گره دارای برچسب هایی (در پرانتز)است که فاصله آن تا گره منبع ، از طریق بهترین مسیر شناخته شده است . در آغاز ، هیچ مسیری شناخته شده نیست ، لذا تمام گره ها دارای برچسب بی نهایت هستند . با ادامه اجرای الگوریتم وپیدا شدن مسیر ها ، امکان دارد برچسب ها تغییر کنند تا مسیر های بهتری را منعکس نمایند . برچسب ممکن است موقتی یا دائمی باشد . در آغاز ، تمام برچسب ها موقتی اند . وقتی مشخص شد که برچسبی کوتاه ترین مسیر بین منبع به آن گره را نمایش می دهد ، دائمی می شود و از آن پس تغییر نمی کند .
برای اینکه مشخص شود الگوریتم برچسب گذاری چگونه کار می کند ، گراف وزن دار بدون جهت شکل اول را در نظر بگیرید ، که وزن ها ، مثلا فاصله را نشان می دهند . می خواهیم کوتاه ترین مسیر ازA بهDرا بیابیم . با علامت گذاری گره Aبه عنوان گره ثابت به صورت دایره پر نشان داده شده است ، شروع می کنیم . سپس به نوبت ، تمام گره های همجوار A(گره کاری)را تست می کنیم ، هر کدام را با فاصله آن بهA ، مجددا برچسب می دهیم . هر وقت گره ای مجددا برچسب دهی شد ، آن را با گره ای که کار از آن جا آغاز شد ، برچسب می دهیم ؛ به این ترتیب میتوانیم مسیر نهایی را بازسازی کنیم . با بررسی تمام گره های همجوار A ، تمام گره هایی را که در کل گراف به طور موقت برچسب دهی شدند بررسی می کنیم و گره ای که دارای کوچک ترین برچسب است ، دائمی می کنیم (شکل اول (ب)) . این گره به عنوان گره کاری جدید انتخاب می شود .
اکنون ازB شروع می کنیم و تمام گره های همجوار آن را مورد بررسی قرار می دهیم . اگر مجموع برچسب در B و فاصله B تا گره ای که باید در نظر گرفته شود کمتر از برچسب موجود در آن گره باشد ، کوتاه ترین مسیر پیدا شده ، این گره مجددا برچسب گذاری می شود .
پس از اینکه تمام گره های همجوار گره کاری بررسی شدند و گره های موقتی تغییر کردند ، کل گراف مورد جستجو قرار می گیرد تا گره ای موقتی با کمترین مقدار برچسب پیدا شود . این گره دائمی می شود و برای سیکل بعدی به عنوان گره کاری انتخاب می شود . شکل اول پنج مرحله اول الگوریتم را نشان می دهد .
برای پی بردن به عملکرد الگوریتم ، شکل اول (ج) را ببینید . در این شکل ، E دائمی است ، فرض کنید مسیر AXYZA کوتاه تر از ABE باشد . دو امکان وجود دارد : یا گره Z به عنوان گره دائمی منظور شده ، یا نشده است . اگر دائمی باشد ، E تا کنون بررسی شده است (در سیکلی بعد از آن که Z دائمی شد) ، لذا AXYZE از دید ما خاج نبوده است ونمی تواند مسیر کوتاه تری باشد .
اکنون حالتی را در نظر بگیرید که هنوز برچسب Z موقتی باشد . برچسب موجود در Zبزرگ تر یا مساوی برچسب درE است ، که دراین حالت AXYZE نسبت به ABE مسیر کوتاه تری نیست ؛ یا کمتر از E است که در این حالت Z وE نمی توانند دائمی گردند وE ازZ مورد جستجو قرار می گیرد .
این الگوریتم در شکل دوم آمده است . متغیر های عمومی n وdist گراف را توصیف می کنند و قبل از فراخوانی shortest-path مقدار می گیرد . تنها تفاوت بین برنامه و الگوریتمی که تشریح شد این است که کوتاه ترین مسیر ، نه از گره منبع sبلکه از گره پایانی t محاسبه شده است . چون کوتاه ترین مسیر از tبهs در گراف بدون جهت ، مانند کوتاه ترین مسیر از sبهt است ، مهم نیست که از کدام طرف شروع کنیم (مگر اینکه ، کوتاه ترین مسیر متعددی وجود داشته باشد ، که در آن حالت ، جستجوی معکوس ، مسیر دیگری را انتخاب می نماید .) دلیل جستجوی معکوس این است که هرگره با گره قبلی خود (به جای گره بعدی) برچسب گذاری می شود . هنگام کپی کردن مسیر نهایی در متغیر خروجی path ، مسیر ، معکوس می شود . با معکوس کردن جستجو ،این دو اثر خنثی می شود و پاسخ به ترتیب درستی تولید می گردد .
