|
|
עמוד:247
כתבו אלגוריתם מילולי , קצר ויעיל בעברית מבנית , אשר מחזיר את התשובה TRUE אס כל המסלולים הקצרים ביותר X-n זדו עוברים דרך 1 Z אוזרת , הוא מחזיר את התשובה . FALSE שאלה 5 . 14 הגרף G מוגדר על-ידי . G = ( V , E ) פונקציית המשקל W : £ - >/? + קובעת משקל ( מספר ) לכל קשת בגרף . G לפניכם רשת 'rt מצאו את כל המסלולים הקצרים ביותר מן הקדקוד A לקדקוד Y ברשת הנתונה . תארו כל מסלול כזה בנפרד , באופן סכמתי , בצורה של רשימה ליניארית מקושרת . ב . S הוא קדקוד בגרף . { S & V ) נסמן לכל מסלול P מקדקוד S לקדקוד ? . a W ( P ) מסמן את משקל המסלול ( כלומר את סכום משקלי הקשתות של מסלול UP ) מסמן את אורך המסלול ( כלומר את מספר הקשתות במסלול XP כתבו אלגוריתם מילולי קצר ויעיל , בעברית מבנית , המוצא לכל קדקוד ( asV ) a את הערך המינימלי האפשרי של : ? W ( P ) + L ( P ) : ™> ron בנו גרף חדש , ; G' = ( V \ F ) , 6 " מצאו את הערך W ( P ) + L ( P ) המינימלי האפשרי , < 7-ב וציינו מה מכיל V" ומה מכיל . E
|
|