[알고리즘] Week 7: 고급 그래프 최단 경로 알고리즘 - 벨만-포드 알고리즘과 존슨 알고리즘

Day 1: 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

• 강의 내용:
  • 벨만-포드 알고리즘의 개념
    • 벨만-포드 알고리즘이란 무엇인가?
    • 다익스트라 알고리즘과의 차이점
    • 음의 가중치 허용
  • 벨만-포드 알고리즘의 동작 원리
    • 각 단계에서 간선의 완화 (Relaxation) 수행
    • 음의 사이클 존재 여부 검출
  • 벨만-포드 알고리즘의 시간 복잡도
    • 시간 복잡도: O(VE)
• 실습:
  • 파이썬을 사용한 벨만-포드 알고리즘 구현 및 예제

# 벨만-포드 알고리즘 구현
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def bellman_ford(self, src):
        dist = [float('inf')] * self.V
        dist[src] = 0

        for _ in range(self.V - 1):
            for u, v, w in self.graph:
                if dist[u] != float('inf') and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        for u, v, w in self.graph:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                print("Graph contains negative weight cycle")
                return

        return dist

# 예제 실행
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)

distances = g.bellman_ford(0)
if distances:
    print("벨만-포드 알고리즘 결과:")
    for i, dist in enumerate(distances):
        print(f"정점 0에서 정점 {i}까지의 거리: {dist}")

 

Day 2: 벨만-포드 알고리즘 심화

• 강의 내용:
  • 벨만-포드 알고리즘의 응용 사례
    • 금융 네트워크에서의 사이클 검출
    • 네트워크 라우팅 프로토콜
  • 벨만-포드 알고리즘의 한계
    • 음의 가중치 사이클 처리
  • 벨만-포드 알고리즘의 최적화 방법
    • 에지 리스트 활용
• 실습:
  • 다양한 그래프 구조에서 벨만-포드 알고리즘 적용

# 음의 가중치 사이클 예제
g = Graph(4)
g.add_edge(0, 1, 1)
g.add_edge(1, 2, -1)
g.add_edge(2, 3, -1)
g.add_edge(3, 0, -1)

distances = g.bellman_ford(0)
if distances:
    print("벨만-포드 알고리즘 결과:")
    for i, dist in enumerate(distances):
        print(f"정점 0에서 정점 {i}까지의 거리: {dist}")

 

Day 3: 존슨 알고리즘 (Johnson's Algorithm)

• 강의 내용:
  • 존슨 알고리즘의 개념
    • 존슨 알고리즘이란 무엇인가?
    • 모든 쌍 최단 경로 문제 해결
  • 존슨 알고리즘의 동작 원리
    • 벨만-포드 알고리즘과 다익스트라 알고리즘의 결합
    • 그래프의 재가중치 (Reweighting)
  • 존슨 알고리즘의 시간 복잡도
    • 시간 복잡도: O(V^2 log V + VE)
• 실습:
  • 파이썬을 사용한 존슨 알고리즘 구현 및 예제

import heapq

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def bellman_ford(self, src):
        dist = [float('inf')] * (self.V + 1)
        dist[src] = 0

        for _ in range(self.V):
            for u, v, w in self.graph:
                if dist[u] != float('inf') and dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

        for u, v, w in self.graph:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                print("Graph contains negative weight cycle")
                return None

        return dist[:self.V]

    def dijkstra(self, src, h):
        dist = [float('inf')] * self.V
        dist[src] = 0
        pq = [(0, src)]
        
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, weight in self.graph[u]:
                if dist[u] + weight < dist[v]:
                    dist[v] = dist[u] + weight
                    heapq.heappush(pq, (dist[v], v))
        
        for i in range(self.V):
            dist[i] += h[i] - h[src]
        
        return dist

    def johnson(self):
        new_graph = Graph(self.V + 1)
        for u, v, w in self.graph:
            new_graph.add_edge(u, v, w)
        for i in range(self.V):
            new_graph.add_edge(self.V, i, 0)
        
        h = new_graph.bellman_ford(self.V)
        if h is None:
            return
        
        for u in range(self.V):
            for i in range(len(self.graph[u])):
                v, w = self.graph[u][i]
                self.graph[u][i] = (v, w + h[u] - h[v])
        
        all_pairs_dist = []
        for u in range(self.V):
            dist = self.dijkstra(u, h)
            all_pairs_dist.append(dist)
        
        return all_pairs_dist

# 예제 실행
g = Graph(5)
g.add_edge(0, 1, -1)
g.add_edge(0, 2, 4)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 2)
g.add_edge(1, 4, 2)
g.add_edge(3, 2, 5)
g.add_edge(3, 1, 1)
g.add_edge(4, 3, -3)

