[Algorithm] Shortest Path 3: Dijkstra

Dijkstra

• 다익스트라 알고리즘 역시 최단거리를 찾는 알고리즘이다.

 

 

Dijkstra 특징

• 음수가 없다는 전제하에 구현되었다.
• 노드들 중에서 distance 값이 최소인 노드를 찾고 relax 연산을 수행한다.
• 벨만포드와 다른점은 벨만포드는 모든 노드를 다익스트라는 최소의 값을 가진 노드에 대해 relax 연산을 한다.

 

 

수행단계

1. 시작노드 선택

2. 선택된 노드를 집합 S 에추가 (파랑색)

3. 선택된 노드와 인접한 노드 값 업데이트(빨간색)

4. 선택된 노드들과 인접한 노드중 제일 작은 delta 값을 가진 노드 선택

5, 2~4 번을 반복한다. 모든 노드가 집합 S 에 추가 되면 종료한다.

 

 

 

 

구현

 

코드

package algorithm.dijkstra;

import java.util.ArrayList;
import java.util.List;

public class Dijkstra {
    private List<List<Node>> graph = new ArrayList<>();
    private int []dist;
    private boolean []visit;
    private int maxValue = 987654321;
    private int nodeCount;

    public Dijkstra(int count) {
        nodeCount = count;
        dist = new int[count];
        visit = new boolean[count];
        for(int i = 0; i < count; i++) {
            dist[i] = maxValue;
            visit[i] = false;
            graph.add(new ArrayList<>());
        }

   }

    public void addNode(int u,int v,int w) {
        graph.get(u).add(new Node(v, w));
    }

    public int findMinDistance() {
        int minValue = this.maxValue;
        int minNodeIndex = 0;
        for (int i = 0; i < dist.length; i++) {
            if (!visit[i]) {
                if (minValue >= dist[i]) {
                    minNodeIndex = i;
                    minValue = dist[i];
                }
            }
        }

        return minNodeIndex;
    }

    public void runDijkstra(int start) {
        dist[start] = 0;
        int visitCount = 0;
        while (visitCount < nodeCount) {
            int currentNode = findMinDistance();
            if(!visit[currentNode]) {
                visit[currentNode] = true;
                visitCount++;
                for(Node node : graph.get(currentNode)) {
                    relax(currentNode, node.index, node.weight);
                }
            }
        }
    }

    public void relax(int u, int v, int w) {       // 노드에 대해 relax 연산수행
        if(dist[u] == maxValue) {                  // 방문안한 노드는 무시
            return;
        }
        if(dist[v] > dist[u]+w) {                  // delta 값 업데이트
            dist[v] = dist[u]+w;
        }
    }


    public void printDistance() {
        for(int i = 0; i <dist.length; i++) {
            System.out.println("delta of node("+i+") is "+dist[i]);
        }
    }

    class Node {
        private int index;
        private int weight;
        public Node(int index, int weight) {
            this.index = index;
            this.weight = weight;
        }
    }
}

 

 

테스트 코드

import algorithm.dijkstra.Dijkstra;

public class DijkstraTest {
    public static void main(String[] args) {

        try {

            Dijkstra dijkstra = new Dijkstra(5);
            dijkstra.addNode(0, 1, 10);
            dijkstra.addNode(0, 2, 5);
            dijkstra.addNode(1, 2, 2);
            dijkstra.addNode(1, 3, 1);
            dijkstra.addNode(2, 1, 3);
            dijkstra.addNode(2, 3, 9);
            dijkstra.addNode(2, 4, 2);
            dijkstra.addNode(3, 4, 4);
            dijkstra.addNode(4, 3, 6);

            dijkstra.runDijkstra(0);
            dijkstra.printDistance();
            System.out.println("END");
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }
}

 

 

결과

delta of node(0) is 0
delta of node(1) is 8
delta of node(2) is 5
delta of node(3) is 9
delta of node(4) is 7
END