먼저 cin 속도를 줄이려면 다음라인을 추가한다.
cout 속도는 마음편히 printf를 사용한다
ios::sync_with_stdio(false);
cout 속도는 마음편히 printf를 사용한다
정의 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘 알고리즈 개요 데이크스트라 알고리즘은 각각의 꼭짓점 v에 대해 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다. 데이크스트라 알고리즘은 변 경감(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지 길이가 w(u,v)인 변 (u, v)가 존재할 때, s에서 v까지의 최단 경로는 u까지의 최단 경로에 변 (u, v)를 추가함으로써 얻을 수 있다. 이 경로의 비용은 d[u]+w(u, v)가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다. 경감 연산은 모든 변 (u, v)에 대해 한번씩 경감이 적용되어 모든 d[v]가 최단 경로의 비용을 나타내게 되었을 때 끝난다. 실행시간 개의 변과 {\displaystyle n} 개의 꼭짓점 을 가진 그래프 에 대해 대문자 O 표기법 으로 데이크스트라 알고리즘의 실행시간을 나타낼 수 있다. 가장 간단한 구현으로, Q 의 집합을 연결 리스트 나 배열 구조로 구현하고 Extract-Min(Q) 함수를 단순한 선형 탐색 으로 구현했을 때 실행 시간은 {\displaystyle O(n^{2})} 시간이 된다. 만약 희소 그래프(sparse graph), 즉 {\displaystyle n^{2}} 보다 훨씬 작은 개수의 변만을 갖는 그래프에 대해서는, 인접 리스트 와 바이너리 힙 또는 피보나치 힙 으로 구현한 우선순위 큐 를 이용해 데이크스트라 알
댓글
댓글 쓰기