최단 경로

08 May 2023 in Study on Algorithm

###가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로(플로이드 알고리즘)

데이크스트라 알고리즘 - 단일 출발점 최단 경로 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로 구하기 시간 복잡도 : O(|V|^2)

거리 d[v]

• 출발점에서 시작하여 거리 d[]가 최소인 정점을 차례로 선택하여 최단 경로를 구하는 방법
  
  1. 초기화 -> 출발점 d[s]=0, 나머지 모든 정점 v의 d[v]=무한대, 선택 정점 집합 s={}
     
  2.