Question

bfs
dynamic_programming

יהא G=(V,E)G = (V, E) גרף לא מכוון, ויהא sVs \in V. הצע אלגוריתם המחשב לכל צומת vVv \in V את מספר המסלולים הקצרים ביותר מ-ss ל-vv.

1

Answers

בהינתן המרחק של כל צומתvvמ-ss, d(v)d(v), נגדיר את "גרף המסלולים הקצרים":

D=(V,A)D = (V, A)

כאשר

A={uv:uvEd(v)=d(u)}A = \{uv : uv \in E \land d(v) = d(u)\}.

נשים לב כי DD גרף מכוון שגרף התשתית שלו הוא תת גרף של GG.

טענה 1: אם s,v1,,vks, v_1, \ldots, v_k מסלול ב-DD אז d(vk)=kd(v_k) = k, כלומר, כל מסלול ב-DD הוא מסלול קצר ביותר ב-GG.

הוכחה: באינדוקציה על kk.

בסיס: עבור k=0k = 0 הטענה טריוויאלית.

צעד: אם d(vk1)=k1d(v_{k - 1}) = k - 1 (הנחת האינדוקציה)ו-vk1vkAv_{k - 1}v_k \in A אז d(vk)=kd(v_k) = k (הגדרה של AA).

טענה 2: אם s,v1,,vks, v_1, \ldots, v_k מסלול קצר ביותר ב-GG אז זהו גם מסלול ב-DD.

הוכחה: מכיוון שזהו מסלול קצר ביותר אז לכל ii מתקיים ש-d(vi+1=d(vi)d(v_{i + 1} = d(v_i) ולכן vivi+1Av_iv_{i+1} \in A.

אבחנה: DD חסר מעגלים (נובע מטענה 1).

כעת, לכל צומת, vv, נסמן ב-f(v)f(v) את מספר המסלולים הקצרים ביותר מ-ss ל-vv. קל לראות ש-f(s)=1f(s) = 1 ו-

f(v)=uvAf(u) f(v) = \sum_{uv \in A} f(u)

את ff אפשר לחשב לפי סדר המיון הטופולוגי של DD.

סיבוכיות:

  • חישוב מרחקים קצרים ביותר O(V+E)O(V + E)
  • בניית DD O(V+E)O(V + E)
  • מיון טופולוגי וחישוב ff O(V+E)O(V + E)

סך הכל O(V+E)O(V + E).

4
Feedback