알고리즘 - Shortest Path

Shortest Path

---

최단경로

• 간선 가중치가 있는 유향 그래프에서 두 정점 사이의 최단 경로를 찾는다.

 

Dijkstra Algorithmn

• 첫 정점을 기준으로 연결되어있는 정점의 거리 정보를 min heap에 넣고 가장 작은 거리를 갖는 정점을 선택한다. (방향성이 있다는 것만 제외하면 MST의 prim알고리즘과 유사하다.)

• 시작 정점이 A일때, A -> B: 8이고, B -> E: 10이면 A -> E: 18로 갱신해준다. 

• 하나의 정점에서 다른 모든 정점들의 최저 비용을 구한다.

• 모든 간선의 가중치는 음이 아니어야하고 재방문을 허용하지 않는다.

• 수행시간: O(ElogV)

• 구현 with JAVA (백준 1753 최단 경로)

  public static void dijkstra() {
          PriorityQueue<Node> q = new PriorityQueue<>();
          dist[start] = 0;
          q.offer(new Node(start, 0));
          
          while(!q.isEmpty()) {
              Node current = q.poll();
              
              if(visited[current.x] == false) visited[current.x] = true;
              else continue;
              
              for(int i = 0; i < list[current.x].size(); i++) {
                  Node next = list[current.x].get(i);
                  if(dist[next.x] > dist[current.x] + next.cost) {
                      dist[next.x] = dist[current.x] + next.cost;//거리 값을 이전의 거리값 + 현재 비용으로 갱신해 준다.
                      q.offer(new Node(next.x, dist[next.x])); 
                  }
              }
          }
      }

 

Bellman-Ford Algorithmn

• 첫 정점을 기준으로 연결된 정점의 거리정보를 가장 작은 거리를 갖는 정보로 갱신한다. 갱신하는 과정이 모든 정점에서 부터 모든 간선의 정보를 비교하면서 진행된다.
• 이를 반복하며 음수의 싸이클이 생기면 최단 거리를 구할 수 없음을 의미한다.
• 음의 가중치를 허용한다. (방문했던 정점을 재 방문하는 것을 허용한다.)
• 최단 거리를 찾기 때문에 음수 싸이클이 있는지 확인하는 작업이 필요하다. 
• 수행시간: O(VE)
• 구현 with JAVA (백준 11657 타임머신)

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  public static boolean bellmanFord() {     dist[1] = 0; //시작점 최단거리 0으로 초기화.              //전체 n개의 노드가 있으며 노드를 선택할 때마다 거리 값을 갱신해 주어야 하므로 n - 1번 갱신을 해준다.     for(int i = 0; i < n - 1; i++) {         for(int j = 0; j < m; j++) {             Node current = nodelist[j];             if(dist[current.s] != max && dist[current.e] > dist[current.s] + current.cost) {                 dist[current.e] = dist[current.s] + current.cost;             }         }     }              //음수 싸이클이 있는지 확인     for(int i = 0; i < m; i++) {         Node node = nodelist[i];         //현재 위치의 최단거리 + 거리값이 다음 노드의 최단거리보다 작을경우 음의 싸이클이 있다고 판단한다.          if(dist[node.s] != max && dist[node.e] > dist[node.s] + node.cost) return false;     }     return true; } Colored by Color Scripter

  cs

 

Floyd-Warshall Algorithm

• 모든 간선의 정보를 배열로 저장하고 3중 반복문을 사용해 a -> b보다 a -> c -> b의 비용이 더 적다면 a -> b를 a -> c -> b로 갱신해준다.
• 모든 정점 -> 모든 정점의 최단 경로를 모두 구한다.
• 수행시간: O(n^3)
• 구현 with JAVA (프로그래머스 합승 택시 요금)

      int[][] node = new int[n + 1][n + 1];
      for(int i = 1; i < n + 1; i++) {    
          for(int j = 1; j < n + 1; j++) {
              node[i][j] = 20000001; //최대값으로 
          }
          node[i][i] = 0;//자기 자신으로 오는 거리는 항상 0
      }
          
      for(int i = 0; i < fares.length; i++) {
          node[fares[i][0]][fares[i][1]] = fares[i][2];
          node[fares[i][1]][fares[i][0]] = fares[i][2];
      }
          
      for(int k = 1; k < n + 1; k++) {
          for(int i = 1; i < n + 1; i++) {
              for(int j = 1; j < n + 1; j++) {
                  if(node[i][j] > node[i][k] + node[k][j]) {
                      node[i][j] = node[i][k] + node[k][j];
                  }
              }
          }
      }

 

reference