다익스트라 알고리즘(Dijkstra Algorithm)

☞ 최단 경로를 구하기 위해선 어떤 방법을 써야할까? 우리는 BFS(너비우선탐색)을 이용해서 어떤 한 점까지 최소 거리를 알 수 있었고, 또한 경로를 구할 수 있었다. 하지만 너비우선탐색을 이용해 구할 때는 가중치가 없을 때라는 조건이 있었다....... 가중치가 있고, 방향성 그래프일때 어떤 방식을 이용해 최단 경로, 최소 거리를 구할 수 있을까?... 여기서 다익스트라 알고리즘이 나온다. 다익스트라 알고리즘이란 그래프 간선에 가중치가 있을 때 최단 경로를 구할 수 있는 알고리즘이며, 너비 우선탐색을 조금 변형해서 만든 알고리즘이라 할 수 있다. BFS는 큐를 사용해 최단 경로를 구하는 반면, 다익스트라 알고리즘은 우선순위큐를 사용해 최단 경로를 구할 수 있다. 다익스트라의 원리를 살펴보면,,,,, 먼..