היי
אשמח להבין איך ניתן לפתור את שאלה 5ב' ממועד א' של סמסטר א של 2012
תודה רבה,
שרון
השאלה:
נתון גרף מכוון
G
ופונקציית משקל על הקשתות
w:E->R
וקודקודים
s,t
ידוע שאין ב-
G
מעגל שלילי
בנוסף, 10 מקשתות הגרף צבועות באדום.
תארו אלגוריתם יעיל למציאת מסלול קל ביותר מ
-s ל-t
מבין כל המסלולים המכילים לפחות 5 קשתות אדומות.
מעבר דרך קשת אדומה
x
פעמים נספר כקשת אדומה אחת , ולא כ-
x
קשתות אדומות במסלול.