Question

dijkstra

יהא G=(V,E)G = (V,E) גרף מכוון עם משקלות אי-שליליות על הקשתות, ויהא sVs \in V.

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

1

Answers

לכל צומת vv ניתן למצוא את משקל מעגל קל ביותר המכיל הן את vv והן את ss על ידי מציאת עץ מסלולים קלים ביותר ב-GG ועץ מסלולים קלים ביותר ב-GTG^T (הגרף GG לאחר היפוך כיווני הקשתות) וחיבור המשקלים לכל צומת.

סיבוכיות: את GTG^T ניתן לחשב בזמן לינארי. ניתן להשתמש ב-Dijkstra כדי לחשב עץ מסלולים קלים ביותר בזמן O(ElogV)O(E\log V) ולכן הסיבוכיות הכוללת היא O(ElogV)O(E\log V).

נכונות: נובעת מכך שמשקל מעגל קל ביותר שמכיל הן את vv והן את ss הוא סכום משקלי המסלולים הקלים ביותר מ-ss ל-vv ומ-vv ל-ss.

1

אלגוריתם -

  1. נחשב את GSCCG^{SCC} , נסמן ב- SS את הרק"ה בו ss מצוי.
  2. נריץ Dijkstra מכל vSv\in S ברק"ה SS (לא על הגרף הכללי) כדי לחשב את המסלולים הקלים ביותר בין כל זוג s,vSs,v\in S .
  3. לכל vSv\in S נחזיר wc(s,v)=ds(v)+dv(s)w_{c(s,v)}=d_s(v) + d_v(s) .
  4. לכל vVSv\in V\setminus S - אין מעגל משותף עם ss על כן נחזיר ערך כלשהו (נניח 1-1) .

סיבוכיות -

O(VElog(V))O(|V||E|log(|V|)) - מפני שמריצים S|S| פעמים Dijkstra . הסיבכויות לחישוב GSCCG^{SCC} כלולה.

נכונות -

לפי טענה מהתרגול - אם קיים מעגל CC כך ש: sCs\in C אז המעגל מוכל כולו באותו רכיב קשיר היטב. על כן כל צומת שאינו ב- SS לא מצוי במעגל משותף עם ss וכן כל צומת ב- SS מצוי במעגל משותף עם ss (לפי הגדרה של רק"ה) .

יהיו vSv\in S ומעגל משותף CC ל- ss ו- vv . נסמן את :

  • C=su1u2...vw1w2...wnsC=s-u_1-u_2...-v-w_1-w_2...w_n-s
  • מפני - ds(v),dv(s)d_s(v) , d_v(s) מסלולים קלים ביותר, מתקיים:
    1. w(su1u2...v)ds(v)w(s-u_1-u_2-...-v)\ge d_s(v)
    2. w(vw1...s)dv(s)w(v-w_1-...-s)\ge d_v(s)

על כן הסקנו כי לכל מעגל משותף מתקיים w(C)ds(v)+dv(s)w(C) \ge d_s(v)+d_v(s) ולכן האלגוריתם אכן מחזיר את המעגל המינמלי.

0
Feedback