以下整理Constraint Graph的觀念:
1. Ax <= b,Constraint graph的vertices數目為x向量內元素個數+1。
2. 額外多出來的vertex為v0,目的為確保vertex之間都能互通。
3. Constraint graph中的edge對應一組Constraint。
4. weight的表示法:w(vi,vj) = bk,代表xj - xi = bk。(i、j、k為下標的index)。
5. 只要用找出v0到各vertex的shortest path的方法,且不能有負的edge weight,就可以找出每個vertex對應的xi的解。
沒有留言:
張貼留言