DAA-다단계 그래프

다단계 그래프 G = (V, E) 정점이 분할 된 방향성 그래프입니다. k (어디 k > 1) 분리 된 부분 집합의 수 S = {s₁,s₂,…,s_k}에지 (u, v) 가 E에있는 경우 u Є s _i 및 v Є s _{1 + 1 (} 파티션의 일부 하위 집합에 대해) 및 |s₁| = |s_k| = 1.

정점 s Є s₁ 불린다 source 그리고 꼭지점 t Є s_k 불린다 sink.

G일반적으로 가중 그래프로 간주됩니다. 이 그래프에서 모서리 비용 (i, j) 은 c (i, j)로 표시 됩니다. 따라서 소스로부터의 경로 비용은s 가라 앉다 t 이 경로의 각 모서리 비용의 합계입니다.

다단계 그래프 문제는 소스에서 최소 비용으로 경로를 찾는 것입니다. s 가라 앉다 t.

예

다단계 그래프의 개념을 이해하려면 다음 예제를 고려하십시오.

공식에 따라 비용을 계산해야합니다. (i, j) 다음 단계 사용

1 단계 : 비용 (K-2, j)

이 단계에서는 3 개의 노드 (노드 4, 5. 6)가 다음과 같이 선택됩니다. j. 따라서이 단계에서 최소 비용을 선택할 수있는 세 가지 옵션이 있습니다.

비용 (3, 4) = 최소 {c (4, 7) + 비용 (7, 9), c (4, 8) + 비용 (8, 9)} = 7

비용 (3, 5) = 최소 {c (5, 7) + 비용 (7, 9), c (5, 8) + 비용 (8, 9)} = 5

비용 (3, 6) = 최소 {c (6, 7) + 비용 (7, 9), c (6, 8) + 비용 (8, 9)} = 5

2 단계 : 비용 (K-3, j)

단계 k-3 = 2에는 두 개의 노드, 2와 3이 있기 때문에 두 개의 노드가 j로 선택됩니다. 따라서 값 i = 2 및 j = 2 및 3입니다.

비용 (2, 2) = 최소 {c (2, 4) + 비용 (4, 8) + 비용 (8, 9), c (2, 6) +

비용 (6, 8) + 비용 (8, 9)} = 8

비용 (2, 3) = {c (3, 4) + 비용 (4, 8) + 비용 (8, 9), c (3, 5) + 비용 (5, 8) + 비용 (8, 9), c (3, 6) + 비용 (6, 8) + 비용 (8, 9)} = 10

3 단계 : 비용 (K-4, j)

비용 (1, 1) = {c (1, 2) + 비용 (2, 6) + 비용 (6, 8) + 비용 (8, 9), c (1, 3) + 비용 (3, 5) + 비용 (5, 8) + 비용 (8, 9))} = 12

c (1, 3) + 비용 (3, 6) + 비용 (6, 8 + 비용 (8, 9))} = 13

따라서 최소 비용을 갖는 경로는 1→ 3→ 5→ 8→ 9.