|
|
עמוד:248
שאלה 5 . 15 נתון הגרף המכוון . G = ( V , E ) פונקציית המשקל •/? + w : £ - > קובעת משקל שלם , , W ( e ) המקיים 1 < W ( e ) < 50 לכל קשת e בגרף . s 6 V הוא קדקוד נתון בגרף . א . נסמן - | V' | מספר הקדקודים בגרף . - \ E \ מספר הקשתות בגרף . כתבו אלגוריתם מילולי קצר ויעיל , בעברית מבנית , בעל סיבוביות זמן , 0 (\ V \ + \ E \ ) אשר מוצא לכל צומת v e v - { s } את משקל המסלול הקל ביותר מ- s rt הראו כי סיבוביות הזמן של האלגוריתם שהצעתם בסעיף א' היא הסיבוביות הנדרשת , ? O (\ v \ + | £ |) שאלה 5 . 16 נתון הגרף . G = ( V , E ) פונקציית המשקל W-. E ^ R * קובעת משקל ( מספר ) לכל קשת בגרף . G א . כתבו אלגוריתם יעיל , הקובע אם קשת מסוימת e נמצאת על כל המסלולים הקצרים ביותר מקדקוד המקור s לקדקוד היעד / 7 ב . נתחו את סיבוביות זמן הריצה של האלגוריתם שהצעתם בסעיף . 'א שאלה 5 . 17 נתון הגרף . G- ( V , E ) פונקציית המשקל w-. E ^ R + קובעת משקל ( מספר ) לכל קשת בגרף G כל קשת בגרף צבועה באדום או בלבן . נתונים הקדקודים 0 s בגרף G א . כתבו אלגוריתם יעיל , אשר מוצא מבין המסלולים הקצרים ביותר בין s / -ל ( ביחס למשקלות שעל הקשתות ) את המסלול שבו מספר הקשתות האדומות הוא מינימלי . ב . נתחו את סיבוביות זמן הריצה של האלגוריתם שהצעתם בסעיף . 'א
|
|