اگر هر شرکت هواپیمایی را معادل یک رنگ در نظر بگیریم، مسئله از ما مسیری می‌خواهد که در آن کم‌ترین تعداد تغییر رنگ را داشته باشیم. در ادامه راه‌حل، هر شرکت هواپیمایی را معادل با یک رنگ فرض می‌گیریم‎.

‎ در هر قسمت از مسیر که قرار داشته باشیم، برای ما تنها چیزهایی که مهم است، این است که در چه رأسی قرار داریم و با چه یالی به این رأس وارد شده‌ایم. بنابراین اگر بخواهیم این مسئله را با روش پویا یا چیزی مشابه آن حل کنیم، می‌توانیم هر وضعیت را با یک زوج مرتب مثل ‎$(v‎, ‎c)$‎ نشان دهیم که ‎$v$‎ شماره ی رأس و ‎$c$‎ رنگ بلیطی است که به آن رأس وارد شده‌ایم. هنگام تغییر از یک وضعیت به وضعیت دیگر در صورتی که تغییر رنگ دهیم، باید ‎1‎ واحد هزینه بپردازیم و در غیر این صورت، هزینه‌ای نباید بپردازیم. بنابراین مسئله به یافتن کوتاه‌ترین مسیر از وضعیت ‎$(1‎, -‎1)$‎ به وضعیت ‎$(n‎, ‎*)$‎ در گراف وضعیت‌ها تبدیل می‌شود. رنگ -‎1‎ نشان‌دهنده‌ی این است که با رنگ مشخصی وارد رأس یک نشده‌ایم. و منظور از ‎$(n‎, ‎*)$‎ این است که با هر رنگی می‌توان مسیر را در رأس ‎$n$‎ تمام کرد. این روش دومشکل دارد: ‎

1. ‎گراف وضعیت‌ها دور دارد، و با روش پویا نمی‌توان کوتاه‌ترین مسیر را پیدا کرد.
2. ‎ تعداد وضعیت‌ها برابر تعداد رنگ‌ها ضرب در تعداد شهرهاست که بسیار زیاد است و همچنین تعداد یال‌های بین وضعیت‌ها می‌تواند بسیار زیاد باشد.

‎ ‎ برای حل مشکل اول، می‌توان به جای استفاده از روش پویا، از الگوریتم‌های ‎BFS‎ یا ‎Dijkstra‎ برای یافتن کوتاه‌ترین مسیر استفاده کرد. اما برای رفع مشکل دوم باید تعداد وضعیت‌ها و یال‌های بین آن‌ها را کاهش دهیم. اولا توجه کنید که برای یک وضعیت مثل ‎$(u,c)$‎ در صورتی که در گراف ورودی به رأس ‎$u$‎ یالی به رنگ ‎$c$‎ متصل نباشد، این وضعیت اصلا قابل دسترسی نیست. بنابراین کافی است فقط وضعیت‌هایی مثل ‎$(u‎, ‎c)$‎ را در نظر بگیریم که در گراف ورودی رأس ‎u‎ یالی به رنگ ‎$c$‎ داشته باشد و به سادگی می‌توان نشان داد که تعداد این وضعیت‌ها حداکثر برابر ‎$m$ (تعداد یال های گراف ورودی) است‎.

اما هم‌چنان با مشکل تعداد زیاد یال‌ها مواجه هستیم. فرض کنید در گراف رأسی مثل ‎$v$‎ وجود دارد که به آن ‎$t$‎ یال با رنگ‌های مختلف متصل است. در نتیجه به ازای هر کدام از این رنگ‌ها مثل ‎$c$‎ یک وضعیت ‎$(v‎ , ‎c)$‎ در گراف وضعیت‌ها داریم و همه‌ی این وضعیت‌ها به هم متصل هستند. بناربراین در حدود ‎t2‎ یال به ازای این رأس وجود دارد. و این تعداد می تواند بسیار زیاد باشد. برای حل این مشکل می‌توان به ازای هر رأس مثل ‎u‎ یک وضعیت دیگر به اسم ‎$(u‎, -‎1)$‎ گرفت که به معنی تغییر رنگ باشد. به این شکل که از هر وضعیت مثل ‎$(u‎, ‎c)$‎ در صورتی که نخواهیم تغییر رنگ دهیم فقط به وضعیت‌هایی مثل ‎$(v‎, ‎c)$‎ می توان رفت، به شرطی که در گراف ورودی بین رئوس ‎$u$‎ و ‎$v$‎ یالی با رنگ ‎$c$‎ وجود داشته باشد و در صورتی که بخواهیم تغییر رنگ بدهیم به وضعیت ‎$(u‎, -‎1)$‎ می رویم و یک واحد هزینه می‌پردازیم. به سادگی می‌توان نشان داد که با این روش تعداد یال‌ها در گراف وضعیت ها از ‎$O(m)$‎ یعنی تعداد یال‌های گراف ورودی است‎.

‎ پس می‌توان در گراف وضعیت‌ها با الگوریتمی مثل Dijkstra کوتاه‌ترین مسیر بین وضعیت‌های ‎$(1‎, -‎1)$‎ و ‎$(n‎, ‎*)$‎ پیدا کرد. و در نهایت با اندکی تغییر در الگوریتم ‎Dijkstra‎ می‌توان کاری کرد که مسیر نهایی از نظر lexicographically‎ هم بهینه باشد‎.‎

پيچيدگي ‎

با توجه به اینکه شماره‌ی رنگ‌ها تا ‎$10^9$‎ مقدار می‌تواند داشته باشد، برای نگهداری وضعیت‌ها می‌توان از map یا set‎ استفاده کرد، که این کار باعث می‌شود هنگام دسترسی به هر وضیعت از ‎$O(\log m)$‎ زمان صرف کنیم. الگوریتم ‎Dijkstra‎ نیز از ‎$O(m \log m)$‎ زمان صرف می‌کند، زیرا در گراف وضعیت‌ها هم تعداد رئوس و هم تعدا یال‌ها از ‎$O(m)$‎ است. بنابراین می توان الگوریتم را با پیچیدگی ‎$O(m \log m)$‎ پیاده‌سازی کرد.