Question

shortest_path
bellman_ford

נתונים nn משתנים x1,,xnx_1,\ldots,x_n ו-mm (mnm \geq n) אי-שוויונים מהצורה xixjckx_i - x_j \leq c_k כך ש-ckc_k מספר ממשי לכל 1km1 \leq k \leq m.

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

1

Answers

נבנה את הגרף הגרף שבו כל צומת, xix_i מייצג משתנה וקיימת קשת (xi,xj)(x_i, x_j) עם משקל ckc_k אמ"מ קיים אי-שוויון xjxickx_j - x_i \leq c_k. נוסיף צומת ss ונחבר אותה עם קשתות במשקל 00 לכל שאר הצמתים בגרף.

טענה: אם בגרף אין מעגלים שליליים אז ההשמה xiδ(s,xi)x_i \leftarrow \delta(s,x_i) מספקת את כל האי-שוויונים.

הוכחה: מאי שוויון המשולש נובע ש-δ(s,xj)δ(s,xi)+w(xjxi)\delta(s, x_j) \leq \delta(s, x_i) + w(x_jx_i).

טענה: אם בגרף קיים מעגל שלילי xi1,,xil,xi1x_{i_1}, \ldots, x_{i_l}, x_{i_1} אז לא קיימת השמה שמספקת את כל האי שוויונים.

הוכחה: נסכום את אי-השוויונים המתאימים לקשתות במעגל ונקבל ש-0<00 < 0.

אלגוריתם:

  • הרץ את אלגוריתם בלמן פורד למציאת מרחקים קלים ביותר מ-ss לשאר צמתי הגרף.
  • אם קיים מעגל שלילי החזר שלא ניתן לספק את אי השוויונים.
  • אחרת החזר את המרחקים.

נכונות: מיידית מהטענות.

סיבוכיות: O(nm)O(nm).

1
Feedback