다익스트라 알고리즘

출발점에서 목표점까지의 최단거리를 구할 때 사용하는 알고리즘

int distance [ ] = new int [n+1]; // 최단 거리를 저장할 변수 

boolean check[ ] = new boolean[n+1];

//해당 노드를 방문했는지 체크할 변수

알고리즘 순서

1. distance는 처음에 나올 수 있는 가장 큰 값으로 초기화 하기 (Integer.MAX_VALUE)와 같은 값

2. 시작노드의 거리를 0으로 표시 (자기자신까지 거리는 0), 시작노드의 check값은 true로 바꾸기

3. 시작노드와 연결이 되어있는 노드들의 distance 값을 갱신하기

4. 방문하지 않은 노드중 distance 값이 최소인 노드(min_node)를 찾는다

5. min_node의 check값을 true로 변경한다. 그리고 min_node와 연결된 노드들 (방문이 안된) distance 값을 갱신한다.

4~5를 모든 노드가 방문할 때까지 반복한다

##하지만

distance 의 최소값을 찾는 과정이 n이다 이 과정을 log n으로 바꿀 수 있는데, 우선순위 큐로 이용하면 된다 (힙)

static class Node implements Compol{

int index, distance;

Node(int index, int distance){

this

}

@overide

pulic int compareTo(Node o){

return this.distance <= o.distance ? -1 : 1

}

}

queue(new Node(1,0);

public static void dijkstra(int start) {

while(!queue.isEmpty()) {

int current_index = queue.peek().index; // 1

queue.remove();

visit[current_index] = true;

for(int i=0; i< al.get(current_index).size(); i++) {

int next_index = al.get(current_index).get(i).index; //2

int next_distance = al.get(current_index).get(i).distance; //3

if(dist[next_index] > next_distance + dist[current_index]) 

dist[next_index] = next_distance + dist[current_index];

queue.add(new Node(next_index,dist[next_index]));

}

}

}

for(int i=1; i<=v; i++) {

if(visit[i])

System.out.println(dist[i]);

else

System.out.println("INF");

}

}

}