<div id="readability-page-1" class="page"><div><h3 id="다익스트라-최단경로-알고리즘은">다익스트라 최단경로 알고리즘은?</h3>
<ul>
<li>하나의 정점에서 다른 모든 정점으로 가는 최단경로를 탐색</li>
<li>즉, 정해진 출발점에서부터 도달할 수 있는 모든 도착점까지의 최단경로를 탐색하는 경우 사용</li>
<li>다만, 정점과 정점 사이의 간선이 음수인 경우에는 사용 불가</li>
</ul>
현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 인공위성, GPS 등에서 사용되는 실용적인 알고리즘입니다.
<h3 id="다이나믹-프로그래밍dp">다이나믹 프로그래밍(DP)</h3>
<ul>
<li>하나의 최단거리는 여러개의 최단거리의 합</li>
<li>다익스트라는 최단경로 탐색을 위해 이전까지 구했던 최단 거리 정보를 그대로 사용 =&gt; DP의 개념</li>
</ul>
<img src="https://user-images.githubusercontent.com/74946802/116486513-c8292f80-a8c8-11eb-9cbc-964656ea58aa.png"><ul>
<li>1에서 3으로 이동하는 최단경로의 현재 값은 7</li>
<li>1에서 2로 이동하는 최단경로의 현재 값은 3</li>
<li>2에서 3으로 이동하는 최단경로의 현재 값은 1</li>
<li>1에서 2를 통해 3으로 이동하면, 1에서 3으로 바로 이동하는 경우보다 적은 값으로 이동 가능하기 때문에 최단경로 값이 4로 업데이트</li>
<li>즉, 특정거리까지의 최단경로를 탐색하기 위해 이전까지 구해졌던 최단거리 정보를 그대로 사용</li>
</ul>
<h3 id="구현">구현</h3>
<ul>
<li>출발점을 설정</li>
<li>출발점에서 부터 모든 도착점까지의 최단거리를 설정</li>
<li>방문하지 않은 노드를 모두 탐색<ul>
<li>간선의 경로 값이 가장 적은 값부터 탐색</li>
</ul></li>
<li>해당 노드에서부터 도달 가능한 노드의 모든 경로값 업데이트</li>
</ul>
<img src="https://user-images.githubusercontent.com/74946802/116486961-cd3aae80-a8c9-11eb-990a-bd9dc20193a7.png"><ul>
<li>1을 출발점으로 모든 노드까지의 최단경로는<ul>
<li>1에서 1까지 최단경로 =&gt; 0</li>
<li>1에서 2까지 최단경로 =&gt; 1</li>
<li>1에서 3까지 최단경로 =&gt; 2</li>
<li>1에서 4까지 최단경로 =&gt; 3</li>
<li>1에서 5까지 최단경로 =&gt; 불가(이 경우 무한대 값으로 설정)</li>
</ul></li>
<li>즉, [0, 1, 2, 3, INF]가 출발점으로부터 모든 노드까지의 최단경로 값</li>
</ul>
<img src="https://user-images.githubusercontent.com/74946802/116487143-3f12f800-a8ca-11eb-991f-abbadc630b60.png"><ul>
<li>
위에서 언급한 대로 가장 작은 최단경로 값(1)을 가진 정점 2부터 탐색
<ul>
<li>1에서 2로의 이동비용 =&gt; 1</li>
<li>2에서 4로의 이동비용 =&gt; 1</li>
<li>1에서 2를 거쳐 4로 이동하는 비용 =&gt; 2</li>
<li>1에서 4로 바로 이동하는 비용 =&gt; 3</li>
<li>2를 거칠 때 비용이 바로 이동하는 비용보다 적기때문에</li>
<li>최단거리 정보 업데이트</li>
<li>[0, 1, 2, 2, INF]</li>
</ul>
</li>
<li>
정점 2에서 도달 가능한 정점인 5번으로의 이동비용 탐색
<ul>
<li>1에서 2로의 이동비용 =&gt; 1</li>
<li>2에서 5로의 이동비용 =&gt; 3</li>
<li>1에서 2를 거쳐 5로 이동하는 비용 =&gt; 4</li>
<li>1에서 5로 바로 이동하는 비용 =&gt; 무한대</li>
<li>2를 거칠 때 비용이 바로 이동하는 비용보다 적기때문에</li>
<li>최단거리 정보 업데이트</li>
<li>[0, 1, 2, 2, 4]</li>
</ul>
</li>
</ul>
이런 방식으로 최단거리 정보가 갱신된다.
<h3 id="활용-문제">활용 문제</h3>
<ul>
<li><a href="https://programmers.co.kr/learn/courses/30/lessons/12978?language=python3">다익스트라를 활용하여 연습해볼 문제</a></li>
</ul>
<h3 id="풀이코드">풀이코드</h3>
<ul>
<li>최소힙을 사용해야 dijkstra의 시간복잡도가 O(nlogn)<ul>
<li>단, 이 경우에도 다수의 노드가 존재할 때 각 노드 들이 서로 다른 노드와 적은 수로 연결되어 있을 경우에 한해서 O(nlogn)</li>
</ul></li>
<li>Swift의 경우 간단하게 힙구조를 제공하는 라이브러리가 없기 때문에 선형탐색을 통하여 풀이 진행</li>
<li>반드시 힙 구조가 필요한 경우엔, 미리 구현해둔 heap구조를 가져와 사용(제약사항 등의 이유로 불가능할 경우는 python활용 추천)</li>
<li>선형탐색을 사용하는 경우 O(n2)</li>
</ul>
<pre><code>func solution(_ N:Int, _ road:[[Int]], _ k:Int) -&gt; Int {
 var graph = [[(Int, Int)]](repeating: [(Int, Int)](repeating: (0, 0), count: N+1), count: N+1)
 let maxNum = 9999999
 for node in road {
 let (a, b, cost) = (node[0], node[1], node[2])
 if graph[a].first! == (0, 0) {
 graph[a] = [(b, cost)]
 } else {
 graph[a].append((b, cost))
 }
 if graph[b].first! == (0, 0) {
 graph[b] = [(a, cost)]
 } else {
 graph[b].append((a, cost))
 }
 }
 
 var distance = [Int](repeating: maxNum, count: N+1)
 distance[1] = 0
 var queue = [(0, 1)]
 
 
 while !queue.isEmpty {
 queue.sort(by: &gt;)
 let (dist, now) = queue.removeLast()
 
 if distance[now] &lt; dist {
 continue
 }
 
 for node in graph[now] {
 let updateCost = dist + node.1
 if updateCost &lt; distance[node.0] {
 distance[node.0] = updateCost
 queue.append((updateCost, node.0))
 }
 }
 }
 return distance.filter{$0&lt;=k}.count
}</code></pre></div></div>

