א. אלגוריתם: לכל צומת, 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)\}
Feedback