Question

shortest_path
dijkstra

יהא G=(V,E)G = (V, E) גרף מכוון בעל משקלות אי-שליליות על הקשתות. יהא sVs \in V ושני מספרים 0R,BE0 \leq R,B \leq |E|. כל קשת בגרף צבועה באחד מבין שלושת הצבעים - כחול, לבן או אדום.

הציעו אלגוריתם המוצא מסלול קל ביותר מ-ss לכל צומת בגרף, המשתמש בלכל הפחות RR קשתות אדומות ובלכל היותר BB קשתות כחולות. על האלגוריתם לרוץ בסיבוכיות זמן O(RB(E+ElogV))O(RB(|E| + |E|\log|V|)).

1

Answers

נסמן ב-Ew,Er,EbE_w, E_r, E_b את קבוצת הקשתות הלבנות, אדומות וכחולות בהתאמה ונגיד שמסלול הוא חוקי אם הוא עובר ב-RR קשתות אדומות לפחות וב-BB קשתות כחולות לכל היותר.

נשכפל את צמתי הגרף (R+1)(B+1)(R + 1)(B + 1) פעמים,

i[R]j[B+1]Vij \bigcup_{i \in [R] \atop j \in [B + 1]} V_{ij}

ופעם נוספת VfV_f.

נגדיר קשתות באופן הבא:

i[R1]j[B]Eij \bigcup_{i \in [R - 1] \atop j \in [B]} E_{ij}

כאשר

Eij={uijvij:uvEw}{uijvi+1,j:uvEr}{uijvi,j+1:uvEb} E_{ij} = \{u_{ij}v_{ij} : uv \in E_w\} \cup \{u_{ij}v_{i + 1,j} : uv \in E_r\} \cup \{u_{ij}v_{i, j + 1} : uv \in E_b\}

ובנוסף נגדיר

Ef={uRjvf:uvEr}{ufvf:uvEwEr} E_f = \{u_{Rj}v_{f} : uv \in E_r\} \cup \{u_fv_f : uv \in E_w \cup E_r\}

כלומר מסלול מ-s11s_11 לצומת vijv_ij בגרף שהגדרנו עובר ב-ii קשתות אדומות ו-jj קשתות כחולות.

כמו כן נשים לב שלכל מסלול חוקי ב-GG יש מסלול מתאים בעל אותו משקל בדיוק בגרף החדש שמסתיים ב-VfV_fוכל מסלול מצומת s11s_11 לצומת vfv_f מתאים למסלול חוקי מ-ss ל-vv ב-GG.

אלגוריתם:

  • בנה את הגרף החדש כמתואר לעיל.
  • מצא עץ מרחקי קלים ביותר מ-s11s_{11} לשאר צמתי הגרף.
  • החזר את המשקלים של המסלולים מ-s11s_{11} לצמתי VfV_f.

נכונות: מהדיון שלמעלה.

סיבוכיות: מספר הצמתים החדשים הוא O(RBV)O(RBV) ומספר הקשתות החדשות הוא O(RBE)O(RBE) ולכן, על ידי שימוש בדיקסטרה למשל, אפשר למצוא מרחקים קלים ביותר בגרף החדש בזמן O(RB(ElogV))O(RB(E\log V)).

1
Feedback