Question

shortest_path
dijkstra

נתון גרף מכוון G=(V,E)G = (V,E) עם משקלים אי שליליים על הקשתות, פרט לקשת אחת e=(a,b)e = (a,b) שמשקלה שלילי. נניח שאין מעגלים שליליים בגרף.

בהינתן צומת מקור ss הציעו אלגוריתם בסיבוכיות O(V+ElogV)O(|V| + |E|\log|V|) שמוצא עבור כל צומת vVv \in V את משקל המסלול הקל ביותר מ-ss ל-vv.

1

Answers

האלגוריתם:

  1. הסר את הקשת abab מהגרף
  2. הרץ את אלגוריתם דייקסטרה מ-ss
  3. הרץ את אלגוריתם דייקסטרה מ-bb
  4. לכל צומת vv החזר min{d(s,v),d(s,a)+w(ab)+d(b,v)}\min \{d(s,v), d(s,a) + w(ab) + d(b,v)\}

נכונות:

מכיוון שאין מעגלים שליליים בגרף אז לכל צומת קיים מסלול פשוט קל ביותר. אם לצומת vv קיים מסלול קל ביותר שלא עובר בקשת abab אז ערכו הוא d(s,v)d(s,v).

אחרת המסלול הזה מורכב ממסלול קל ביותר מ-ss ל-aa, הקשת abab ומסלול קל ביותר מ-bb ל-vv ולכן ערכו הוא d(s,a)+w(ab)+d(b,v)d(s,a) + w(ab) + d(b,v).

1
Feedback