distances = g.johnson()
if distances:
    print("존슨 알고리즘에 의한 모든 쌍 최단 경로:")
    for i in range(len(distances)):
        print(f"정점 {i}로부터의 거리: {distances[i]}")

 

Day 4: 존슨 알고리즘 심화

• 강의 내용:
  • 존슨 알고리즘의 응용 사례
    • 네트워크 라우팅
    • 교통 경로 최적화
  • 존슨 알고리즘의 한계
    • 대규모 그래프에서의 성능 이슈
  • 존슨 알고리즘의 최적화 방법
    • 효율적인 데이터 구조 사용
• 실습:
  • 다양한 그래프 구조에서 존슨 알고리즘 적용

# 다양한 그래프 구조 예제
g = Graph(4)
g.add_edge(0, 1, 1)
g.add_edge(1, 2, 2)
g.add_edge(2, 3, 1)
g.add_edge(3, 0, -4)

distances = g.johnson()
if distances:
    print("존슨 알고리즘에 의한 모든 쌍 최단 경로:")
    for i in range(len(distances)):
        print(f"정점 {i}로부터의 거리: {distances[i]}")

 

Day 5: 고급 그래프 최단 경로 알고리즘 종합 연습

• 강의 내용:
  • 종합 연습 문제 풀이
    • 벨만-포드 알고리즘과 존슨 알고리즘을 활용한 종합 문제
  • 고급 그래프 최단 경로 알고리즘의 응용
    • 다양한 실생활 문제에서의 응용 사례
• 실습:
  • 종합 연습 문제 해결 및 결과 분석

### 종합 연습 문제 예시
1. 주어진 그래프에서 벨만-포드 알고리즘을 사용하여 최단 경로를 구하세요.
2. 주어진 그래프에서 존슨 알고리즘을 사용하여 모든 쌍 최단 경로를 구하세요.

 

Day 6: 프로젝트 준비

• 강의 내용:
  • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 주제 및 요구사항 확정
    • 프로젝트 설계 및 계획 수립
  • 프로젝트 구현 준비
    • 데이터 구조 및 알고리즘 설계
    • 프로젝트 팀 구성 및 역할 분담
• 실습:
  • 프로젝트 주제 및 요구사항 분석
  • 프로젝트 설계 및 계획 수립

### 프로젝트 주제 예시
1. 대규모 네트워크 최적화 시스템 개발
2. 실시간 교통 경로 최적화 시스템

### 프로젝트 요구사항 예시
1. 대규모 네트워크 최적화 시스템:
   - 대규모 네트워크 데이터 입력 및 저장
   - 고급 그래프 최단 경로 알고리즘을 통한 최적화
   - 최적화된 데이터 출력 및 성능 분석

### 프로젝트 설계 및 계획 예시
1. 데이터 입력 모듈 구현
2. 고급 그래프 최단 경로 알고리즘 구현 (벨만-포드, 존슨 등)
3. 데이터 출력 및 성능 분석 모듈 구현

 

이 강의는 파이썬의 고급 그래프 최단 경로 알고리즘, 특히 벨만-포드 알고리즘과 존슨 알고리즘의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!