Dijkstra 다익스트라 (최단 경로 알고리즘)

최단경로 문제란?

두 노드를 잇는 가장 짧은 경로를 찾는 문제이다
가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

최단 경로 문제 종류

단일 출발 및 단일 도착 (single-source and single-destiantion sortest path problem) 최단 경로 문제
- 그래프 내의 특정 노드 u에서 출발, 또다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제
단일 출발 (single-source shortest path problem) 최단 경로 문제
- 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
- a와 연결된 b,c,d,e 중에서 가장짧은 경로를 찾는 것
전체 쌍 (all-pair) 최단 경로 : 그래프 내의 모든 노드 쌍 (u, v)에 대한 최단 경로를 찾는 문제

최단 경로 알고리즘

다익스트라 알고리즘

단일 출발 최단 경로 문제(2번)를 위한 알고리즘
하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제

로직

첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법
너비우선탐색(BFS)와 유사하다
- 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트
우선순위 큐를 사용한다

우선 순위 큐를 활용한 다익스트라 알고리즘

우선 순위 큐는 MinHeap방식을 활용해서 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 된다

첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
- 초기에는 첫 정점(시작정점)의 거리는 0, 나머지는 무한대로 저장한다(inf라고 표현)
- 우선순위 큐에 (첫 정점, 거리 0)만 먼저 넣는다
우선순위 큐에서 노드를 꺼낸다
- 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내진다
- 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리(현재 inf)를 비교한다
- 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다
- 배열에 해당 노드의 거리가 업데이트 된 경우, 우선순위 큐에 넣는다
2번 과정을 우선순위 큐가 비어있을때까지 반복한다

예제

1단계 _ 초기화

첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장

초기에는 첫 정점의 거리는 0, 나머지는 inf(무한대)로 저장
우선순위 큐에 (첫 정점, 거리(0))만 넣는다

2단계 (루프 시작)

우선순위 큐에서 추출한 (A, 0)노드인 첫 노드와의 거리를 기반으로 인접한 노드와의 거리 계산

우선순위 큐에서 노드를 꺼낸다
- 처음에는 첫 정점만 저장되어 있으므로, 첫 정점(A, 0)이 꺼내진다
- 첫 정점에 인접한 노드들 각각에 대해, 첫 정점과 각 노드간의 거리와 현재 배열에 저장되어있는 첫 정점과 각 노드간의 거리를 비교해준다 (실제거리 vs INF)
- 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 짧으면, 배열에 해당 노드의 거리를 변경 해준다
- 배열에 해당 노드의 거리가 변경된 경우, 우선 순위 큐에 넣어준다

3단계

우선순위 큐에서 (C, 1) 노드인 첫 노드와의 거리를 기반으로 인접한 노드와의 거리 계산

우선순위 큐가 MinHeap 방식이므로, 위 표에서 넣어진 (c,1), (d,2), (b,8)중 (c,1)이 먼저 추출된다
현재 배열에서 a-b의 거리는 8이다
- 그런데 새로운 노드 기준으로 a-c의 거리는 1, c에 인접한 b노드까지의 거리는 5이므로 a-c-b의 거리는 1+5(6)이 된다. 따라서, 8보다 작으므로 배열에 업데이트를 하고 (b, 6)을 우선순위 큐에 넣어준다
- 반대로, c-d의 거리는 2이고 a-c의 거리는 1로 a-c-d는 3인 반면 a-d는 2이므로 더 큰 경우에 해당해서 넣지 않고 무시된다

이런식으로 계속 새로운 인접노드를 확인하고 배열을 최소거리로 업데이트 해주면서 반복해준다
큐에서 꺼낸 노드의 비용이 배열에 적혀있는 비용보다 크거나 같다면 비교할 필요도없이 스킵하면된다

큐에서 꺼낸 노드까지 가는데 비용 >= 배열에 존재하는 노드까지의 비용 -> 계산 없이 스킵

구현

배열을 이용한 구현

Graph g = new Graph(8);
g.input(1, 2, 3);
g.input(1, 5, 4);
g.input(1, 4, 4);
g.input(2, 3, 2);
g.input(3, 4, 1);
g.input(4, 5, 2);
g.input(5, 6, 4);
g.input(4, 7, 6);
g.input(7, 6, 3);
g.input(3, 8, 3);
g.input(6, 8, 2);
g.dijkstra(1);

class Graph
{
	private int N;
	private int[][] maps;

	public Graph(int n)
	{
		this.N = n;
		maps = new int[N+1][N+1];
	}

	public void input (int i, int j, int w)
	{
		maps[i][j] = w;
		maps[j][i] = w;
	}

