( kormanyos | 2015. 05. 05., k – 18:31 )

A kérdés nem arra irányult, hogy a lehető legkevesebb csúcsú utat keressem meg. A Ford-Bellman valóban ebből a szempontból remek választás lenne.
A bemeneti gráf néhány csúcspontjának strukturális szempontból speciális relevanciája van a többi csúcsponthoz képest. A lényeg az, hogy ezen speciális jelentőségű pontok között megtaláljam a gráfban azt a lehető legrövidebb utat, ami nem tartalmaz más speciális pontot. Legyenek például az f1, f2, f3, f4, f5 pontok ezek speciális csúcsok, ezeken kívül még van számos más egyéb csúcs is, amelyek nem kitüntetettek. Keresem az például az f1 és f5 csúcsok közötti legrövidebb utat. Ha ezen szerepel más speciális csúcs a kezdő és végponton kívül, akkor az ekvivalens azzal, mintha nem találtunk volna utat. Tehát arra a legrövidebb útra lenne szükségem ezen speciális csúcspárok között a gráfban, ami nem tartalmaz speciális pontokat, azaz csak "hagyományos" csúcsok fekszenek rajta. Az sem baj, ha hosszabb, mint a tényleges legrövidebb - de speciális pontokat tartalmazó - út.