Question

bfs
dijkstra

נתון גרף לא מכוון G=(V,E)G = (V,E)

ונתונה פונקציית משקל w:E{0,1}w:E \to \{0,1\}.

יהא sVs \in V צומת בגרף. משקל מסלול בגרף הוא סכום משקלי הקשתות לאורכו.

הציעו אלגוריתם המחשב את משקל המסלול הקל ביותר ds(v)d_s(v) לכל צומת vVv \in V בגרף בזמן O(V+E)O(|V| + |E|).

1

Answers

נזכר באלגוריתם דיקסטרה:

  1. אתחול:
    • לכל vVv \in V מציבים d(v)d(v) \leftarrow \infty, p(v)nilp(v) \leftarrow nil
    • מציבים d(s)0d(s) \leftarrow 0
    • מציבים QVQ \leftarrow V
  2. כל עוד QQ לא ריק:
    • יהי uQu \in Q צומת עם ערך dd מינימלי
    • הוצא את uu מ-QQ ולכל uvEuv \in E בצע ניסיון שיפור לפי uvuv

נשים לב שאם משקלי הקשתות הם 0 או 1 אז לצמתים ב-QQ יש 3 ערכים שונים לכל היותר בכל רגע נתון. נממש את QQ על ידי 3 רשימות מקושרות עבור 3 הערכים ולכן כל פעולה על QQ לוקחת O(1)O(1) ובסך הכל זמן הריצה הוא לינארי.

1
Feedback