درخت کوتاهترین مسیر
در نظریه گراف، برای هر گراف همبند ساده (غیر جهتدار) یک زیر گراف وجود دارد که در آن از گره ریشه به تمامی گره‌ها مسیری وجود دارد و طول این مسیر (فاصلهٔ گره ریشه با سایر گره‌ها) کمینه است.
این گراف یک درخت است. زیرا اگر دو مسیر بین گره ریشه و یک راس v (به عنوان مثال یک دور) باشد، می‌توانیم یال با طول بزرگتر را حذف کنیم، بدون اینکه فاصلهٔ بین گره ریشه تا هر یک از گره‌های دیگر در این زیردرخت افزایش یابد؛ بنابراین دوری در گراف باقی نمی‌ماند و به یک درخت تبدیل می‌شود.
اگر بین هر جفت گره در گراف کوتاهترین مسیر یکتایی وجود داشته باشد، در نتیجه این درختِ باکوتاهترین مسیر، یکتاست. با استفاده از اثبات زیر می‌توان این ادعا را ثابت کرد. اگر یک مسیر مشخص از ریشه به هر گره، دارای یال کمینه باشد، می‌توان گفت هر قسمت از آن مسیر (بین هر دو گره مختلف) یک مسیر کمینه بین آن دو گره است.
در گراف‌های بدون یال منفی، با مشخص کردن یک راس، می‌توان با استفاده از الگوریتم دیکسترا درخت با کوتاهترین مسیر را یافت. در گراف‌هایی که احتمالاً دارای یال منفی هستند، می‌توان از الگوریتم بلمن–فورد، به جای این الگوریتم استفاده کرد.
اگر بخواهیم مسیر کمینه را برای هر دو جفت گره موجود در گراف پیدا کنیم، الگوریتم به صرفه تری به نام الگوریتم فلوید-وارشال وجود دارد.
یک مسئلهٔ شناخته شده در شبکه که از درخت با کوتاهترین مسیر استفاده می‌کند، محاسبهٔ هزینه، قابلیت اطمینان، و پهنای باند مورد نیاز برای گره مرکزی هست.
مسئلهٔ درخت کوتاهترین مسیر
[ویرایش]
در تئوری گراف، مسئلهٔ درخت کوتاهترین مسیر، در واقع پیدا کردن مسیری بین دو گره در گراف است، به صورتی که حاصل جمع وزن یال‌های موجود در مسیر کمینه باشد. یک مثال از این مسئله در دنیای واقعی پیدا کردن کوتاهترین مسیر به یک مقصد از روی نقشه‌است. در اینجا ر ئوس، نمایندهٔ مبدأ و مقصدها (مکان‌های مورد نظر) و یال‌ها بیانگر جاده‌ها هستند که با توجه به زمانی که طول می‌کشد تا مسافت بین این دو مکان را طی کنیم، ارزش‌گذاری می‌شوند.
شکل زیر یک نمونه از اجرای الگوریتم دیکسترا که برای پیدا کردن درخت کوتاهترین مسیر، در گراف‌های بدون دور منفی به کار گرفته می‌شود، می‌باشد.
جستارهای وابسته
[ویرایش]منابع
[ویرایش]مشارکت‌کنندگان ویکی‌پدیا. «Shortest path tree». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۸ ژوئیه ۲۰۱۱.