다익스트라(dijkstra) 알고리즘

mu1616·2020년 10월 17일
0

그래프/트리

목록 보기
5/5

다익스트라 알고리즘?

모든 간선의 비용이 양수일 때, 하나의 시작 정점에서 끝 정점까지의 최단 경로를 구하기 위한 알고리즘이다.

👉다익스트라 알고리즘의 원리

  • 시작정점 s 에서 끝정점 t까지의 최단 경로에 정점 x가 존재한다.
  • 이때 최단경로는 s 에서 x 까지의 최단경로와 x 에서 t 까지의 최단경로로 구성된다.
  • 즉, s -> ... -> x -> ... -> t 가 최단 경로라면 s -> ... -> x 는 무조건 최단경로이다.

알고리즘의 동작 방식

  1. 시작 정점을 선택한다.
  1. 아직 방문하지 않았고 현재 방문노드들과 인접한 정점 중에서 시작 정점과 연결했을 때 비용이 가장 낮은 정점을 선택한다.
  1. 선택한 정점을 이었다면 그것이 최단 경로가 된다.
  1. 모든 정점을 방문할 때 까지 2,3번을 반복한다.

코드

🤚 참고사항

  • 아래 코드는 동작 순서를 기술하였을 뿐 특정 언어의 문법에 종속되지 않는 수도코드 입니다.
// graph: 인접행렬, 자기 자신 외에 이어져 있지 않은 정점과의 cost는 무한으로 표시, 자기자신과는 0으로 표시
// dist : 최단 경로가 들어있는 배열, 이 배열을 점점 채워나갈 것임
// prev : 만약 경로를 추가해야한다면 prev 배열을 이용한다. 자기까지 오기 직전 노드의 값을 저장한다.
int n, graph[n][n], dist[n], prev[n]; 

void dijkstra(int start) {
    boolean visited[n];
    for(int i = 0; i < n; i++) {
    	prev[i] = -1;
        Dist[i] = Integer.MAX_VALUE;
    }
		
    // 첫 번째 정점에 대한 연결정보
    dist[start] = 0;
    visited[start] = true;
    for (int i = 0; i < V; i++) {
    	if (graph[start][i] != 0) {
            dist[i] = graph[start][i];
        }
    }

    for(int i = 0; i < n - 1; i++) {
        int minCost =  Integer.MAX_VALUE;
        int minVertex;
        for(int j = 0; j < n; j++) {
            if(!visited[j] && dist[j] < minCost) { // 아직 방문하지 않은 정점들 중에서 cost가 낮은 거 선택
                minCost = dist[j];
                minVertex = j;
            }
        }
	visited[minVertex] = true;
	// minVertex에서 갈 수 있는 경로를 포함하여 더 짧은 경로로 dist배열 업데이트
	for(int j = 0; j < n; j++) {
   	    if (!visited[j] && graph[minVertex][j] != 0) {
                if (dist[j] > dist[minVertex] + graph[minVertex][j]) {
                    dist[j] = dist[minVertex] + graph[minVertex][j];
                }
            }
        }
    }
}

시간복잡도

위 코드는 O(v^2 + E)의 시간복잡도를 가진다.
간선의 개수가 많다면 효율적인 알고리즘일 수 있겠지만 정점의 개수가 많아진다면 시간이 엄청 오래 걸린다.

따라서, 정점의 개수가 많을 경우에는 우선순위 큐를 이용하여 구현하면 된다. 이 경우에 시간복잡도는 O(E * logV) 이다.

우선순위 큐를 이용한 코드

class Node {
    int v; // vertex
    int w; // weight
}
int n, dist[n];
Arrays.fill(dist, Integer.MAX_VALUE);
List<Node>[] list; // 연결정보 저장 

void dijkstra(int start) {
    boolean visited[n];
    priority_queue pq;
    dist[start] = 0;
    pq.offer(new Node(start, 0));
    
    while(!pq.empty() {
    	Node curr = pq.pop();
        
        if(visited[curr]) continue;
        visited[curr] = true;
        
        for(Node next : list[curr.v]) {
	    if(dist[next.v] > dist[curr.v] + next.weight) {
                dist[next.v] = dist[curr.v] + next.weight;
                // 시작정점 ~ v 까지의 거리 O, curr ~ v 까지의 거리 X
                pq.offer(new Node(next.v, dist[next.v]); 
            }
        }
    }
}
profile
Enjoy!!

0개의 댓글