수정 벨만 - 포드는 두 번째 에지 무게를 지원하는

Question

그래서 초기 및 최종 노드 주어, 나는에 ALG 벨만 - 포드를 사용해야합니다 : 가장 낮은 비용으로 경로를 찾기

동안

2. 특정 시간 기간

각 모서리가 비용과 시간/기간의 가중치를 가지고 아래에 남은.

그러나 이것을 최적화하는 방법을 알아낼 수는 없지만 우선 순위 대기열을 사용하는 것이 좋습니다. 휴식 기능이나 전체 프로그램을 변경합니까?

Answer 1

Bellman-Ford를 약간 수정하여 수행 할 수 있습니다. 보통 외부 루프는 N이 최대 N-1 번 실행됩니다. 여기서 N은 정점의 수입니다.

소스에서 정점까지의 거리를 저장하는 대신 각 정점에 대해 거리와 시간을 모두 저장해야합니다.

내부 루프는 약간 수정되어야한다 (dist 아래 time로 표기) - 모든 정점 위에

1. 대하여 반복.
2. 각 정점 v에 대해 이웃을 반복합니다. 각 이웃 U를 들어
은 (티맥스는 최대 허용 시간) 조건이 단지 정상 벨맨 같은 경우

if (dist[v] + cost_of_edge[v -> u] < dist[u]) then 
    if (time[v] + time_of_edge[v -> u] < Tmax) then 
     dist[u] = dist[v] + cost_of_edge[v -> u] 
     time[u] = time[v] + time_of_edge[v -> u] 
    end if 
end if 
else if (dist[v] + cost_of_edge[v -> u] == dist[u]) then 
    if (time[v] + time_of_edge[v -> u] < time[u]) then 
     time[u] = time[v] + time_of_edge[v -> u] 
    end if 
end if 

첫 번째 - 포드 : 같은에서, u에 최소 거리를 찾기 위해 노력 u에 도달하는 데 걸리는 시간을 보장하는 시간은 Tmax보다 크지 않습니다.

조건이 새로운 경우 두 번째 :의를 통과 할 시간 time[u]이 비용 dist[u]와 u에 소스에서 경로 P이며 소요 가정 해 봅시다. 이제 같은 경로 인 dist[u]을 가진 다른 경로 P'을 찾으려고하지만 time[u]보다 짧은 시간이 걸리므로 u에서 더 많은 정점에 도달 할 수 있으므로이 경로를 선택하고 싶습니다.

의 우리가 더 알고리즘,이 경우, 경로 P'을 선택하는 대신 P를 선택하지 않은 가정 해 봅시다

는, 어쩌면 다른 정점에 u에서 경로, 우리는 시간 제약으로 인해 고려하지 않을 수있는 x가 말한다. 그러나 P' 경로가 P' < 시간을 가로 지르는 데 걸리는 시간 이후로 선택되면 P을 가로 지르는 데 걸린 시간이이 경로를 고려하는 것이 가능할 수 있습니다.