An0401na/0203-ps-ShortestPath

🔖 다익스트라

🔍 다익스트라 알고리즘의 시간복잡도가 $O( (V+E)logV )$ 가 되는 이유는?

다익스트라 알고리즘은 우선순위큐에 간선들을 넣고 빼는 과정으로 이루어져 있다. 따라서 각각에 해당하는 과정에 드는 시간복잡도를 더해주는 방식으로 구해볼 수 있다.

1. PriorityQueue add 과정

• 최악의 경우 모든 간선들을 pq에 넣어야 하는 경우가 생기기 때문에 $ElogE$ 의 시간이 걸린다.
• $E < V^2$ 인 희소 그래프의 경우 다음과 같이 시간복잡도를 바꾸어서 쓸 수 있다.

$$ O( ElogE ) = O( ElogV^2 ) = O( 2ElogV) = O( ElogV )$$

• 따라서 우선순위큐에 간선을 넣는 시간은 (정확히 말하면 희소 그래프의 경우) $O(ElogV)$ 라고 할 수 있다.

2. PriorityQueue poll 과정

• PriorityQueue에서 한번 꺼내짐으로써 방문이 된 정점은 최솟값이 구해졌다고 보장할 수 있으므로 이후 PriorityQueue에 해당 정점이 들어가지 않는다.
• 따라서 우선순위큐에서 간선을 빼는 횟수는 정점의 갯수에 근사하게 된다.
• 그렇다면 시간 복잡도는 $O(VlogE)$ 라고 쓸 수 있다.
• 희소그래프의 경우 1번 에서의 과정을 반복해 $O(VlogV)$ 라고 쓸 수 있다.

3. 결론

• 앞서 구해진 add와 poll 과정의 시간복잡도를 더해볼 때 다익스트라 알고리즘의 시간 복잡도는

$O( (V+E)logV )$

라고 할 수 있다.

🔍 다익스트라 알고리즘의 시간복잡도를 구할 때 왜 희소그래프의 경우로 구할까?

희소그래프는 $E < V^2$ 를 만족하는 그래프이다. V개의 정점을 가지는 그래프를 생각해보자. 이 그래프에서 중복없이 만들 수 있는 최대 간선의 개수는 다음과 같다. $$Emax = _VC_2 = V(V-1)/2$$ 즉 최대로 간선을 만들어도 $V^2$ 이 되지 않기 때문에 밀집 그래프가 되려면 중복간선이 필요하게 된다. 하지만 최단 경로를 구하는 다익스트라 알고리즘의 특성상 중복간선 중 가장 비용이 적은 간선만 알고리즘에 들어가 계산을 해도 답이 나오기 때문에 밀집 그래프 또한 희소 그래프로 다익스트라 알고리즘을 적용할 수 있게 된다. 이와 같은 이유로 시간복잡도를 계산할 때 희소 그래프의 경우로 계산하게 된다.

🔍 다익스트라 알고리즘에 음수간선이 있을 때 왜 사용할 수 없을까?

다익스트라 알고리즘에서는 현재 갈 수 있는 정점 중 최소 비용을 가지는 정점을 찾아 방문을 하고 그 곳에서 갈 수 있는 정점들의 최소 비용을 갱신한다. 이 때 방문된 정점은 최소 비용이 구해졌다는 것을 보장하기 때문에 이후 다시 방문하지 않고 최솟값 또한 갱신되지 않는다. 하지만 음수인 간선이 있다면 방문이 되었어도 추후 음수간선으로 인해 더 적은 비용이 나올 수 있지만 방문되었기 때문에 갱신되지 못하므로 최적의 해를 구할 수 없다.

위와 같은 예시의 그래프에서 A 정점에서 출발할 경우 먼저 C가 방문되게 되고 비용의 최솟값은 4로 확정된다. 하지만 이후 B->C 간선으로 -90 비용이 나올 수 있음에도 불구하고 이미 방문된 C 정점의 최솟값은 갱신되지 않는다.

🔖 벨만 포드

🔍 벨만 포드 알고리즘에서 간선 순회를 V-1 번 반복하는 이유는?

한 정점에서 다른 정점까지 가는데 최대 V-1 개의 간선을 거칠 수 있기 때문이다. V번 이상의 간선을 거쳐 방문한다면 중복된 간선을 거쳤다는 말이기 때문에 최소비용이라고 할 수 없다. 즉, 한 정점에서 다른 정점까지 가는 최소 비용을 구하기 위해 가능한 경로들을 모두 탐색하기 위해서는 V-1 번 까지 반복을 할 수 있어야 한다.

🔖 플로이드 워셜

🔍 플로이드 워셜 알고리즘에서 음수 간선 사이클을 판별할 수 있는 방법은?

음수 간선 사이클이 없다면 한 정점이 자기 자신으로 오는 비용은 항상 0이 되어야만 한다. 하지만 음수 간선 사이클이 존재하면 자기 자신으로 돌아오는 dist[i][i] 값이 0보다 작은 음수값을 갖게 된다. 이를 통해 음수 간선 사이클의 유무를 판단할 수 있다.