다익스트라 알고리즘2 Dijkstra 알고리즘이란 무엇인가? 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘 : 하나의 정점에서 다른 모든 정점들의 최단 경로를 구한다. 다익스트라 알고리즘의 기본 로직 : 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를 갱신하는 것이다. 정점을 잇기 전까지는 시작점을 제외한 정점들은 모두 무한 대 값을 가진다. 1. 다익스트라 알고리즘 기본 로직 시작점 : 5번 정점 5번 노드를 제외한 나머지 정점들이 가지는 최단 경로는 아직 연결되지 않았으므로 무한대이다. 1) 경로가 가장 짧은 정점을 고른다. 시작 점, 5번 노드와 연결되어 있는 노드는 2, 4번 노드이다. 2번 노드 dist[2] = min(dist[2], dist[5] + adj[5][2]) min(INF, 4) = 4 4번 .. 2021. 8. 15. Floyd 알고리즘이란 무엇인가? 플로이드(Floyd) 알고리즘 플로이드 알고리즘 : 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구한다. 다익스트라 알고리즘 : 한 시작점에서 다른 정점까지의 최단 거리를 구한다. 1) 경유점 a와 b로 연결되어 있는 간선의 비용 : 5 a와 c : 2, c 와 b : 2 => 4 a와 b로 가는데 c를 거쳐가는 것이 더 효율적이다. c와 같이 경로가 거쳐가는 정점이 경유점이라고 한다. 플로이드 알고리즘은 두 정점 사이의 어떤 경유점이 존재한다면 경유점을 거쳐가는 것을 확인하면서 더 짧은 것을 선택하게 된다. 2) 구현 위 그래프가 있을 때, 모든 쌍의 최단거리는 어떻게 될까?🤔 다익스트라 알고리즘을 이용하여 모든 정점에 대해서 구할 수 있지지만, 플로이드 알고리즘을 쓰면 보다 쉽고 빠르게 구할 수 있.. 2021. 8. 14. 이전 1 다음
