Question

shortest_path
dijkstra

נתון גרף מכוון G=(V,E)G = (V,E) עם משקלים חיוביים על הקשתות: w:ER+w:E \to \mathbb{R}^+. בנוסף נתון צומת sVs \in V ומספר 0kE0 \leq k \leq |E|. הקשתות צבועות בשני צבעים: שחור ולבן.

הציעו אלגוריתם המוצא לכל vVv \in V, את משקל המסלול הקל ביותר מ-ss ל-vv, מבין כל המסלולים מ-ss ל-vv המשתמשים ב-kk קשתות שחורות בדיוק (לא פחות ולא יותר).

על האלגוריתם לרוץ בסיבוכיות O(k(V+ElogV))O(k (|V| + |E| \log |V|)).

1

Answers

נסמן ב-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)).

1
Feedback