מעגלים במשקלים שליליים
Nir (guest) 07 Sep 2012 11:56
בתרגול ראינו אלגוריתם למציאת מעגל במשקל 0, רציתי להציע פיתרון אחר ולדעת האם הוא נכון לדעתכם:
ניצור גרף שכבות, לעותק הראשון נחבר את קודקוד חדש
s
לכל שאר הקודקודים בעותק, כאשר כל קשת שיצאה במקור מקודקוד לקודקוד, כעת היא המעבר לעותק שני שבו יש את כל הקודקודים והקשתות המקוריות,
ונריץ בלמן פורד מ-
s
לכל קודקודי העותק השני ונבדוק אם יש קודקוד במשקל 0 בסיום בלמן פורד.
(אין בגרף המקורי משקלים שליליים, וכן אילצנו מעבר של קשת אחת לפחות ע"י גרף השכבות).
מה דעתכם?
תודה.