נתון גרף קשיר עם צמתים 1 , 2 n ומרחקים C . > 0 לכל קשת ( נ , ו ) המחברת צמתים - ו i נ . יש למצוא את הדרך הקצרה ביותר מהמקור ( צומת ( 1 ליעד צומת וו . לדו גמה , יש למצוא את הדרך הקצרה ביותר מצומת 1 לצומת , 8 כאשר ליד כל צלע מסמנים את אורך הצלע . לא תמיד הארכים מציינים דרך . למעשה ישנם שימושים לבעיה , שבהם המספרים מציינים זמנים , עלויות , וכו י . נ יסוח כגעית תכנות לינארי מיתרון בעית הדרך הקצרה הוא בדיוק כאילו היינו רוצים להעביר יחידת זרם אחת מהמקור ליעד . 1 אם הדרך הקצרה עוברת דרך ענף ( i , j ) יהי - x X .. ij > 0 אחרת הבעיה x .. א * מ : לכל ענף ( i , j ) כך שיתקיים : הבעיה הדואלית מצא y , y כר שיתקיים n Max iy - y y } n s . t . לכל ענף ( נ , ו ) y . - y . < C . . ברשת J J y ( i = 1 ,..., n ) אינם מוגבלים בסימן , ^
אל הספר