반응형 [알고리즘] 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.. 2024. 6. 2. [알고리즘] Week 11: 그래프 알고리즘 II - 최단 경로 알고리즘과 최소 스패닝 트리 Day 1: 최단 경로 알고리즘 개요강의 내용:최단 경로 문제 정의최단 경로 문제란 무엇인가?단일 출발점 최단 경로와 모든 쌍 최단 경로 문제의 차이최단 경로 알고리즘의 응용 사례네비게이션 시스템네트워크 라우팅실습:최단 경로 문제를 해결할 기본적인 그래프 준비# 기본적인 그래프 준비graph = { 'A': {'B': 1, 'C': 4}, 'B': {'A': 1, 'C': 2, 'D': 5}, 'C': {'A': 4, 'B': 2, 'D': 1}, 'D': {'B': 5, 'C': 1}} Day 2: 다익스트라 알고리즘 (Dijkstra's Algorithm)강의 내용:다익스트라 알고리즘의 개념다익스트라 알고리즘의 정의 및 작동 원리우선순위 큐를 이용한 구현다익스트라 알고리즘의 시간.. 2024. 6. 2. [알고리즘] 8. 최단 경로 알고리즘 Index 1. 최단 경로 문제 2. 다익스트라 최단 경로 3. 플로이드 워셜 4. 벨만 포드 5. 추천 문제 6. 참고자료1. 최단 경로 문제최단 경로 문제- 가장 짧은 경로를 찾는 알고리즘- 각 지점은 그래프에서 node로 표현, 지점 간 연결된 도로는 edge로 표현 (최단 경로 유형)- 한 지점에서 다른 한 지점까지의 최단 경로- 한 지점에서 다른 모든 지점까지의 최단 경로- 모든 지점에서 다른 모든 지점까지의 최단 경로 2. 다익스트라 최단 경로Djikstra- 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산- 음의 간선이 없을 때 정상적으로 동작- 매 상황에서 방문하지 않은 가장 적은 비용이 드는 노드를 선택(그리디)- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 .. 2023. 10. 5. 이전 1 다음 반응형
