درخت کوتاه‌ترین مسیر

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در نظریه گراف، برای هر گراف همبند ساده (غیر جهتدار) یک زیر گراف وجود دارد که در آن از گره ریشه به تمامی گره ها مسیری وجود دارد و طول این مسیر (فاصله ی گره ریشه با سایر گره ها) کمینه است.

این گراف یک درخت است. زیرا اگر دو مسیر بین گره ریشه و یک راس v (به عنوان مثال یک دور) باشد، می‌توانیم یال با طول بزرگتر را حذف کنیم، بدون اینکه فاصلهٔ بین گره ریشه تا هر یک از گره های دیگر در این زیردرخت افزایش یابد. بنابراین دوری در گراف باقی نمی‌ماند و به یک درخت تبدیل می شود.

اگر بین هر جفت گره در گراف کوتاهترین مسیر یکتایی وجود داشته باشد، در نتیجه این درختِ باکوتاهترین مسیر، یکتاست. با استفاده از اثبات زیر می‌توان این ادعا را ثابت کرد. اگر یک مسیر مشخص از ریشه به هر گره، دارای یال کمینه باشد، می‌توان گفت هر قسمت از آن مسیر (بین هر دو گره مختلف) یک مسیر کمینه بین آن دو گره است.

در گراف‌های بدون یال منفی، با مشخص کردن یک راس، می‌توان با استفاده از الگوریتم دیکسترا درخت با کوتاهترین مسیر را یافت. در گراف‌هایی که احتمالاً دارای یال منفی هستند، می‌توان از الگوریتم بلمن–فورد، به جای این الگوریتم استفاده کرد.

اگر بخواهیم مسیر کمینه را برای هر دو جفت گره موجود در گراف پیدا کنیم، الگوریتم به صرفه تری به نام الگوریتم فلوید-وارشال وجود دارد.

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

مسئلهٔ درخت کوتاه‌ترین مسیر[ویرایش]

Dijkstra Animation.gif

در تئوری گراف، مسئلهٔ درخت کوتاهترین مسیر، درواقع پیدا کردن مسیری بین دو گره در گراف است، به صورتی که حاصل جمع وزن یال‌های موجود در مسیر کمینه باشد. یک مثال از این مسئله در دنیای واقعی پیدا کردن کوتاهترین مسیر به یک مقصد از روی نقشه‌است. در اینجا ر ئوس، نمایندهٔ مبدا و مقصدها (مکان‌های مورد نظر) و یال‌ها بیانگر جاده‌ها هستند که با توجه به زمانی که طول می‌کشد تا مسافت بین این دو مکان را طی کنیم، ارزش گذاری می‌شوند.

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

جستارهای وابسته[ویرایش]

منابع[ویرایش]

مشارکت‌کنندگان ویکی‌پدیا، «Shortest path tree»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۸ ژوئیه ۲۰۱۱).