다익스트라6 [알고리즘] 다익스트라 (Dijkstra) 알고리즘 다익스트라 (Dijkstra) 모든 간선의 가중치가 '음이 아닌 경우' 의 유향 그래프 최단 경로 알고리즘 '한 정점' → '모든 정점' 까지의 최단 경로 구하기 우선순위 큐 사용O 시간복잡도 : O(E log V) 우선순위 큐 사용X 시간복잡도 : O(V ^ 2 + E) 정점 수 대비 간선의 수가 많은 경우 (간선 밀도가 높은 경우)에는 우선순위 큐를 사용하지 않는 경우가 더 빠르다. 모든 간선의 가중치가 같다면 BFS로 최단 경로를 구할 수 있지만 그렇지 않은 경우엔 다익스트라 사용 BFS 기반 그리디 알고리즘 (Greedy Algorithm) 알고리즘 시작점 start로부터의 정점들까지의 최단거리를 나타내는 dist 배열을 둔다. dist[start] = 0, 나머지는 무한대로 설정한다. queue.. 2020. 10. 2. [알고리즘] 최소비용 구하기 (백준 1916번) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 한 시작점에서 나머지 노드까지의 최소 거리를 구하는, 전형적인 다익스트라 문제다. 사실 다익스트라 문제는 이번이 처음 풀어보는데 생각보다 시간이 오래걸렸다. 계속 8%에서 넘어가질 않아서 한참 고민하고 있었는데 알고 보니 버스는 단방향인데 나는 양방향으로 생각하고 문제를 풀었다.... Solution dist 배열에서 시작점 dist[start] = 0이고 나머지는 무한대로 초기화한다. 각 노드의 edge 정보들을 저장해놓는다... 2020. 10. 2. 이전 1 2 다음
