最短路徑線性編程

Question

我被困在最大化d_t點在頁4 https://courses.engr.illinois.edu/cs498dl1/sp2015/notes/26-lp.pdf。 我絕對不能按照作者的說法

這些放寬限制意味着，在任何可行的解決方案，d_v 是atmost從s的最短路徑距離到v。因此，有些 直覺相反，我們正在正確的最大化目標函數 來計算最短路徑！

我們正在尋找最短的路徑，但爲什麼我們要爲max d_t找機會呢？

Answer 1

想象一下兩個直接連接的頂點s和t之間最短路徑的平凡情況，沒有任何其他邊或頂點。在這裏，LP歸結爲：

maximize d_t 
subject to d_s = 0 
      d_t − d_s ≤ l_st for every edge s -> t 

最大化d_t的唯一方法是將其設置爲最短路徑從s到t - 在這種情況下，兩者之間的邊緣。這是因爲第二個約束條件d_t ≤ l_st禁止任何更大的值，即從s到t的任何更長的路徑。現在

，這種想法可以被轉移到s和t不相鄰頂點的一般情形：想想d變量來的t的所有相鄰頂點最短路徑。然後與d_t有關的限制決定了必須選擇哪些邊來定義總體最短路徑。它會被平等滿足，而任何更高的值將會違反這些限制中的至少一個。