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