반응형 다익스트라1 [알고리즘] 다익스트라 최단거리 알고리즘(Dijkstra) 다익스트라 최단거리 알고리즘(Dijkstra) 다익스트라 알고리즘은 워낙 유명하죠 ㅎㅎ 다익스트라 알고리즘은 그래프에 있어서 탐색 시작 노드에서 탐색할 노드까지의 최단거리를 구하는 알고리즘입니다. 다익스트라 알고리즘은 실생활에서도 많이 쓰입니다. 지하철 최단거리 노선을 알려준다거나, 네비게이션 최단 경로를 알려주는 등 굉장히 활용도가 높은 알고리즘 입니다. 일단 노드간 가중치가 있어 최단거리를 구할 수 있습니다. 연결되 노드간 가중치의 합이 최단거리라고 할 수 있기 때문이죠. 아래 전체소스에 주석으로 상세히 적어놓았으나, 몇가지 포인트는 알고있어야 합니다. 원리는 다음과 같습니다. 경로를 통해 지나온 노드간 가중치들의 합이 가장 작은 값을 계속 갱신하며, 최단거리 가중치 합을 구하는 것입니다. 예를 들어.. 2018. 12. 25. 이전 1 다음 반응형