Coding1 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. 이전 1 다음
