Question

winter_16-17_a
shortest_path

יהא G=(V,E)G = (V,E) גרף מכוון ויהא vVv \in V. נניח כי נתונים המרחקים בין כל זוג צמתים בגרף G=G[V{v}]G' = G[V \setminus \{v\}] ביחס לפונקציית משקל אי שלילית w:ER+w:E \to \mathbb{R}^+. כלומר, לכל זוג צמתים a,bV{v}a,b \in V \setminus \{v\} ידוע dG(a,b)d_{G'}(a,b) - משקל מסלול קל ביותר מ-aa ל-bb בגרף GG'.

א. הציעו אלגוריתם הרץ בזמן O(V2)O(|V|^2) המחשב לכל צומת uVu \in V את משקל המסלול הקל ביותר dG(u,v)d_G(u,v).

ב. גם בסעיף זה נתון G=(V,E)G = (V,E) גרף מכוון ו-vVv \in V. לכל a,bV{v}a,b \in V \setminus \{v\} נתון מראש dG(a,b)d_{G'}(a,b). בנוסף, לכל uVu \in V נתונים המרחקים dG(u,v),dG(v,u)d_G(u,v), d_G(v,u).

הציעו אלגוריתם הרץ בזמן O(V2)O(|V|^2) המחשב לכל זוג צמתים s,tVs,t \in V את המרחק dG(s,t)d_G(s,t).

אין צורך להוכיח נכונות.

1

Answers

א. אלגוריתם: לכל צומת, vuv \neq u נחזיר

minw:uwEw(uw)+dG(w,v) \min_{w : uw \in E} w(uw) + d_{G'}(w, v)

נכונות:

נסתכל על מסלול קל ביותר ב-GG מ-vv ל-uu: v,,w,uv, \ldots, w, u אז wuEwu \in E ו-dG(v,w)=dG(v,w)d_G(v, w) = d_{G'}(v, w).

סיבוכיות: לכל צומת עוברים על כל השכנים של uu - סך הכל O(V2)O(|V|^2).

ב. לכל זוג צמתים s,ts,t נחזיר

min{dG(s,t),dG(s,v)+dG(v,t)} \min \{d_{G'}(s,t), d_G(s, v) + d_G(v, t)\}
1
Feedback