'Dijkstra' 태그의 글 목록

강의 출처 : 요약 : 가중치 그래프에서 사용하는 알고리즘 가중치 그래프란 ? 비용이 가장 작게 드는 경로는 ? 생각할 경우가 2가지 있다. 1. 가중치가 없는 경우 (모든 경로의 가중치는 1) 가장 짧은 경로가 가장 비용이 적게 든다. 이 경우는 이전과 동일한 BFS를 이용 2. 가중치가 있는 경우 비용이 가장 적게 드는 경로를 경유해야 한다. 간선마다 가중치가 주어진 경우 BFS를 사용하지 않고 이때 다익스트라 알고리즘을 사용해야 한다. 다익스트라 다익스트라 알고리즘은 가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최단경로를 RETURN 하는 알고리즘 방문할 수 있는 노드중에 가장 비용이 작은 곳 방문 (우선순위가 높은 곳 방문) # 다익스트라 원리 1. 우선순위큐에 시작노드 추가 우선순위큐 구현..