Question

shortest_path

יהא G=(V,E)G = (V,E) גרף מכוון עם משקלות על הקשתות. תהא eEe' \in E ויהיו s,tVs,t \in V.

  1. הציעו אלגוריתם המכריע האם קשת ee' נמצאת על כל מסלול קל ביותר מ-ss ל-tt.
  2. הציעו אלגוריתם המכריע האם הקשת ee' נמצאת על איזשהו מסלול קל ביותר מ-ss ל-tt.
1

Answers

1. נחשב משקל מסלול קל ביותר מ-ss ל-tt ב-GG ונבדוק אם לאחר הסרת ee' מ-GG משקל מסלול קל ביותר מ-ss ל-tt נשאר זהה, אם כן אז התשובה היא לא ואם לא אז התשובה היא כן.

נכונות: אם לאחר הסרת הקשת ee' קיים מסלול קל ביותר באותו משקל אז ee' לא נמצאת על כל מסלול, אם לא קיים אז ee' חייבת להיות בכל מסלול קל ביותר אחרת גם אחרי שמורידים אותה קיים מסלול קל ביותר.

סיבוכיות: אנחנו מחשבים מסלול קל ביותר פעמיים וניתן לעשות זאת על ידי בלמן פורד למשל בסיבוכיות O(EV)O(EV).

2. נחשב משקל מסלול קל ביותר מ-ss ל-tt, w1w_1.נסמן e=uve' = uv, נחשב משקל מסלול קל ביותר מ-ss ל-uu, w2w_2 ומשקל מסלול קל ביותר מ-vv ל-tt, w3w_3.נחזיר כן אמ"מ מתקיים w1=w2+w(uv)+w(t)w_1 = w_2 + w(uv) + w(t).

נכונות: אם קיים מסלול קל ביותר שעובר דרך קשת uvuv, s,u,v,,ts, \dots u, v, \dots, t אז תת המסלול שלו מ-ss ל-uu הוא מסלול קל ביותר מ-ss ל-uu ותת המסלול שלו מ-vv ל-tt הוא מסלול קל ביותר מ-vv ל-tt ולכן מתקיים w1=w2+w(uv)+w(t)w_1 = w_2 + w(uv) + w(t).

מצד שני, אם מתקיים w1=w2+w(uv)+w(t)w_1 = w_2 + w(uv) + w(t), אז מצאנו מסלול במשקל w1w_1 שעובר בקשת uvuv.

סיבוכיות: מחשבים 3 מסלולים קלים ביותר ואפשר לעשות זאת, על ידי בלמן פורד למשל, בסיבוכיות O(VE)O(VE).

1
Feedback