최단경로2 최단경로 문제: Dijkstra 알고리즘 학습 : Chan-Su Shin (신찬수): 알고리즘-자료구조 - 최단경로 Dijkstra 알고리즘 (2/3)https://www.youtube.com/watch?v=4pyBLcHXRjQ&list=PLsMufJgu5932XYejsOwcUDJ2F75f56nrl&index=50최단경로 문제 & Dijkstra 알고리즘앞에서 알아본 Bellman Ford 알고리즘은 O(n³)으로 너무 느림.왼쪽과 같은 그래프가 있다면, 아래와 같이 작동해 오른쪽 처럼 진행된다. 가장먼저 Source Node를 정하고 나머지는 Distance 무한대로 초기화한다.가장 먼저 Distance가 가장 작은 Node(a)를 선택 그 Node에서 인접한 모드 Node를 Relax다시 또 Distance가 가장 작은 Node(c)를 선택.. 2025. 4. 4. 최단경로 문제: Bellman Ford 알고리즘 학습 : Chan-Su Shin (신찬수): 알고리즘-자료구조 - 최단경로 문제 소개와 Bellman Ford 알고리즘 (1/3)https://www.youtube.com/watch?v=0NrlN88D9Fs&list=PLsMufJgu5932XYejsOwcUDJ2F75f56nrl&index=49최단경로 문제 & Bellman Ford 알고리즘위와 같은 그래프가 있을 때, a에서 i까지 가는 경로는 파란색 루트와 보라색 루트가 있다. (다른 경로는 제외한다면)보라색 루트가 최단경로가된다.dist[v]는 s에서 v로 가는 최단경로의 길이를 나타내고 이는 s에서 u로가는 최단경로와 같다. s에서 v의 최단경로를 구하기 위해선 오른쪽과 같이 s에서 u1, u2, u3로 가는 경로중에 최단 경로를 찾아야한다.그렇게.. 2025. 4. 3. 이전 1 다음
