그래프 탐색

다익스트라 알고리즘

• 하나의 정점에서 출발해서 다른 노드들 까지의 최단 거리를 구하는 알고리즘
• 음수 가중치가 없어야 사용할 수 있다.
• 인접행렬로 구현하는 경우 시간복잡도는 O(n^2)
• 우선순위 큐를 이용하여 구현하는 경우 시간 복잡도는 O(mlogn)
  • m: edge의 수
  • n: node의 수
• 과정
  • 현재 노드와 인접 노드 중 가장 거리가 짧은 노드를 찾아 방문한다.
  • 해당 노드를 거쳐 방문할 수 있는 노드들 까지의 경로의 최솟값을 업데이트한다.
    • 즉, 기존 거리 값과 해당 노드를 거쳐 방문 노드까지 거리 값 중 최소를 해당 노드까지의 거리의 최소값으로 한다.
  • 이 과정을 반복해 도착 노드까지 경로의 최솟값을 알아낸다.
• 구현방법
  • 순차탐색 : 그냥 거리가 가장 짧은 노드를 찾는 걸 순차적으로 탐색하는 행위
  • 우선순위 큐 : 거리값을 정렬기준으로하는 우선순위 큐를 사용해서 탐색의 시간복잡도를 줄이는 것, 거리가 가장 짧은 노드를 맨 앞에 오게끔 정렬해서 사용
    • PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
    • 이런식으로 우선순위 큐를 생성하는 시점에 간단하게 compare조건을 설정할 수 있다.
      • 저렇게 정렬하면 o1[1]이 o2[1]보다 크면 o1이 o2보다 뒤에 정렬 된다.
    • 그렇기에 최단 거리 노드를 따로 탐색하는 것이 아닌 poll로 뽑아서 바로 사용하면 된다.

참고

https://velog.io/@717lumos/알고리즘-다익스트라Dijkstra-알고리즘

https://velog.io/@suk13574/알고리즘Java다익스트라Dijkstra-알고리즘

 

벨만-포드 알고리즘

• 다익스트라와 거의 다 같지만 음수 가중치를 허용한다는 특징이 있다 (단, 음수 사이클은 없어야 한다.)
• 과정
  • 처음에 시작 노드를 제외한 나머지 노드의 비용을 INF로 설정한다.
  • 현재 노드에 연결된 노드(v)로의 비용 dist[v] = min(dist[v] , dist[w]+cost[w,v])로 값을 업데이트 한다.
  • 이 과정을 정점의 개수 n개-1번 반복한다.
• 시간복잡도는 O(mn) (m:edge수, n: 노드 수)

private int[] bellmanFord(int src) {
        // 최단 거리 초기화
        int[] shortest = new int[N];
        for(int i = 0; i < N; i++) shortest[i] = Integer.MAX_VALUE;
        shortest[src] = 0;

        // 모든 간선에 대해서 N-1번 만큼 edge relaxation 한다.
        for(int i = 1; i < N; i++) {
            for(int j = 0; j < E; j++) {
                Edge edge = this.edges.get(j); // 간선 하나를 가져와서 edge relaxation을 수행한다.
                int u = edge.src;
                int v = edge.dest;
                int w = edge.weight;
                if(shortest[u] != Integer.MAX_VALUE && shortest[u] + w < shortest[v])
                    shortest[v] = shortest[u] + w;
            }
        }

        // negative-wegith cycle의 존재 유무를 확인한다.
        for(int i = 0; i < E; i++) {
            Edge edge = edges.get(i);
            int u = edge.src;
            int v = edge.dest;
            int w = edge.weight;
            // V-1 만큼 반복하여 모든 정점을 고려한 최단 거리를 찾았음에도 더 짧은 경로가 있다는 것은 음수의 사이클이 존재한다는 의미이다.
            if(shortest[u] != Integer.MAX_VALUE && shortest[u] + w < shortest[v]) {
                System.out.println("Graph contains negative weight cycle.");
                return new int[N];
            }
        }

        return shortest;
    }

출처 : https://jammdev.tistory.com/100

[Algorithm] Bellman-Ford Algorithm (벨만 포드 알고리즘)

 

플로이드-와샬

• 모든 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘
• 음수 가중치 허용( 사이클은 안된다)
• O(n^3)의 시간복잡도
• 과정
  • i를 출발지, j를 도착지, k를 경유지라 하면,
    • graph[i][j]=min(graph[i][j], graph[i][k]+graph[k][j] 로 비용을 갱신한다.
  • 이걸 경유지, 출발지, 도착지 순으로 모든 노드에 대해 반복한다.

class Solution {
    private static final int MAX = 98765432;
    private int[][] memo;

    public int solution(int n, int s, int a, int b, int[][] fares) {
        init(n, fares);

        for (int k = 1; k <= n; k++)
            for (int u = 1; u <= n; u++)
                for (int v = 1; v <= n; v++)
                    memo[u][v] = Math.min(memo[u][v], memo[u][k] + memo[k][v]);

        int answer = MAX;
        for (int k = 1; k <= n; k++) 
            answer = Math.min(answer, memo[s][k] + memo[k][a] + memo[k][b]);
        return answer;
    }

    private void init(int n, int[][] fares) {
        this.memo = new int[n+1][n+1];

        for (int i = 0; i < memo.length; i++)
            for (int j = 0; j < memo[i].length; j++)
                    memo[i][j] = (i == j)? 0 : MAX;

        for (int[] edge : fares)
            memo[edge[0]][edge[1]] = memo[edge[1]][edge[0]] = edge[2];
    }
}

참고 : https://school.programmers.co.kr/questions/33314

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%99%80%EC%83%ACFloyd-Warshall-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98