Question

winter17-18
shortest_path
dijkstra

נתון גרף מכוון G=(V,E)G = (V,E) וזוג צמתים s,tVs,t \in V. פניה מוגדרת ע"י שלשת צמתים (u,v,w)(u,v,w). מסלול עובר דרך פניה (u,v,w)(u,v,w) אם הצמתים u,v,wu,v,w מופיעים במסלול ברצף. קבוצת הפניות בגרף היא

T={(u,v,w):(u,v)E(v,w)E}T = \{(u,v,w) : (u,v) \in E \land (v,w) \in E\}.

ונתונה תת קבוצה של פניות מסוכנות, DTD \subseteq T.

הציעו אלגוריתם המוצא מסלול מ-ss ל-tt העובר דרך מינימום פניות מסוכנות.

1

Answers

נניח בלי הגבלת הכלליות ש-(s,t)E(s,t) \notin E ונגדיר גרף חדש G=(V,E)G' = (V', E') כאשר

  • V={uv:(u,v)E}{s,t}V' = \{uv : (u,v) \in E\} \cup \{s,t\}
  • E={(uv,vw):(u,v,w)T}{(s,su):suV}{(vt,t):vtV}E' = \{(uv, vw) : (u, v, w) \in T\} \cup \{(s, su) : su \in V'\} \cup \{(vt, t) : vt \in V'\}

ופונקציית משקל w:E{0,1}w:E' \to \{0,1\} כאשר

w(uv,vw)={1(u,v,w)T0otherwise w(uv, vw) = \begin{cases} 1 & (u,v,w) \in T \\ 0 & \text{otherwise} \end{cases}

ו- w(s,su)=w(vt,t)=0w(s, su) = w(vt, t) = 0

נחשב מסלול קל ביותר מ-ss ל-tt ב-GG' ונפלוט את המסלול המתאים לו ב-GG כמתואר בהמשך.

נכונות:

נראה שלכל מסלול ב-GG עם dd פניות מסוכנות מתאים מסלול ב-GG' במשקל dd ולכל מסלול ב-GG' עם משקל dd קיים מסלול ב-GG עם dd פניות מסוכנות. הנכונות נובעת מיידית.

נשים לב ש-

sv1v2vk1vkt s-v_1-v_2-\ldots-v_{k - 1}-v_k-t

מסלול עם dd פניות ב-GG אמ"מ

ssv1v1v2vk1vkvktt s-sv_1-v_1v_2-\ldots-v_{k - 1}v_k-v_kt-t

מסלול במשקל dd ב-GG'.

3
Feedback