다익스트라 알고리즘 (최단 경로 알고리즘)
- 방향이 있는 가중치 그래프
- 하나의 정점에서 다른 모든 정점에 도착하는 가장 짧은 거리를 구하는 문제
- A를 선택하고, A에서 각 각의 최단 거리를 구하기 위해 자기 노드를 포함하여 모든 노드에
최단 거리를 무한대로 정해놓는다.
최소힙의 로직을 가진 우선순위 큐도 추가해준다.
(가중치의 합이 가장 작은 것을 언제든 꺼낼 수 있는 큐)
A의 가중치가 0인것은, 스스로의 노드(자기노드)로 가는 가중치는 0이기 때문..
위와같이 초기화를 해주고나서,
A,0
우선순위 큐에서 하나를 뽑는다. A,0 이므로 A노드를 기준으로 다른 노드로 갈 수 있는 모든 연결된 노드의 가중치들을 확인한다.
A에서 B로 갈 수 있는데 가중치는 8이므로, 무한대인 값보다 8이 작으므로 8로 업데이트를 해준다. 업데이트 되고나면 이 값을 그대로 우선순위 큐에 넣어준다.
이렇게 한 바퀴를 돌리고 나서, 우선순위 큐에서 하나를 뽑는다! 이번에는 C를 기준으로.
C,1
C를 기준으로 B와 D에 갈 수 있다.
B의 경우 가중치가 5이므로 1+5= 6으로 8보다 작기 때문에 업데이트 해준다.
이것을 또 우선순위큐에 배치한다.
그다음 이미 D에 2가 들어가있는데 1+2는 3이므로 3보다 2가 작기 때문에 업데이트를 하지 않는다.
더 이상 반복할 것이 없으므로 다음 반복문으로 넘어가준다.
D,2
D와 연결된 E를 보면, 2+3 = 5이기에 업데이트 해주고, 우선순위 큐에도 추가를 해준다.
D와 연결된 F를 보면, 2+5 = 7이기에 마찬가지로 업데이트 해주고 큐에 넣어준다.
E,5
E에서 F로 가는 가중치는 1이므로 5+1 = 6이 기존의 7보다 작으므로 업데이트 해준다.
B,6
우선순위 큐에서 가장 작은 값을 빼준다.
B를 가보면 B에서는 갈 수 있는 곳이 없으므로 끝낸다.
F,6
그 다음 우선순위 큐에서 뺄 값은 F에 6인데,
F를 보면 A로 갈 수 있으나 6+5= 11이므로 기존의 0보다 크기때문에 마찬가지로 마무리한다.
F,7
7도 위와같이 기존의 0보다 크므로 마무리한다.
B,8
B에서는 갈 수 있는 곳이 없으므로 마무리한다.
(위는 최종 정리 표)
위의 내용을 토대로 하여 코드로 작성해보자!
우선 가중치와 해당 노드의 이름이 담긴 클래스를 작성한다.
class Edge implements Comparable<Edge> {
public int distance;
public String vertex;
public Edge(int distance, String vertex) {
this.distance = distance;
this.vertex = vertex;
}
public String toString() {
return "vertex:"+this.vertex+", distance:" +this.distance;
}
@Override
public int compareTo(Edge o) {
return this.distance - o.distance;
}
}그래프 관련하여 해쉬맵에 담아준다.
HashMap<String, ArrayList<Edge>> graph = new HashMap<String,ArrayList<Edge>>();
graph.put("A",new ArrayList<Edge>(Arrays.asList(new Edge(8,"B"),new Edge(1,"C"), new Edge(2,"D"))));
graph.put("B", new ArrayList<Edge>());
graph.put("C", new ArrayList<Edge>(Arrays.asList(new Edge(5,"B"), new Edge(2,"D"))));
graph.put("D", new ArrayList<Edge>(Arrays.asList(new Edge(3,"E"), new Edge(5,"F"))));
graph.put("E", new ArrayList<Edge>(Arrays.asList(new Edge(1,"F"))));
graph.put("F", new ArrayList<Edge>(Arrays.asList(new Edge(5,"A"))));다익스트라 알고리즘을 구현하는 메서드 생성
public HashMap<String, Integer> dijkstraFunc(HashMap<String, ArrayList<Edge>> graph, String start) {
HashMap<String, Integer> distances = new HashMap<String, Integer>();
<4>
Edge edgeNode, adjacentNode;
int currentDistance, weight, distance;
String currentNode, adjacent;
<6>
ArrayList<Edge> nodeList;
<1> 거리 관련 빈 배열을 생성해주는 코드 (A에만 0을 넣어주고 다른 노드들은 무한대로 생성..)
for(String key: graph.keySet()) {
distances.put(key, Integer.MAX_VALUE);
}
distances.put(start,0);
<2> 우선순위 큐도 생성해줌.
PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>();
priorityQueue.add(new Edge(distances.get(start),start));
<3> 우선순위큐에 더이상 검색할 노드가 없을 때 끝내줌 -> 그동안 반복.
while(PriorityQueue.size() > 0) {
<4>
edgeNode = priorityQueue.poll();
currentDistance = edgeNode.distance;
currentNode = edgeNode.vertex;
<5>
if(distance.get(currentNode) < currentDistance) {
continue;
}
<6>
nodeList = graph.get(currentNode);
for(int i=0; i<nodeList.size(); i++) {
adjacentNode = nodeList.get(i); (edge정보)
adjacent = adjacentNode.vertex; (노드이름)
weight = adjacentNode.distance; (거리)
distance = currentDistance + weight;
// 거리값을 비교하여 가중치를 더해 기존의 저장된 배열에 있는 값보다 작은경우 업데이트 해준다!. + 우선순위큐에도 추가.
if(distance < distances.get(distance)) {
distances.put(adjacent,distance);
priorityQueue.add(new Edge(distance,adjacent));
}
}
}
return distances;
}<1>
distances 라는 해쉬맵에 key와 무한대의 큰 숫자를 넣어준 후, start노드에는 0을 넣어준다.
<2> 위의 사진처럼 우선순위 큐도 생성!
<4> priorityQueue.poll() 을 이용하여 해당 edge 정보를 가져온다! (edgeNode에 넣어줌)
currentDistance(가중치), currentNode(노드 ex..A,B...) 를 선언해준다.
<5> 현재 edge의 distance가 지금까지의 최단거리를 가진 distances.put(start,0);
의 distance보다 더 큰 값을 가지면 넘어가고, 작다면 업데이트 해준다.
<6> 현재 노드와 연결된 edge 정보를 가져온다.
시간복잡도
- 각 노드마다 인접한 간선들을 모두 검사
- 각 노드는 최대 한 번씩 방문하므로 그래프의 모든 간선은 최대 한 번씩 검사 - 우선순위 큐에 노드/거리 정보를 넣고 삭제
- 추가는 각 간선마다 최대 한 번 일어날 수 있으므로 최대 O(E)의 시간이 걸리고,
O(E)개의 노드/거리 정보에 대해 우선순위 큐를 유지하는 작업은 O(logE)가 걸린다.따라서 해당 과정의 시간 복잡도는 O(ElogE)
O(E) + O(ElogE) = O(E + ElogE) = O(ElogE)
