تحقیق در مورد تحلیل مساله کوتاهترین مسیر در گراف جهت دار

لینک پرداخت و دانلود *پایین مطلب *   فرمت فایل :Word ( قابل ویرایش و آماده پرینت )    تعداد صفحه10   فهرست مطالب     تحلیل مساله کوتاهترین مسیر در گراف جهت دار یک ایده برنامه نویسی پویا : ضمایم: بهینه سازیهای مهم الگوریتم اگر G دورهای منفی نداشته باشد؛‍‍‍ پس کوتاهترین مسیر ساده از S به t وجود دارد.(یعنی گره ها تکرار نمی شوند.) و از اینرو در نهایت n-1 یال دارد. اثبات: تا زمانی که هر دور هیچ هزینه منفی نداشته باشد؛ کوتاهترین مسیر P از s به t با بیشترین تعداد از یالها هیچ راس v را مرور نمی کند. اگر P ؛ راس v را تکرار کند؛ ما می توانیم بخش مابین عبورهای متوالی از v را حذف کنیم. که این عمل هزینه کمینه و یال بیشینه را نتیجه می دهد. اجازه دهید OPT(i,v) را برای تفکیک کمترین هزینه یک مسیر v-t با استفاده از بی ...