[Advanced] 7. 그래프의 최소 비용 문제 - 이론편

그래프에서 최소 비용 문제

• 최소 신장 트리 문제 : 모든 정점들을 연결하는 간선들의 가중치의 합이 최소가 되는 트리
• 최단 경로 문제 : 시작 정점에서 목표 정점까지 가는 간선의 가중치의 합이 최소가 되는 경로

---

최소 신장 트리 문제

신장 트리 (Spanning Tree)
n 개의 정점을 포함하는 무향 그래프에서 n개의 정점과 n-1개의 간선으로 구성된 트리

최소 신장 트리 (Minimun Spanning Tree)
가중치의 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리
→ 프림과 크루스칼 알고리즘

 

프림 알고리즘

한 정점에 연결된 간선들 중 하나씩 선택하면서 최소 신장 트리를 만들어가는 방식

1. 임의의 정점을 하나 선택
2. 선택한 정점들과 인접하는 정점들 중에 최소 비용의 간선이 존재하는 정점 선택
3. 모든 정점이 선택될 때 까지 두 번째 과정 반복

동작 과정

# D : 출발점에서 각 정점까지 최단 경로 가중치 합을 저장
# P : 최단 경로 트리 저장

def MST_Prim(G, s):  # G 그래프, s 시작정점
    D = [Inf] * N  # 가중치를 무한대로 초기화
    P = [None] * N  
    visited = [False] * N  # 방문여부 초기화
    D[s] = 0  # 시작 정점의 가중치 0으로 설정

    for _ in range(N):  # 정점의 개수만큼 반복
        minIndex = -1
        min = Inf
        for i in range(N):  # 방문 안한 정점중 최소 가중치 정점 찾기
            if not visited[i] and D[i] < min:
                min = D[i]
                minIndex = i
        visited[minIndex] = True  # 방문 처리
        for v, val in G[minIndex]:  # 선택 정점의 인접 정점
            if not visited[v] and val < D[v]:
                D[v] = val  # 가중치 갱신
                P[v] = minIndex  # 트리에서 연결될 부모 정점

알고리즘 적용 예

pi : 정점이 트리에 연결될 때 사용된 간선정보 저장
key : pi에 저장된 간선의 가중치 저장 

 

크루스칼 알고리즘

최소 가중치 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘

N개의 정점을 포함하는 그래프에서 N-1개의 간선을 선택하는 방식
간선을 선택해 나가는 과정에 여러 개의 트리들이 존재

동작 과정

def MST_Kruskal(G):
    mst = []
    
    for i in range(N):
        Make_Set(i)
        
    G.sort(key = lambda t: t[2])   # 가중치 기준으로 정렬
    mst_cost = 0
    
    while len(mst) < N-1:
        u, v, val = G.pop(0)    # 최소 가중치 간선 가져오기
        if Find_Set(u) != Find_Set(v):
            Union(u, v)
            mst.append((u,v))
            mst_cost += val

알고리즘 적용 예

---

최단 경로 문제

간선의 가중치가 있는 유향 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로

단일 시작점 최단 경로 문제	모든 쌍 최단 경로 문제
출발점에서 다른 모든 정점들에 이르는 최단 경로를 구하는 문제 - 다익스트라 알고리즘 : 음의 가중치 x - 벨만-포드 알고리즘 : 음의 가중치 o, 가중치 합이 음 x	모든 정점 쌍 간의 최단 경로를 구하는 것 - 플로이드 - 워샬 알고리즘

 

다익스트라 알고리즘

시작 정점에서 거리가 최소인 정점부터 선택해 나가면서 최단 경로를 구하는 방식
탐욕 기법을 사용한 알고리즘으로, 최소 신장 트리를 구하는 프림 알고리즘과 유사
시작 정점(r)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재
최단 경로는 r에서 x까지의 최단 경로와 x에서 t까지의 최단 경로로 구성

 

알고리즘

시작점에서의 최단 경로를 찾은 정점들의 집합 S를 관리

• 최초 S = {r}, d[r] = 0, d[v] = Inf
• 집합 S에 포함되지 않은 정점들 중에 출발점에 가장 가까운 정점 선택
• 최단 경로를 찾은 정점을 하나씩 집합 S에 추가

 

동작 과정

# D : 출발점에서 각 정점까지 최단 경로 가중치 합을 저장
# P : 최단 경로 트리 저장

def Dijkstra(G, r):
    D = [Inf]*N
    P = [None]*N
    visited = [False]*N
    D[r] = 0
    
    for _ in range(N):
        minIndex = -1
        min = Inf
        for i in range(N):
            if not visited[i] and D[i] < min:   # 방문하지 않은 정점 중 최소값 선택
            min = D[i]
            minIndex = i
        visited[minIndex] = True
        for v, val in G[minIndex]:   # minIndex에서 v까지 val만큼 가중치
            if not visited[v] and D[minIndex] + val < D[v]:
                D[v] = D[minIndex] + val
                P[v] = minIndex

 

벨만-포드 알고리즘

음의 가중치를 포함하는 그래프에서 최단 경로를 구함

• 하지만, 가중치의 합이 음인 사이클은 허용하지 않음
• 다익스트라로 최단 경로를 구할 수 있다면 벨만-포드로 가능

출발점에서 각 정점까지 간선 하나로 구성된 경로만 고려해서 최단 경로를 구함

최대 간선 두 개까지 고려해서 최단 경로를 구해나가고, 최대 간선 N-1개 까지 고려한 경로들에서 최단 경로를 구함

• 동적 계획법 적용

탐욕 기법이 적용된 다익스트라보다 많은 시간 소요