Questions

Questions

student (guest) 26 Feb 2017 12:36

היי אשמח אם תוכלו לענות לי על מספר שאלות :

- האם ניתן למצוא את כל המסלולים העוברים דרך קשת מסויימת בזמן לינארי? מעגלים העוברים דרך קשת מסויימת?
- גרף המסלולים הקצרים ביותר (גרף מכוון) יכול להיות בעל מעגלים שליליים?
- כאשר אנו רוצים לתת ״עדיפות״ לקשתות (למשל כחולות) באלגוריתם דייקסטרה אנו יכולים לתקן את מיון הקשתות או להוסיף קבוע מספיק קטן כדי שלא יפגע בגרף. אשמח לדעת איך ניתן לחשב קבוע זה בצורה נכונה ובזמן לינארי.
- מדוע מציאת מסלול ארוך ביותר (או לחילופין כבד ביותר) מצומת כלשהו בגרף מכוון לוקחת זמן לינארי?
- מדוע לא ניתן לעשות את ה״טריק״ שהופך משקלים לחיוביים בשביל הפעלת דייקסטרה בג׳ונסון על מנת להפעיל רק את דייקסטרה בשביל למצוא מסלול קצר ביותר עם משקלים שליליים?

Re: Questions

RaeNye 26 Feb 2017 18:02

1) מה זה אומר בדיוק למצוא את כל המסלולים/מעגלים? אולי יש מספר אקספוננציאלי שלהם? אם הכוונה היא למצוא את קבוצת הצמתים/הקשתות X כך שלכל צומת/קשת מ-X יש מסלול שעובר גם דרכו/דרכה וגם דרך הקשת הנתונה אז BFS.
2) נניח שזה מצומת מקור s. איך מוגדר גרף מק"בים? בד"כ הוא כולל את כל הקשתות (u,v) עבורן $\delta(s,v) = w(u,v)+\delta(s,u)$, אבל מה עושים כאשר המרחקים הם $-\infty$?
3) התכוונת קרוסקל? אין שום סיבה לחשב את הקבוע הנ"ל. אם מתעקשים אז כמדומני מספיק לקחת משהו כמו $\min\{|w(e)-w(e')|\}$ אבל לשם חישוב יעיל של זה צריך למיין את הקשתות לפי סדר עולה של משקלים, כך שזה לא לינארי.
4) זו בעיה NP-קשה. אולי התכוונת בגרף אציקלי?
5) ה"טריק" הוא הרצה אחת של בלמן-פורד, ומחירו $O(|V||E|)$. זה יותר מדייקסטרה בודד, אבל פחות מ-|V| פעמים דייקסטרה.