توسیع مسئله کوتاهترین مسیر به کمک کارایی متقاطع

چکیده مقاله

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