ارایه: کاربرد الگوریتم‌های کوتاه‌ترین مسیر

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

ارایه بخش 4.1 و 4.2 از کتاب Network flows: theory, algorithms, and applications نوشته Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin برای درس «مباحثی در محاسبات علمی» به من واگذار شده بود که می‌تونید از اینجا اسلایدهای اون رو دریافت کنید. شاید این موضوع کمی پیش‌پاافتاده به نظر برسد، اما در حل مسایل تحقیق در عملیات یا OR از اهمیت بالایی برخوردار هستند. تلاش من در این ارایه که تکرار مباحث دوره کارشناسی بودند، ارایه شیوه مدل‌سازی مسایل به صورت شبکه و تبدیل حل آن مسایل به عنوان کوتاه‌ترین مسیر بوده است.
کتاب Network flows: theory, algorithms, and applications یک متن کلاسیک درباره شبکه جریان است که این ترم به عنوان منبع درسی «مباحثی در محاسبات علمی» در نظر گرفته شده است.

In a shortest path problem, we are searching for a path from a source node to a sink node with minimum cost (length) in a network. A network in principle is a graph with associated cost to each arc.

This term, I was responsible to present sections 4.1 and 4.2 of Network flows: theory, algorithms, and applications written by Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin in class. My presentation was consisted of some Applications of shortest path problem. Although these concepts are elementary, I tried to present modeling ideas used to reduce real world problems into Network instances. The slides can be accessed from here.