گراف ساده و بدون‌جهت ‎$G(V‎, ‎E)$‎ با ‎$|V|=n$‎ رأس و ‎$|E|=e$‎ یال داده شده است. وزن یال‌های این گراف همگی یک هستند، منتهی روی هر یک از یال‌های این گراف، دقیقاً یکی از هفت نت موسیقی (دو، ر، می، فا، سل، لا، سی) نوشته شده است.

یک مسیر در این گراف را ملودیکال می‌گوییم اگر نت روی یال‌های مسیر به این صورت باشد: دو، ر، می، فا، سل، لا، سی، لا، سل، فا، می، ر، دو، ر، ‎$\dots$‎ یعنی الزاماً از اولین نت شروع بشود، تا نت آخر برود و بعد برگردد و تا اولین نت برود و ‎$\dots$‎ دقت کنید که مسیر ‎«ر، می، فا»‎ موزیکال نیست چون از ‎«دو»‎ شروع نمی‌شود؛ مسیر «دو، ر، می، فا، سل، لا، سی، دو، ر»‎ هم موزیکال نیست چون باید بعد از سی (بالاترین نت) پایین بیاییم ‎($\dots$‎، لا، سی، لا، سل، ‎$\dots$)‎. به عبارت دیگر نمودار نت‌های مسیر با شروع از دو به‌صورت زیگزاگ ‎(کوهستانی)‎ خواهد بود.

آبتین می‌خواهد روی این گراف کوتاه‌ترین مسیر ملودیکال ممکن از رأس داده‌شده‌ی ‎$s$‎ به رأس داده‌شده‌ی ‎$t$‎ را پیدا کند. سعی‌کنید برای این‌کار یک الگوریتم ‎${\cal O}(n+e)$‎ بدهید و الگوریتم خود را تحلیل و اثبات کنید.

• سوال بعد
• سوال قبل