[Algorithm] 그래프 최단 경로 알고리즘

두개의 노드 사이에서 가장 짧은 경로를 찾는 알고리즘

분류

• 단일 노드 ~ 단일 노드에 대한 최단 거리

  • 가중치 있음
    • 음수 가중치 없음
      • 다익스트라(Dijkstra)
    • 음수 가중치 있음
      • 벨만-포드
    • 가중치 없음
      • Breath First Search(BFS)

• 모든 노드 쌍에 대한 최단 거리

  • 플로이드 와샬(Floyd-Warshall)

Breath First Search(BFS)

다익스트라(Dijkstra)

• 단일 시작점
  • 특정 정점 ~ 모든 정점까지의 최단 경로를 구하는 알고리즘
• 시작 노드에서 최단 거리가 짧은 노드를 차례대로 선택하여 거리 계산
• 아직 방하지 않은 노드들의 최단 거리 찾는 방법
  • Priority Queue / Heap 사용
    • E개의 간선을 검사할 때 마다 우선순위 큐를 유지 -> 시간 복잡도 : $O(ElogE)$
  • 각 정점마다 인접한 간선들 탐색
    • 각 노드는 최대 한번씩 방문 -> 시간 복잡도 : $O(E)$
  • 다익스트라 시간 복잡도 : $O(E) + O(logE) = O(E~log~E)$
• BFS 기본 + 모든 가중치 양수(0 이상)
  • 음수 가중치를 가지는 간선이 존재하면 사용할 수 없음
  • 시작 노드부터 다음으로 선택되는 노드까지의 최단 거리임을 보장할 수 없기 때문
  • 이 때는 벨만-포트 알고리즘 사용

static class Node implements Comparable<Node> {
    // 노드 번호, 해당 노드까지의 가중치
    int idx, dist;

    public Node(int idx, int dist) {
      this.idx = idx;
      this.dist = dist;
    }

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

// 각 정점에서 이동할 수 있는 정점에 대한 가중치를 담은 2차원 배열
static int[][] graph;

public static int[] dijkstra(int from) {
    PriorityQueue<Node> pq = new PriorityQueue<Node>();
    int[] dist = new int[N + 1];
    boolean[] visited = new boolean[N + 1];

    // 나머지 정점은 최대값으로 초기화 
   Arrays.fill(dist, INF);

    // 시작 정점인 자기 자신에 대한 거리는 0
    dist[from] = 0;
    pq.add(new Node(from, dist[from]));

  
    // 우선순위 큐를 사용하여 아직 선택되지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
    while (!pq.isEmpty()) {
      int here = pq.peek().idx;
      int cost = pq.peek().dist;
      pq.poll();

      if (cost > dist[here])
        continue;

      
      for (int i = 1; i <= N; i++) {
        // 방문할 수 있는 노드이고, 아직 방문 전이라면
        if (graph[here][i] != INF && !visited[i]) {
          
          // (이미 계산되어있는)다음 노드로 갈 수 있는 이동 값이
          // 현재 위치한 노드의 경로 + 다음 노드로의 dist 보다 더 크다면 갱신
          // next로 가는 최소 값이 (지금 있는 노드 + next로 가는 가중치)보다 크면 최솟값으로 갱신
          if (dist[i] > (dist[here] + graph[here][i])) {
            dist[i] = dist[here] + graph[here][i];
            pq.add(new Node(i, dist[i]));
          }
        }
      }

      visited[here] = true;
    }

    return dist;
}

벨만-포드

• 단일 시작점
  • 특정 정점 ~ 모든 정점까지의 최단 경로를 구하는 알고리즘
• 음수 가중치 가능
  • 다익스크라보다 느리기 때문에 가중치 모두 양수면 다익스트라 사용하기
  • 그래프 간선이 많으면 시간 복잡도 올라가기 때문
• 해결 아이디어 : 최단 경로 = 최대 N(전체 노드 수) -1 개의 간선으로 이루어져있음 (모든 노드 방문 시)
  • 순환을 포함해서는 안되므로!!
  • 최대 이동횟수(N - 1)만큼 모든 간선을 체크하면서 노드 사이에 존재하는 간선의 가중치가 줄어들 수 있는지 확인
  • 줄어들 수 있으면 낮은 비용 반영하여 풀이 : 더 낮은 가중치로 도달할 수 있는 경우 값 갱신
    • false 를 반환해주고 아니라면 true 를 반환
  • 그 후 다시 모든 간선에 대해서 검사 진행
• 시간 복잡도
  • 최대 V번 모든 간선 E 확인 : $O(VE)$
  • |V|-1 까지만 반복
  • 그 이상이 된다면 사이클이 생기므로 멈춤
  • 각 반복에 대해서는 해당 정점과 연결되어 있는 모든 간선을 탐색

static class Node {
  // 출발노드 / 끝노드 / 간선 가중치
	int end, cost;
  
