[알고리즘/Java] Dijkstra(다이스트라) 코드, 시간복잡도

안녕하세요. 여러분.

 

Dijkstra 알고리즘은 상당히 유명한 알고리즘에도 불구하고.. 제 마음에 드는 코드를 찾을 수 없었습니다.

Cracking the coding interview 책에 있었으면 좋았을텐데 ㅎㅎ 이상하게 dijkstra 부분에는 설명만 있고 코드가 없습니다.

유명한 Geeksforgeeks에 있는 코드도 좀 수정이 필요해 보이더라구요.

(https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-in-java-using-priorityqueue/)

 

1. edge가 없는 node가 존재하는 경우는 적용할 수 없는 코드였습니다. 아래와 같이 수정함

//while (settled.size() != V) { 
while (!pq.isEmpty()) {

 

2. 변수 이름을 좀 수정하면 좋겠습니다. 왜 u와 같은 변수 이름을 사용하여 혼란을 주는지 모르겠습니다. dijkstra의 경우에는 의미없는 변수 u, v보다는 current, next와 같이 이름을 지어 현재 노드, 다음 노드(엣지)를 나타내면 저와 같은 초보자들이 이해하기 더 좋을텐데 말이죠.

 

3. 방문한 노드를 기록하기 위해 HashSet인 settled를 사용했는데.. 굳이 HashSet을 써야했나 싶습니다. 그냥 boolean 배열이면 충분한 것 같습니다.

4. e_Neighbours() 함수의 이름도 좀 마음에 들지 않습니다. ㅜㅜ 제가 모르는 것일 수도 있지만 e가 무슨 의미로 앞에 붙었을까.. 아무리 생각해봐도 모르겠네요 ㅎㅎ;; 해당 코드를 함수로 따로 뺀 것은 호불호가 갈릴 것 같습니다. 저는 함수로 따로 빼지 않았습니다.

5. Edge의 가중치를 나타내는 변수로 cost를 사용했는데 wieght가 더 보편적인 이름이 아닌가 생각합니다.

6. Node 클래스(저는 Edge클래스로 이름을 바꿈)에서 compare()함수를 왜 복잡하게 작성했는지도 좀 의문입니다.

 

그냥 1줄로 작성 가는한 부분인데 아래와 같이 적었더라구요.

if (node1.cost < node2.cost) 
    return -1; 
if (node1.cost > node2.cost) 
    return 1; 
return 0; 

아래의 1줄 코드가 낫지 않나요?;;

return node1.cost - node2.cost;

 

어쨋든 제가 조금 손 본 코드는 아래와 같습니다. 전체를 보면 꽤나 긴 소스인데 자세히 살펴보면 중요한 부분은 dijkstra()함수 부분이며 이는 BFS에서 좀 변형된 정도입니다. Dijkstra의 수행방법을 이해하고 코드를 계속 보다보면 이해가 될 거에요.

// Java implementation of Dijkstra's Algorithm  
// using Priority Queue 
import java.util.*; 
public class DPQ { 
    private int dist[]; 
    private boolean[] visited;
    private PriorityQueue<Edge> pq; 
    private int V; // Number of vertices 
    List<List<Edge>> adj; 
  
    public DPQ(int V){ 
        this.V = V; 
        dist = new int[V]; 
        visited = new boolean[V];
        //PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
        pq = new PriorityQueue<Edge>(V, new Edge());        
    } 
  
    // Function for Dijkstra's Algorithm 
    public void dijkstra(List<List<Edge>> adj, int src){ 
        this.adj = adj; 
  
        for (int i = 0; i < V; i++) 
            dist[i] = Integer.MAX_VALUE; 
  
        // Add source edge to the priority queue 
        pq.add(new Edge(src, 0)); 
  
        // Distance to the source is 0 
        dist[src] = 0; 
        //while (settled.size() != V) { 
        while (!pq.isEmpty()) {
  
            // remove the minimum distance edge  
            // from the priority queue  
            int current = pq.remove().end; 
  
            // adding the edge whose distance is finalized 
            visited[current] = true; 
  
            for (int i = 0; i < adj.get(current).size(); i++) { 
                Edge next = adj.get(current).get(i); 
      
                // If current edge hasn't already been processed 
                if (!visited[next.end]) { 
                    // If new distance is cheaper in weight 
                    if (dist[current] + next.weight < dist[next.end]) {
                        dist[next.end] = dist[current] + next.weight;
                        // Add the current edge to the queue 
                        pq.add(new Edge(next.end, dist[next.end]));
                    }
                } 
            }
            
        } 
    } 
  
    // Driver code 
    public static void main(String arg[]){ 
        int V = 5; 
        int source = 0; 
  
        // Adjacency list representation of the  
        // connected edges 
        List<List<Edge> > adj = new ArrayList<List<Edge> >(); 
  
        // Initialize list for every edge 
        for (int i = 0; i < V; i++) { 
            List<Edge> item = new ArrayList<Edge>(); 
            adj.add(item); 
        } 
  
        // Inputs for the DPQ graph 
        adj.get(0).add(new Edge(1, 9)); 
        adj.get(0).add(new Edge(2, 6)); 
        adj.get(0).add(new Edge(3, 5)); 
        adj.get(0).add(new Edge(4, 3)); 
  
        adj.get(2).add(new Edge(1, 2)); 
        adj.get(2).add(new Edge(3, 4)); 
  
        // Calculate the single source shortest path 
        DPQ dpq = new DPQ(V); 
        dpq.dijkstra(adj, source); 
  
        // Print the shortest path to all the edges 
        // from the source edge 
        System.out.println("The shorted path from edge :"); 
        for (int i = 0; i < dpq.dist.length; i++) 
            System.out.println(source + " to " + i + " is "
                               + dpq.dist[i]); 
    } 
} 
  
// Class to represent a edge in the graph 
class Edge implements Comparator<Edge> { 
    public int end; 
    public int weight; 
  
    public Edge() 
    { 
    } 
  
    public Edge(int end, int weight) 
    { 
        this.end = end; 
        this.weight = weight; 
    } 
  
    @Override
    public int compare(Edge edge1, Edge edge2) 
    { 
        return edge1.weight - edge2.weight; //ASC
    } 
} 

 

이 코드의 시간 복잡도(Time Complexity)는 얼마일까요?

dijkstra함수의 아래부분이 시간복잡도를 결정합니다.

while (!pq.isEmpty()) { //O(|V|)

	int current = pq.remove().end; //O(log|V|)
	visited[current] = true;

	for (int i = 0; i < adj.get(current).size(); i++) { 
		...생략...
	}
} 

2중 loop가 있어 혼란스러워 보이는데 일단 밖에 있는 while() 루프먼저 보겠습니다.

이 while loop는 각 노드에 대해 1번씩 방문하게 되므로 최대 |V|(=노드의 수)만큼 실행되게 됩니다. (만약 도달 불가능한, 끊어진 노드가 있다면 V보다는 작은 수가 되겠네요)

그리고  while문 내부에는 PriorityQueue의 삭제 함수가 불립니다. Heap으로 구성된 PriorityQueue는 insert, delete 등은 O(logN)의 시간 복잡도를 가지게 됩니다.(N는 노드의 수) 

 

일단 내부 loop인 for문을 제외하면 시간 복잡도는 O(|V|log|V|)가 됩니다.

그러면 for문 내부의 시간 복잡도는 어떻게 구할 수 있을까요?

while (!pq.isEmpty()) { //O(|V|)
	..생략..
	for (int i = 0; i < adj.get(current).size(); i++) { //O(|E|)??
		Edge next = adj.get(current).get(i); 

		if (!visited[next.end]) { 
			if (dist[current] + next.weight < dist[next.end]) {
				dist[next.end] = dist[current] + next.weight;
				pq.add(new Edge(next.end, dist[next.end])); //O(log|V|)
			}
		} 
	}
} 

다소 복잡해 보이는 코드입니다. for문이 실행되는 횟수는 일정하지 않고.. 각 노드에 연결된 edge가 몇개 있느냐에 따라 달라지며 내부에 위치한 pq.add() 함수가 실행되는 경우도 복잡합니다.

 

이 경우 for문이 O(|E|) 즉, Edge의 개수만큼 실행된다고 결정내릴 수도 있습니다. 그런데 이렇게 되버리면 바깥쪽 while문을 고려하면 for문의 시간 복잡도가 O(|V|*|E|*Log|V|)가 되버립니다. 이는 O(빅오)의 정의에 따르면 틀린 값은 아니지만 우리가 원하는 tight한 시간 복잡도가 아닙니다.

왜냐하면 내부 for문은 그래프의 Edge의 총 개수만큼 실행되는게 아니라 현재 검사하는 Node에 연결된 Edge 개수만큼 실행되기 때문이죠.

바깥쪽 while문과 안쪽 for문을 자세히 봅시다. 이 2개를 연결해서 생각해보면.. 각 노드마다 연결된 edge(간선)마다 실행되는 동작임을 알 수 있습니다. 각 노드마다 연결된 간선이면.. 전체 Edge를 의미하게 됩니다. 그래서 이 부분의 시간 복잡도는 O(|E|Log|V|)가 됩니다.(for문 내부의 pq.add()는 실행될 수도 있고.. 실행이 안될 수도 있는데 그냥 실행될 수도 있다고 보는 정도까지만 고려함)

 

결국 지금까지 구한 두 시간복잡도를 더하면 O((|V|+|E|)Log|V|)가 됩니다. 이 값은 Cracking the coding Interview에 나온 값과 동일합니다.

 

생각해보면 그렇게 어렵지 않네요 ㅎㅎ

 

참고

C++ 코드 : hsp1116.tistory.com/42

다익스트라 알고리즘(Dijkstra Algorithm)