נסמן ב-WW את קבוצת הקשתות הלבנות וב-BB את קבוצת הקשתות השחורות. נבנה גרף מכוון חדש על ידי שכפול צמתי הגרף המקורי k+1k + 1 פעמים V1Vk+1V_1 \ldots V_{k + 1} וקבוצת הקשתות

{uivi:uvW}1ik+1{uivi+1:uvB} \left\{u_iv_i : uv \in W\right\}_{1 \leq i \leq k + 1} \cup \{u_iv_{i+1} : uv \in B\}

קל לראות שמשקל מסלול קל ביותר מ-ss ל-vv שמכיל kk קשתות שחורות בדיוק בגרף המקורי הוא משקל מסלול קל ביותר מ-s1s_1 ל-vk+1v_{k + 1} בגרף החדש.

בגרף החדש יש O(kE)O(kE) קשתות ו-kVkV צמתים ולכן אפשר למצוא בו עץ מסלולים קלים ביותר בסיבוכיות

O(k(V+ElogV))O(k(V + E \log V)).

Feedback