  public Node(int end, int cost) {
    this.end = end;
    this.cost = cost;
  }  
}

static int INF = 987654321;
static ArrayList<Node>[] map;

public static void main(String[] args) throws IOException {
  // 전체 노드의 개수
  int N;
  // 간선 정보의 개수
  int M;
  // 그래프 정보
  map = new ArrayList<Node>[];
  
  for (int i = 0; i <= N; i++) {
    map[i] = new ArrayList<Node>();
  }
  
  for (int i = 0; i < M; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int start = Integer.valueOf(st.nextToken());
    int end = Integer.valueOf(st.nextToken());
    int cost = Integer.valueOf(st.nextToken());
    
    // 양방향 그래프 초기화
    map[start].add(new Node(end, cost));
    map[end].add(new Node(start, cost));
  }
}

static int[] bellmanFord(int start, int N) {
  int[] dist = new int[N+1];
  
  Arrays.fill(dist, INF);
  // 그래프 시작점 0으로 초기화
  dist[start] = 0;
  
  // "전체 노드 개수 - 1" 만큼 대로 최단거리 초기화 반복
  for (int i = 1; i < N; i++) {
    
    // 최단거리 초기화
    // 간선의 개수대로 모두 반복
    for (int j = 1; j <= N; j++) {
      for (Node node : map.get(j)) {
        if (dist[j] == INF)
          continue;
        
        if (dist[road.end] > dist[j] + node.cost)
          dist[road.end] = dist[j] + node.cost;
      }
    } 
  }
  
  return dist;
}
              

플로이드 와샬(Floyd-Warshall)

• 모든 정점 ~ 정점 쌍의 최단 경로
  • 모든 정점에 대하여 다익스트다/벨만-포드 적용하는 것보다 바르게 모든 노드 쌍의 최단 거리를 계산할 수 있음
• 2차원 배열을 이용하여 i -> j 정점으로 가는 최소 비용 구함
  • i : 출발지, j : 도착지, k :경유지
  • 출발지에서 바로 도착지로 가는 경우 / 출발지에서 경유지 들려서 도착지로 가는 경우 중 최소 구함
  • $d_{k}(i, j)~=~min(~d_{k-1}(i,j),~~d_{k-1}(i,k)~+~d_{k-1}(k,j))$
  • 시간 복잡도 : $O(V^{3})$

int INF = 987654321;
// 최소 비용 담은 배열
int[][] dist = new int[][];

// 1) 배열 초기화
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    if (i = j)
      dist[i][j] = 0;
    else
      dist[i][j] = INF;
  }
}

// 2) 그래프 연결 정보 입력
for (int[] info : list) {
  int start = info[0];
  int end = info[1];
  int dist = info[2];
  
  dist[start][end] = dist;
}

// 3) 플로이드 와샬
// 경유 노드
for (int k = 0; k < n; k++) {
  // 시작 노드
  for (int i = 0; i < n; i++) {
    // 도착 노드
    for (int j = 0; j < n; j++) {
      dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
    }
  }
}