• Shortest Path Algorithm

  그래프 G=(V, E)와 정점 s가 주어졌을 때, s로부터 G안의 모든 정점에 이르는 최단 경로를 찾는 문제

  • Unweighted graph

    가중치 최단 경로 문제 중 모든 간선의 가중치가 1인 특별한 경우

    BFS와 유사하며, distance table같은 데이터 구조가 별도로 필요

    시작 정점으로부터 거리가 계산된 정점들이 저장되고, 그들의 인접 정점들이 검사됩니다.

• Weighted graph

  Dijkstar algorithm : BFS를 일반화한 것

  # 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘
  # 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단경로 찾기
  # 최단 거리는 여러 개의 최단 거리로 이루어져 있다.
  # 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용
  # 현재까지 알고 있던 최단 경로를 계속해서 갱신
  
  # 1. 출발 노드 설정
  # 2. 출발 노드를 기준으로 각 노드의 최소 비용 저장
  # 3. 방문하지 않은 노드중에서 가장 비용이 적은 노드 선택
  # 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신
  # 5. 3~4번 반복
  
  mygraph = {
      'A': {'B': 8, 'C': 1, 'D': 2},
      'B': {},
      'C': {'B': 5, 'D': 2},
      'D': {'E': 3, 'F': 5},
      'E': {'F': 1},
      'F': {'A': 5}
  }
  
  import heapq
  
  def dijkstra(graph, start):
      distances = {node: float('inf') for node in graph}
      distances[start] = 0
      queue = []
      heapq.heappush(queue, [distances[start], start])
  
      while queue:
          current_distance, current_node = heapq.heappop(queue)
  
          if distances[current_node] < current_distance:
              continue
  
          # distance 계산
          for adjacent, weight in graph[current_node].items():
              distance = current_distance + weight
  
              # distances 갱신
              if distance < distances[adjacent]:
                  distances[adjacent] = distance
                  heapq.heappush(queue, [distance, adjacent])
  
      return distances
  
  print(dijkstra(mygraph, 'A'))
  

  unweight graph의 경우와 비슷하게 distance table 이용

  시작점으로부터 정점 v의 (weight를 고려한) 최단 거리를 distance table에 저장하면서 동작

  Distance[v]의 값은 s로부터 v까지의 거리

  시작점으로부터 자신에 이르는 최단 거리는 0

  distance table의 다른 모든 정점은 -1이 저장되어 이 정점들이 아직 처리되지 않았음을 나타냄

• Minimum Spanning Tree

  어떤 그래프의 spanning tree는 모든 정점을 포함하고 있는 sub-graph이면서 또한 tree입니다.

  한 그래프에는 여러 spanning tree가 있을 수 있습니다.

  여러 spanning tree중 weight의 합이 가장 작은 것

  해결하는 두 개의 유명한 알고리즘

  • Kruskal Algorithm

  Minimum Spanning Tree를 만드는 동안 매번 최소 weight를 가지는 edge를 선택해서 그 edge가 사이클을 만들지 않는다면 트리에 추가

  # 가장적은 비용으로 모든 노드를 연결하는 알고리즘
  # 비용을 기준으로 먼저 오름차순으로 정렬
  # 정렬된 순서에 맞게 그래프에 포함
  # 포함시키 전에 사이클 테이블 확인 (union find 이용)
  # 사이클을 형성하는 경우 간선을 포함하지 않음
  
  def getParent(parent, num):
      if parent[num] == num:
          return num
      else:
          return getParent(parent, parent[num])
  
  def unionParent(parent, num1, num2):
      a = getParent(parent, num1)
      b = getParent(parent, num2)
      if a < b:
          parent[b] = a
      else:
          parent[a] = b
  
  def findParent(parent, num1, num2):
      a = getParent(parent, num1)
      b = getParent(parent, num2)
  
      if a == b:
          return True
      elif a != b:
          return False
  
  mygraph = {
      'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'],
      'edges': [
          (7, 'A', 'B'),
          (5, 'A', 'D'),
          (7, 'B', 'A'),
          (8, 'B', 'C'),
          (9, 'B', 'D'),
          (7, 'B', 'E'),
          (8, 'C', 'B'),
          (5, 'C', 'E'),
          (5, 'D', 'A'),
          (9, 'D', 'B'),
          (7, 'D', 'E'),
          (6, 'D', 'F'),
          (7, 'E', 'B'),
          (5, 'E', 'C'),
          (7, 'E', 'D'),
          (8, 'E', 'F'),
          (9, 'E', 'G'),
          (6, 'F', 'D'),
          (8, 'F', 'E'),
          (11, 'F', 'G'),
          (9, 'G', 'E'),
          (11, 'G', 'F')
      ]
  }
  
  # 간선의 비용 오름차순으로 정렬
  mygraph['edges'].sort()
  
  # 각 정점이 포함된 그래프가 어디인지 저장
  parents = dict()
  for vertice in mygraph['vertices']:
      parents[vertice]=vertice
  
  for edge in mygraph['edges']:
      if not findParent(parents, edge[1], edge[2]):
          unionParent(parents, edge[1], edge[2])
          print(edge)
  

  • Prim Algorithm

  Dijkstra algorithm과 비슷하게 거리와 경로 값을 distance table에 저장

  For each vertex v, Distance[v] is the minimum weight of any edge connecting v to vertex in the current tree

BEFORE

17강 정렬