|
|
صفحة: 222
מייצג את האורך של הכביש הזה ( המרחק בין שני היישובים . ( הבעיה היא - מהו אורך המסלול הקצר ביותר מקדקוד מקור ( יישוב מסוים ) לקדקוד אחר ( ליישוב אחר ) ברשת , בהתחשב במרחקים בין היישובים השונים . כאמור , בעיות רבות דומות באופיין לבעיה הזאת . למשל , אם המספר שמיוחס לקשת מייצג עלות לבניית כביש בין שני יישובים כלשהם , אז מאחר שלא ניתן לבנות כבישים ישירים מכל ישוב לכל ישוב אחר , עלינו לבנות , במינימום עלות , את הכבישים כך , שתהיה אפשרות להגיע מכל יישוב לכל יישוב אחר . להלן התיאור הפורמלי של הבעיה -.נתון גרף קשיר G = ( V , E ) עם קדקודים הממוספרים 0-מ עד , « -1 כלומר , | V' | = « עם פונקציית משקל , W-. E ^ R אשר מייחסת לכל קשת מספר שנכנה אותו בשם מרחק , ועם המרחקים v p i r המחברת את שני קדקודי הגרף , .. / -ו הגדרה : המשקל של המסלול = ( v , Vj , v , , V ) הוא סכום המשקלות ^ המיוחסות לקשתות , (^? - / , V ) לכל . 1 < / < k כלומר , ' w ( V , It * . מייצג את המשקל שעל הקשת w ( p ) , ( Vj _ v j (\ מייצג את המשקל של המסלול ? P נגדיר את ( יו = L ( u , אורך ( משקל ) המסלול הקצר ביותר ( המינימלי ) מהקדקוד u לקדקוד v בגרף כך אם קייס מסלול כלשהו P מהקדקוד u לקדקוד v ברשת הגדרה ; המסלול הקצר ביותר מהקדקוד u אל הקדקוד v מוגדר כמסלול p כלשהו שעבורו ( ע . w ( p ) = L ( u , כאמור , לבעיה-מסלולים קצרים גרסאות אחרות , כגון ;
|
|