algorithm
벨만 포드 알고리즘
수색…
비고
유향 그래프 G 가 주어지면 주어진 노드 A 에서 그래프의 나머지 노드까지의 최단 거리를 찾고 싶습니다. Dijkstra 알고리즘은 최단 경로를 찾는 가장 유명한 알고리즘이지만 주어진 그래프의 에지 가중치가 음수가 아닌 경우에만 작동합니다. Bellman-Ford 는 가중치의 일부가 음수 일지라도 지정된 노드 (존재하는 경우)에서 최단 경로를 찾는 것을 목표로합니다. 그래프에 음의주기가있는 경우 최단 거리가 존재하지 않을 수 있습니다 (이 경우 순환을 따라 가면서 총 거리가 무한히 짧아 질 수 있음). Bellman-Ford는 또한 우리가 그러한주기의 존재를 결정할 수있게 해줍니다.
알고리즘의 총 복잡도는 O(V*E) . 여기서 V -는 꼭짓점 수 및 E 가장자리 수입니다
단일 소스 최단 경로 알고리즘 (그래프에 음의 사이클이 있음)
이 예를 읽기 전에 가장자리 완화에 대한 간단한 아이디어가 필요합니다. 여기 에서 배울 수 있습니다.
Bellman-Ford Algorithm은 단일 소스 버텍스에서 가중치가있는 다이 그래프의 다른 모든 버텍스까지의 최단 경로를 계산합니다. Dijkstra 's Algorithm 보다 느리지 만 가장자리의 무게가 음수이고 그래프에서 음의 가중치 사이클을 발견하는 경우에도 작동합니다. Dijkstra 's 알고리즘의 문제는 부정적인 사이클이 반복되면 사이클을 계속 반복하면서 두 개의 정점 사이의 거리를 줄이는 것입니다.
이 알고리즘의 아이디어는 임의의 순서로이 그래프의 모든 가장자리를 하나씩 살펴 보는 것입니다. 무작위 순서 일 수 있습니다. 그러나 uv ( u 와 v 가 그래프의 두 정점 인 경우)가 주문 중 하나 인 경우 u 에서 v 까지의 모서리가 있어야합니다. 대개 주어진 입력의 순서에서 직접 가져옵니다. 다시 말하지만 임의의 임의 순서로 작동합니다.
순서를 선택하면, 우리는 이완 식에 따라 에지 이완된다. u 에서 v로 진행하는 주어진 에지 uv에 대해 이완 수식은 다음과 같습니다.
if distance[u] + cost[u][v] < d[v]
d[v] = d[u] + cost[u][v]
즉, 소스 에서 임의의 정점 u + 에지 uv 의 무게까지의 거리가 소스 에서 다른 정점 v 까지의 거리보다 작은 경우 소스 에서 v 까지의 거리를 업데이트합니다. 우리는 최대 (V-1) 배의 가장자리를 완화 해야합니다. 여기서 V 는 그래프의 가장자리 수입니다. 왜 (V-1) 물어 보시겠습니까? 다른 예를 들어 설명하겠습니다. 또한 우리는 어떤 꼭지점의 부모 꼭지점을 추적 할 것입니다. 즉, 가장자리를 풀 때 우리는 다음을 설정합니다 :
parent[v] = u
그것은 우리가 u 를 통해 v 에 도달하는 또 다른 짧은 길을 발견했다는 것을 의미합니다. 소스 에서 정점으로가는 최단 경로를 인쇄하려면 나중에이 작업이 필요합니다.
예를 살펴 보겠습니다. 그래프가 있습니다. 
소스 정점으로 1 을 선택했습니다. 소스 에서 다른 모든 정점까지의 최단 경로를 찾고 싶습니다.
처음에 d [1] = 0 이기 때문에 소스입니다. 그리고 우리는 아직 거리를 알지 못하기 때문에 휴식은 무한 합니다.
이 시퀀스에서 가장자리를 완화합니다.
+--------+--------+--------+--------+--------+--------+--------+
| Serial | 1 | 2 | 3 | 4 | 5 | 6 |
+--------+--------+--------+--------+--------+--------+--------+
| Edge | 4->5 | 3->4 | 1->3 | 1->4 | 4->6 | 2->3 |
+--------+--------+--------+--------+--------+--------+--------+
원하는 모든 순서를 취할 수 있습니다. 우리가 한 번 가장자리를 휴식을 취하면, 우리는 무엇을합니까? 소스 에서 최대 1 개의 가장자리를 사용하는 경로의 다른 모든 정점까지의 거리를 구합니다. 이제 가장자리를 풀고 d [] 값을 업데이트합시다. 우리는 얻는다 :
- d [4] + 비용 [4] [5] = 무한대 + 7 = 무한대 . 우리는 이것을 업데이트 할 수 없습니다.
- d [2] + 비용 [3] [4] = 무한대 . 우리는 이것을 업데이트 할 수 없습니다.
- d [1] + 비용 [1] [2] = 0 + 2 = 2 < d [2] . 그래서 d [2] = 2 입니다. 또한 parent [2] = 1 입니다.
- d [1] + 비용 [1] [4] = 4 . 그래서 d [4] = 4 < d [4] . parent [4] = 1 .
- d [4] + 비용 [4] [6] = 9 . d [6] = 9 < d [6] . parent [6] = 4 .
- d [2] + 비용 [2] [2] = 무한대 . 우리는 이것을 업데이트 할 수 없습니다.
d[u] + cost[u][v] < d[v] 조건이 일치하지 않아 일부 정점을 업데이트 할 수 없습니다. 이전에 말했듯이 소스 에서 다른 노드까지의 경로는 최대 1 에지를 사용합니다. 
두 번째 반복은 2 개의 노드를 사용하여 경로를 제공합니다. 우리는 얻는다 :
- d [4] + 비용 [4] [5] = 12 < d [5] . d [5] = 12 이다. parent [5] = 4 .
- d [3] + 비용 [3] [4] = 1 < d [4] . d [4] = 1 이다. parent [4] = 3 .
- d [3] 은 변하지 않는다.
- d [4] 는 변하지 않는다.
- d [4] + 비용 [4] [6] = 6 < d [6] . d [6] = 6 이다. parent [6] = 4 .
- d [3] 은 변하지 않는다.
우리의 그래프는 다음과 같습니다 : 
3 번째 반복은 d [5] 가 8 일 때만 꼭지점 5를 업데이트합니다. 우리의 그래프는 다음과 같습니다 : 
얼마나 많은 반복이 있더라도 우리는 같은 거리를 가질 것입니다. 업데이트가 발생하는지 여부를 확인하는 플래그를 유지합니다. 그렇지 않다면 루프를 해제 할 것입니다. 우리의 의사 코드는 다음과 같습니다.
Procedure Bellman-Ford(Graph, source):
n := number of vertices in Graph
for i from 1 to n
d[i] := infinity
parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
flag := false
for all edges from (u,v) in Graph
if d[u] + cost[u][v] < d[v]
d[v] := d[u] + cost[u][v]
parent[v] := u
flag := true
end if
end for
if flag == false
break
end for
Return d
부정 사이클을 추적하기 위해 여기에 설명 된 절차를 사용하여 코드를 수정할 수 있습니다 . 완료된 의사 코드는 다음과 같습니다.
Procedure Bellman-Ford-With-Negative-Cycle-Detection(Graph, source):
n := number of vertices in Graph
for i from 1 to n
d[i] := infinity
parent[i] := NULL
end for
d[source] := 0
for i from 1 to n-1
flag := false
for all edges from (u,v) in Graph
if d[u] + cost[u][v] < d[v]
d[v] := d[u] + cost[u][v]
parent[v] := u
flag := true
end if
end for
if flag == false
break
end for
for all edges from (u,v) in Graph
if d[u] + cost[u][v] < d[v]
Return "Negative Cycle Detected"
end if
end for
Return d
인쇄 경로 :
정점에 대한 최단 경로를 인쇄하려면 NULL 을 찾아서 정점을 인쇄 할 때까지 부모로 다시 반복합니다. 의사 코드는 다음과 같습니다.
Procedure PathPrinting(u)
v := parent[u]
if v == NULL
return
PathPrinting(v)
print -> u
복잡성:
에지 최대 값 (V-1) 을 완화해야하므로이 알고리즘의 시간 복잡도는 O (V * E) 와 같을 것입니다. 여기서 adjacency list 를 사용하여 그래프를 나타내는 경우 E 는 에지 수를 나타냅니다. 그러나 adjacency matrix 을 사용하여 그래프를 나타낼 경우 시간 복잡도는 O (V ^ 3)가 됩니다. 이유는 adjacency list 을 사용할 때 O (E) 시간에 모든 가장자리를 반복 할 수 있지만 adjacency matrix 을 사용할 때 O (V ^ 2) 시간이 걸립니다.
왜 우리는 대부분 (V-1) 번에 모든 가장자리를 이완시켜야합니까?
이 예제를 이해하려면 여기 에서 찾을 수있는 Bellman-Ford 단일 소스 최단 경로 알고리즘에 대한 간단한 아이디어를 얻는 것이 좋습니다 .
Bellman-Ford 알고리즘에서 최단 경로를 찾으려면 그래프의 모든 가장자리를 완화 해야합니다. 이 프로세스는 최대 (V-1) 번 반복됩니다. 여기서 V 는 그래프의 정점 수입니다.
소스 에서 다른 모든 정점까지의 최단 경로를 찾는 데 필요한 반복 횟수는 가장자리를 완화 하기 위해 선택한 순서에 따라 다릅니다.
예제를 살펴 보겠습니다.
여기에서 소스 정점은 1입니다. 소스 와 다른 모든 정점 사이의 최단 거리를 찾습니다. 꼭지점 4 에 도달하기 위해, 최악의 경우, (V-1) 개의 가장자리를 취할 것입니다. 이제 가장자리가 발견 된 순서에 따라 정점 4 를 발견하는 데 (V-1) 번 걸릴 수 있습니다. 알았어? Bellman-Ford 알고리즘을 사용하여 여기에서 최단 경로를 찾으십시오.
우리는이 시퀀스를 사용할 것입니다 :
+--------+--------+--------+--------+
| Serial | 1 | 2 | 3 |
+--------+--------+--------+--------+
| Edge | 3->4 | 2->3 | 1->2 |
+--------+--------+--------+--------+
첫 번째 반복 :
- d [3] + 비용 [3] [4] = 무한대 . 아무것도 바뀌지 않을거야.
- d [2] + 비용 [2] [3] = 무한대 . 아무것도 바뀌지 않을거야.
- d [1] + 비용 [1] [2] = 2 < d [2] . d [2] = 2 이다. parent [2] = 1 .
우리의 이완 과정은 단지 d [2] 만 바뀌 었음을 알 수 있습니다. 우리의 그래프는 다음과 같습니다 : 
두 번째 반복 :
- d [3] + 비용 [3] [4] = 무한대 . 아무것도 바뀌지 않을거야.
- d [2] + 비용 [2] [3] = 5 < d [3] . d [3] = 5 이다. parent [3] = 2.
- 그것은 변경되지 않습니다.
이번에 이완 과정은 d [3]으로 바뀌었다. 우리의 그래프는 다음과 같습니다 : 
세 번째 반복 :
- d [3] + 비용 [3] [4] = 7 < d [4] . d [4] = 7 이다. parent [4] = 3 .
- 그것은 변경되지 않습니다.
- 그것은 변경되지 않습니다.
3 번째 반복은 마침내 1 에서 4 로 최단 경로를 찾았습니다. 우리의 그래프는 다음과 같습니다 : 
따라서 최단 경로를 찾는 데는 3 번의 반복이 필요했습니다. 이 후, 몇 번이나 가장자리를 풀어도 d [] 의 값은 그대로 유지됩니다. 이제 우리가 다른 시퀀스를 고려한다면 :
+--------+--------+--------+--------+
| Serial | 1 | 2 | 3 |
+--------+--------+--------+--------+
| Edge | 1->2 | 2->3 | 3->4 |
+--------+--------+--------+--------+
우리는 얻을 것이다 :
- d [1] + 비용 [1] [2] = 2 < d [2] . d [2] = 2 이다.
- d [2] + 비용 [2] [3] = 5 < d [3] . d [3] = 5 이다.
- d [3] + 비용 [3] [4] = 7 < d [4] . d [4] = 5 이다.
첫 번째 반복은 소스 에서 다른 모든 노드까지 최단 경로를 찾았습니다. 1-> 2 , 3-> 4 , 2-> 3의 순서 가 가능하며, 2 회 반복 한 후 최단 경로를 제공합니다. 시퀀스를 정렬하는 방법에 관계없이이 예제에서 소스 에서 최단 경로를 찾는 데 3 번 이상 걸리지 않을 것이라는 결정을 내릴 수 있습니다.
최선의 경우 소스 로부터 최단 경로를 찾는 데 1 반복이 걸린다는 결론을 얻을 수 있습니다. 최악의 경우, 그것은 (V-1) 회 반복을 취할 것이기 때문에 우리는 이완 (V-1) 회 과정을 반복합니다.
그래프에서 음수주기 감지
이 예제를 이해하려면 여기 에서 찾을 수있는 Bellman-Ford 알고리즘에 대한 간단한 아이디어를 얻는 것이 좋습니다 .
Bellman-Ford 알고리즘을 사용하면 그래프에 음수 사이클이 있는지 감지 할 수 있습니다. 최단 경로를 찾으려면 그래프 (V-1) 시간의 모든 가장자리를 완화 해야합니다. 여기서 V 는 그래프의 정점 수입니다. 우리는 이미이 예제 에서 (V-1) 회 반복 이후에 반복 횟수가 아무리 많아도 d []를 업데이트 할 수 없다는 것을 보았습니다. 아니면 우리가 할 수 있을까요?
그래프에 음의 사이클이있는 경우, (V-1) 회 반복 한 후에도 d []를 업데이트 할 수 있습니다. 이것은 모든 반복에 대해 음수 사이클을 통과하면 항상 최단 경로의 비용이 감소하기 때문에 발생합니다. 이것이 Bellman-Ford 알고리즘이 반복 횟수를 (V-1)로 제한하는 이유입니다. 여기서 Dijkstra 's Algorithm 을 사용하면 무한 루프에 빠지게됩니다. 그러나 부정적인주기를 찾는 데 집중하십시오.
우리는 그래프를 가지고 있다고 가정 해 봅시다 :
꼭지점 1 을 소스 로 선택해 봅시다. Bellman-Ford의 단일 소스 최단 경로 알고리즘을 그래프에 적용한 후 소스 에서 다른 모든 정점까지의 거리를 확인합니다.
이것은 그래프가 (V-1) = 3 회 반복 된 것과 같은 모양입니다. 4 개의 가장자리가 있기 때문에 결과가되어야합니다. 최단 경로를 찾으려면 최대 3 번 반복해야합니다. 그래서 이것은 대답이거나 그래프에 음의 가중치 순환이 있습니다. 그것을 (V-1) 회 반복 한 후에, 우리는 마지막 반복을 한 번 더하고, 거리가 계속 감소하면 그래프에 음의 가중 사이클이 있음을 의미합니다.
예를 들어 우리는 체크하면 2-3, D [2] + 선정 [2] [3] 우리 D보다 1를 제공한다 [3]. 따라서 우리 그래프에는 음의주기가 있다고 결론을 내릴 수 있습니다.
그렇다면 우리는 어떻게 부정적인주기를 발견 할 수 있습니까? Bellman-Ford 절차에 약간 수정합니다 :
Procedure NegativeCycleDetector(Graph, source):
n := number of vertices in Graph
for i from 1 to n
d[i] := infinity
end for
d[source] := 0
for i from 1 to n-1
flag := false
for all edges from (u,v) in Graph
if d[u] + cost[u][v] < d[v]
d[v] := d[u] + cost[u][v]
flag := true
end if
end for
if flag == false
break
end for
for all edges from (u,v) in Graph
if d[u] + cost[u][v] < d[v]
Return "Negative Cycle Detected"
end if
end for
Return "No Negative Cycle"
이것은 그래프에 음의주기가 있는지를 확인하는 방법입니다. 또한 Bellman-Ford 알고리즘을 수정하여 부정적인 사이클을 추적 할 수 있습니다.