|
|
עמוד:228
אז הביטוי x מתאר את מספר הקשתות היוצאות מהקדקוד , / שדרכן עוברת הדרך ^ ^ הקצרה ביותר , ואילו הביטוי מתאר את מספר הקשתות הנכנסות לקדקוד דן ^ x fa שדרכן עוברת הדרך הקצרה ביותר . לאור המסקנה שלעיל , ברור כי לכל קדקוד , / שאינו קדקוד מקור וגם אינו קדקוד יעד , במסלול בעל אורך מינימלי , מתקיים ? . 2 L X ij = ZJ ki j k כלומר : j k מאחר שכל המסלולים הם פשוטים ואינם מכילים מעגלים , אזי מקדקוד המקור יוצאת רק קשת אחת שדרכה עוברת הדרך הקצרה ביותר , ולא קיימת קשת אשר נכנסת לקדקוד המקור ושדרכה עוברת הדרך הקצרה . לכן מתקיים : H x -T ki = 1 j A ' בנוסף , קל לראות שבקדקוד היעד נכנסת רק קשת אחת שדרכה עוברת הדרך הקצרה ביותר , ולא קיימת קשת אשר יוצאת מקדקוד היעד ושדרכה עוברת הדרך הקצרה ביותר . לכן מתקיים : j k ולסיכום , להלן הניסוח של בעיית המסלול הקצר כבעיית תכנון ליניארי ;
|
|