PS & Algorithm

WooSeok Suh

다익스트라 최단경로 알고리즘은?
하나의 정점에서 다른 모든 정점으로 가는 최단경로를 탐색
즉, 정해진 출발점에서부터 도달할 수 있는 모든 도착점까지의 최단경로를 탐색하는 경우 사용
다만, 정점과 정점 사이의 간선이 음수인 경우에는 사용 불가
현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 인공위성, GPS 등에서 사용되는 실용적인 알고리즘입니다.
다이나믹 프로그래밍(DP)
하나의 최단거리는 여러개의 최단거리의 합
다익스트라는 최단경로 탐색을 위해 이전까지 구했던 최단 거리 정보를 그대로 사용 => DP의 개념
1에서 3으로 이동하는 최단경로의 현재 값은 7
1에서 2로 이동하는 최단경로의 현재 값은 3
2에서 3으로 이동하는 최단경로의 현재 값은 1
1에서 2를 통해 3으로 이동하면, 1에서 3으로 바로 이동하는 경우보다 적은 값으로 이동 가능하기 때문에 최단경로 값이 4로 업데이트
즉, 특정거리까지의 최단경로를 탐색하기 위해 이전까지 구해졌던 최단거리 정보를 그대로 사용
구현
출발점을 설정 
출발점에서 부터 모든 도착점까지의 최단거리를 설정
방문하지 않은 노드를 모두 탐색
간선의 경로 값이 가장 적은 값부터 탐색
해당 노드에서부터 도달 가능한 노드의 모든 경로값 업데이트
1을 출발점으로 모든 노드까지의 최단경로는
1에서 1까지 최단경로 => 0
1에서 2까지 최단경로 => 1
1에서 3까지 최단경로 => 2
1에서 4까지 최단경로 => 3
1에서 5까지 최단경로 => 불가(이 경우 무한대 값으로 설정)
즉, [0, 1, 2, 3, INF]가 출발점으로부터 모든 노드까지의 최단경로 값
위에서 언급한 대로 가장 작은 최단경로 값(1)을 가진 정점 2부터 탐색
1에서 2로의 이동비용 => 1
2에서 4로의 이동비용 => 1
1에서 2를 거쳐 4로 이동하는 비용 => 2
1에서 4로 바로 이동하는 비용 => 3
2를 거칠 때 비용이 바로 이동하는 비용보다 적기때문에
최단거리 정보 업데이트
[0, 1, 2, 2, INF]
정점 2에서 도달 가능한 정점인 5번으로의 이동비용 탐색
1에서 2로의 이동비용 => 1
2에서 5로의 이동비용 => 3
1에서 2를 거쳐 5로 이동하는 비용 => 4
1에서 5로 바로 이동하는 비용 => 무한대
2를 거칠 때 비용이 바로 이동하는 비용보다 적기때문에
최단거리 정보 업데이트
[0, 1, 2, 2, 4]
이런 방식으로 최단거리 정보가 갱신된다.
활용 문제
다익스트라를 활용하여 연습해볼 문제
풀이코드
최소힙을 사용해야 dijkstra의 시간복잡도가 O(nlogn)
단, 이 경우에도 다수의 노드가 존재할 때 각 노드 들이 서로 다른 노드와 적은 수로 연결되어 있을 경우에 한해서 O(nlogn)
Swift의 경우 간단하게 힙구조를 제공하는 라이브러리가 없기 때문에 선형탐색을 통하여 풀이 진행
반드시 힙 구조가 필요한 경우엔, 미리 구현해둔 heap구조를 가져와 사용(제약사항 등의 이유로 불가능할 경우는 python활용 추천)
선형탐색을 사용하는 경우 O(n2)
func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
 var graph = [[(Int, Int)]](repeating: [(Int, Int)](repeating: (0, 0), count: N+1), count: N+1)
 let maxNum = 9999999
 for node in road {
 let (a, b, cost) = (node[0], node[1], node[2])
 if graph[a].first! == (0, 0) {
 graph[a] = [(b, cost)]
 } else {
 graph[a].append((b, cost))
 }
 if graph[b].first! == (0, 0) {
 graph[b] = [(a, cost)]
 } else {
 graph[b].append((a, cost))
 }
 }
 var distance = [Int](repeating: maxNum, count: N+1)
 distance[1] = 0
 var queue = [(0, 1)]
 while !queue.isEmpty {
 queue.sort(by: >)
 let (dist, now) = queue.removeLast()
 if distance[now] < dist {
 continue
 }
 for node in graph[now] {
 let updateCost = dist + node.1
 if updateCost < distance[node.0] {
 distance[node.0] = updateCost
 queue.append((updateCost, node.0))
 }
 }
 }
 return distance.filter{$0<=k}.count
}

다익스트라 - 최단거리

댓글