Dijkstra Algorithm (1) 썸네일형 리스트형 [알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 다음과 같은 도시들과 그 도시들끼리 이어주는 도로망이 있다고 해보자. A 도시에서 F 도시를 방문한다고 하자. 최단 거리를 찾아서 방문한다면 시간이 절약될 것이다. 그러므로, C 도시를 거쳐서 F 도시로 가는 것이 가장 짧은 경로이다. 이때의 거리는 도로의 길이의 합이 가장 짧은 60km가 된다. 가중치 그래프에서도 마찬가지이다. 한 정점 v에서 각 정점들까지의 최단 경로를 구하고자하는 경우가 있다. v에서 각 정점까지의 가중치들을 더하고, 그 가중치가 가장 작으면 최단 거리가 된다. 이렇게 한 시작 정점 v에서 모든 다른 정점들 까지의 최단 경로를 구하는 알고리즘이 다익스트라 알고리즘(Dijkstra Algorithm)이다. 단, 모든 가중치가 음수가 아닐 경우에 사용이 가능하다. .. 이전 1 다음