Question

dynamic_programming
scc
spring17_a

נתונים גרף מכוון G=(V,E)G = (V,E), צומת sVs \in V ופונקציית משקל על הצמתים w:VRw:V \to R. נגדיר משקל של מסלול PP, כמשקל הצומת הקל ביותר בו. כלומר: w(P)=minvP{w(v)}w(P) = \displaystyle{\min_{v \in P}}\{w(v)\}.

הציעו אלגוריתם המחזיר לכל vVv \in V את משקל המסלול הקל ביותר מ-ss ל-vv (אם אין מסלול כזה, יש להחזיר \infty).

שימו לב: מסלול קל ביותר לפי ההגדרה החדשה אינו פשוט בהכרח - עשוי להכיל צמתים או קשתות יותר מפעם אחת.

1

Answers

פתרון ללא הוכחה:

נסמן ב-Gscc=(C,Escc)G_{scc} = (C, E_{scc}) את גרף הרק"ה של GG ונניח ש-C={c1,,ck}C = \{c_1,\ldots,c_k\}. לפי סדר מיון טופולוגי כלשהו של GsccG_scc

לכל ciCc_i \in C נסמן ב-CiC_i את הרק"ה המתאים לו. נגדיר w(ci)=minvCiw(v)w(c_i) = \min_{v \in C_i}w(v).

נסמן ב-CjC_jאת הרק"ה שמכיל את ss.

נגדיר

w(ci)={i<jw(ci)i=jminw(cl:(cl,ci)Esccotherwise w'(c_i) = \begin{cases} \infty & i < j \\ w(c_i) & i = j \\ \min_{w(c_l}:(c_l, c_i) \in E_{scc} & \text{otherwise} \end{cases}

נשים לב שאת ww'ניתן לחשב לפי סדר המיון הטופולוגי.

לבסוף לכל vVv \in Vנחזיר את w(ci):vCiw'(c_i) : v \in C_i.

1
Feedback