	public void dijkstra(int v)
	{
		int[] distances = new int[N+1];
		boolean[] visited = new boolean[N+1];

		for (int i = 1; i < N+1; i++)
			distances[i] = Integer.MAX_VALUE;

		distances[v] = 0;
		visited[v] = true;

		for (int i = 1; i < N+1; i++)
		{
			if (!visited[i] && maps[v][i] != 0) //방문했고 0이 아니라면 (방문했으면 무한값은 아니다)
				distances[i] = maps[v][i];
		}

		for (int all = 0; all < N-1; all++)
		{
			int min = Integer.MAX_VALUE;
			int min_idx = -1;

			for (int i = 1; i < N+1; i++) {
				if (!visited[i] && distances[i] != Integer.MAX_VALUE) {
					if (distances[i] < min){
						min = distances[i];
						min_idx = i;
					}
				}
			}
			visited[min_idx] = true;

			for (int i = 1; i < N+1; i++) {
				if (!visited[i] && maps[min_idx][i] != 0){
					if (distances[i] > distances[min_idx] + maps[min_idx][i])
					{
						distances[i] = distances[min_idx] + maps[min_idx][i];
					}
				}
			}
			for (int i = 1; i < N+1; i++)
				System.out.print(distances[i] + " ");
			System.out.println();
		}
	}
}

Priority Queue를 이용한 구현

public class Dijkstra_algorithm {
    public static void main(String[] args) throws IOException {
        Dijkstra_pq(0);
    }

    private static void Dijkstra_pq(int start) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        //정점의 개수 , 간선의 개수
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        List<Edge>[] adj = new ArrayList[V];
        for (int i = 0; i  < V; i++)
            adj[i] = new ArrayList<>();

        //간선의 출발, 도착, 가중치를 읽어들여서 그래프의 연결상태를 저장
        for (int i = 0; i < E; i++) {
            //출발 노드, 도착 노드, 가중치
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weigth = Integer.parseInt(st.nextToken());
            adj[from].add(new Edge(dest, weigth));
        }

        //우선순위 큐, 방문 체크
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        boolean[] check = new boolean[V];

        //첫노드로부터의 모든 노드들의 거리배열
        Edge[] D = new Edge[V];
        //배열중 출발 노드만 거리가 0 나머지는 최대값으로 설정
        for (int i = 0; i < V; i++){
            if (i == start)
                D[i] = new Edge(i, 0);
            else
                D[i] = new Edge(i, Integer.MAX_VALUE);
        }
        //우선순위큐에 시작 노드를 넣고 시작
        pq.add(D[start]);
        while (!pq.isEmpty())
        {
            //우선순위 큐에 가장 위에있는 노드 및 가중치를 가져온다
            Edge nowV = pq.poll();
            //edge.v에 연결되어있는 간선 리스트를 가져온다
            for (Edge nextV : adj[nowV.v]){
                //시작노드부터 다음 노드에 대한 기존 가중치보다 지금까지의 경로 + 다음 노드로의 경로 가중치 합이 더 작다면 변경
                if (!check[nextV.v] && D[nextV.v].weight > D[nowV.v].weight + nextV.weight) {
                    D[nextV.v].weight = D[nowV.v].weight + nextV.weight;
                    pq.add(D[nextV.v]);
                }
            }
            check[nowV.v] = true;
        }
        System.out.println(Arrays.toString(D));
    }
}

class Edge implements Comparable<Edge> {
    int v, weight;

    public Edge(int v, int weight) {
        this.v = v;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(this.weight, o.weight);
    }

    @Override
    public String toString() {
        return weight + " ";
    }
}

입력
4 5
0 1 2
0 2 3
1 3 1
0 3 5
1 2 1
출력
[0 , 2 , 3 , 3 ]

시간 복잡도

과정

1 각 노드마다 인접한 간선들을 모두 검사하는 과정
2 우선순위 큐에 노드/거리 정보를 넣고 삭제(poll)하는 과정

과정 1 시간복잡도

각 노드는 최대 한 번씩 방문하므로(첫노드와 해당노드간 길이 있다면), 최대 그래프의 모든 간선의 개수인 O(E)이다

과정 2 시간복잡도

우선순위 큐에 가장 많은 (노드, 거리)정보가 들어가는 경우는 그래프의 모든 간선이 검사 될 때마다, 배열의 최단 거리가 변경되고, 우선순위 큐에 (노드, 거리)가 추가되는 경우이다
따라서, 이 때 추가는 간선마다 최대 한번씩 일어날 수 있으므로 최대 O(E)의 시간이 소요되며, O(E)개의 (노드, 거리)정보에 대해 우선순위 큐를 유지하는 작업은 MinHeap유지시간인 O(logE)가 걸린다
결론적으로 O(E * logE) 이다

과정1 + 2의 시간복잡도가 소요되고 O(ElogE)의 시간이 소요된다

Author And Source

이 문제에 관하여(Dijkstra 다익스트라 (최단 경로 알고리즘)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dnstlr2933/최단-경로-알고리즘

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)