[자료구조💾] 10장 최단 경로와 작업 네트워크

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스)

 

10.1 최단 경로 탐색 (shortest path finding)

1) 최단 경로 탐색

- 그래프의대표적인 문제 중 하나

- 탐욕 알고리즘, 다익스트라 알고리즘, 플로이드-와샬 알고리즘 등이 있음.

 

2) 탐욕 알고리즘 (Greedy algorithm)

- 출발지에서 최소 비용 간선만을 포함하여 미 방문 노드로 이동하는 경로 탐색 방법

- 목적지에 도달할 때까지 위 과정을 반복한다.

- 매 순간 최적이라고 판단하는 것을 반복적으로 선택한다.

- 지역적인 해(local solution)를 제공해줄 수 있지만, 전역적인 해(global solution)를 보장하지는 않는다.

 

3) 다익스트라 알고리즘 (Dijkstra)

- 노드 간의 최단 경로를 찾기 위해서는 출발 노드에서 각 노드에 이르는 모든 최단 경로를 탐색한다.

- n개의 정점이 존재할 때 각 노드로의 n개 최단 경로를 비용이 증가하는 순서로 생성한다.

- 간선의 비용은 음수가 아니라고 가정한다.

- 알고리즘

1. 출발 정점도 하나의경로이며 비용은 0이다.
2. 현재까지 발견된 경로에 인접 간선을 1개 추가하여 기존 경로 비용보다 큰 값 중 최소인 최단 경로를 찾는다.
3. 모든 노드에 이르는 최단 경로를 찾을 때까지 2번 과정을 반복한다.

- 코드

class Node:
  def __init__(self, node, weight):
    self.data = node
    self.weight = weight

class ShortestPath:
  def __init__(self):
    self.graph = {}
    self.visit = []
    self.dist = {}
    self.prev = []
    self.min_list = []

  def create(self, v, dest, weight):
    node = Node(dest, weight)
    if v not in self.graph:
      self.graph[v] = []
    self.graph[v].append(node)

  def dijkstra(self,v):
    if v not in self.visit:
      self.visit[v] = {}
    else:
      return
    
    if v not in self.graph:
      print("End of Search")
      return
    for node in self.graph[v]:
      vertex = node.data
      cost = node.weight
      if vertex not in self.dist or cost + self.visit[v] < self.dist[vertex]:
        self.dist[vertex] = cost + self.dist[v]
        self.prev[vertex] = v
        self.min_list[vertex] = cost + self.dist[v]
    self.view_array()

    v = self.pick_min_dist()
    self.dijkstra()

  def view_array(self):
    print('dist', sorted(self.dist.items()))
    print('prev', sorted(self.prev.items()))

  def pick_min_dist(self):
    temp = []
    for v, cost in self.min_list.items():
      temp.append((cost,v))
    
    temp = sorted(temp)
    cost, v = temp.pop(0)
    print('Next min cost vertex is', v)
    self.min_list.pop(v)
    return v
  
  def show(self):
    for no, alist in self.graph.items():
      print('[', no, ']', end=' ')
      for node in alist:
        print('(', node.data, node.weight, ')', end=' ')
      print()

 

 

10.2 플로이드-와샬 알고리즘 (Floyd-warshell)

1) 플로이드-와샬 알고리즘

- 간선에 비용이 있는 방향 그래프에서 모든 정점 간 경로를 탐색하는 방법

- 비용 행렬(cost matrix: A^-1)

• 각 원소(A^-1[i][j])에 두 정점 i, j 사이의 간선 비용이 저장되어 있는 행렬 
• A^-1[i][j] = weight(i, j)
• 정점 사이가 간선으로 연결되지 않은 경우 무한대 값을 저장한다.
• 비용 행렬 Ak의원소 Ak[i][j]에는 정점 k를 거쳐 정점 i에서 j로 가는 최단 경로 비용이 저장되어 있다.
• A^k[i][j] = min(A^k-1[i][j], A^k-1[i][k] + A^k-1[k][j]), k ≥ 0

 

2) 이행적 폐쇄 행렬 (transitive closure matrix : A⁺)

- 두 노드 사이의 경로 존재 유무를 행렬로 표현한 것

- 행렬의 원소는 두 노드 간 경로가 존재하면 1, 존재하지 않으면 0이다.

 

3) 반사 이행적 폐쇄 행렬 (reflexive transitive closure matrix : A^*)

- 자기 자신으로 가는 경로로 허용하며 이행적 폐쇄 행렬의 대각선 원소 값을 1로 지정한다.

 

 

10.3 작업 네트워크와 위상정렬

1) 작업 네트워크 (Activity network)

- 그래프의 정점 또는 간선에 작업을 표시하여 작업의 선수 관계를 표시하는 네트워크

- 정점 작업 네트워크와 간선 작업 네트워크로 나뉜다.

 

2) 정점 작업 네트워크

: 프로젝트 수행에 필요한 작업들 간에 선수 관계를 표시한 네트워크

 

3) 위상 정렬 (topology sort)

- 사이클이 없는 방향 그래프(directed acyclic graph : DAG)에서 작업들을 선수 관계에 의해 정렬하는것

- 인접 리스트로 표현된 그래프에서 위상정렬의 시간복잡도는 O(n+e)이다.

- 큐를 이용해 구현한다.

- 알고리즘

1. 차수가 0인 정점(작업)을 큐(queue)에 넣는다.
2. 큐애서 정점을 제거하고 이 정점에 연결된 간선들을 삭제한다.
3. 모든 정점을 방문하였으면 종료하고 그렇지 않으면 과정 1부터 반복한다.
4. 빈 큐 상태에서 정점을 제거하려고 하면, 그래프에 사이클이 존재한다는 오류를 출력하고 종료한다.

 

10.4 간선 작업 네트워크

1) 간선 작업 네트워크 (Activity on Edge network : AOE)

- 프로젝트 수행을 위한 작업(A)를 간선(edge)에 표시하고, 공정(V)은 정점(vertex)으로 나타낸 그래프이다.

- 특정 정점으로 들어오는 작업들이 모두 완료되어야 해당 공정을 시작할 수 있다.

- 전체 프로젝트 완료 시간에 영향을 미치는 작업들을 탐색하고 공정의 선수 관계를 분석하는 데 활용한다.

- 각 작업의 최단 시작 시간, 최장 시작 시간을 계산할 수 있다.

- 임계도(criticaliy)

• 작업의 여유 시간(slack)을 의미하는 것 
• L(i) - E(i)
• 임계 작업(critical activity) : 임계도가 0인 작업으로, 전체 프로젝트 수행 시간에 영향을 미치는 작업

 

2) 최단 시작 시간 (earlist star time : E)

- 작업 A_i를 가장 빨리 시작할 수 있는 시간 : E(i)

 

3) 최장 시작 시간 (Latest start time : L)

- 프로젝트를 지연시키지 않으면서 작업 A_i를가장늦게 시작할 수 있는시간 : L(i)