다익스트라(Dijkstra)

음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘

 

1. 출발위치 지정

2. 출발점에서 연결되있는 점과 값 저장

3. 가장 가까운 점 힙에서 poll

4. 현재 저장된 거리보다 짧으면 갱신하고, 가까운 점 저장

5. (3,4) 반복

 

static void Dijkstra(int N) {
		//N개의 점, 출발점1
		
		int INF = (int)1e10;
		
		int [][] path = new int [N+1][N+1]; //연결되있는 점들의 거리 
		
		int [] D = new int [N+1];
		
		for(int i = 1; i <= N; i++) {
			D[i] = INF;
		}
		
		PriorityQueue<Distance> pq = new PriorityQueue<>();
		
		pq.add(new Distance(1,0));
		
		while(!pq.isEmpty()) {
			Distance curr = pq.poll();
			if(D[curr.dest] < curr.dis) continue;
			D[curr.dest] = curr.dis;
			for(int i = 1; i <= N; i++) {
				if(path[curr.dest][i]<INF) {
					pq.add(new Distance(i,curr.dis+path[curr.dest][i]));
				}
			}
		}
		
	}

 

시간복잡도 - O(ElogV)