페이지 4의 d_t 최대 점에서 멈추었습니다. https://courses.engr.illinois.edu/cs498dl1/sp2015/notes/26-lp.pdf. 나는 절대적으로 저자 인수최단 경로 선형 프로그래밍
이 휴식 제약은 어떤 가능한 솔루션, d_v 이 s의 atmost 최단 경로 거리가 직관 다소 .Thus V에 것을 의미, 우리가 올바르게 목적 함수를 극대화하는을 따라 갈 수 없어 가장 짧은 경로를 계산하려면 !
우리는 최단 경로를 찾고 있지만 왜 우리는 최대 d_t를 느슨하게합니까?
두 개의 직접 연결된 꼭지점 s과 t 사이의 가장 짧은 경로를 다른 가장자리 나 정점없이 사용한다고 가정 해보십시오. 여기서, LP는 이것으로 귀결 d_t 극대화
maximize d_t
subject to d_s = 0
d_t − d_s ≤ l_st for every edge s -> t
유일한 방법 s에서 t로 최단 경로로 설정한다 -이 경우, 둘 사이의 가장자리. 이는 두 번째 제약 d_t ≤ l_st이 더 큰 값, 즉 s에서 t까지의 더 긴 값을 금지하기 때문입니다. t의 모든 이웃 정점을 최단 경로로 d 변수 생각해
자,이 아이디어는 s 및 t가 정점을 이웃하지 않는 일반적인 경우에 전송할 수 있습니다. 그런 다음 d_t과 관련된 조건은 전체 최단 경로를 정의하기 위해 이러한 에지 중 어느 것이 선택되어야 하는지를 결정합니다. d_t에 대한 더 높은 값이 이러한 제약 조건 중 하나 이상을 위반하는 동안 평등에 만족할 것입니다.