그래프의 최단 경로 탐색

• 한 정점에서 다른 한 정점까지의 최단 경로
  • 가중치가 없거나 1 인경우 BFS
  • 가중치가 양수인 경우 다익스트라
  • 가중치가 음수인 경우 벨만포드
• 모든 정점에서 다른 정점으로 최단 경로
  • 위의 알고리즘으로도 풀이 가능
  • 플로이드 와샬
• 다익스트라 알고리즘
  • 가중치가 가장 적은 노드를 우선적으로 선택하여 탐색하는 방식
  • 동작
    • 1시작 노드와 연결된 정점과의 가중치 업데이트 및 시작 노드 방문 표시
    • 2.방문한 노드에 연결된 정점들의 가중치가 작은 정점을 선택
    • 3.해당 노드로 가는 가중치 업데이트 및 방문 표시
    • 4.아직 선택되지 않은 노드가 남았다면 2,3 과정 반복
  • 구현방법
    • 우선순위 큐를 활용하여 구현 가능
    • 최단 경로로 이동해야하므로 우선순위큐 최소힙으로 구성
    • 항상 최소 가중치의 노드를 선택하여 탐색하도록 함
  • 시간 복잡도
    • 우선순위 큐를 사용하지 않으면 매번 모든 노드에서 가중치가 작은 노드를 찾기 때문에 O(V^2)이 걸림
    • 우선순위 큐를 사용하면 O(ElogV)이 걸림
      • heap을 구성하는데 logV만큼 걸리고
      • 한 정점에 연결된 간선의 개수만큼 확인하고 결국 모든 간선을 보므로 E번 걸림
• 벨만 포드 알고리즘
  • 음의 가중치도 허용하는 알고리즘
  • 이때 음의 가중치 사이클이 생기면 안됨
    • 전체 사이클을 V-1 번만큼 수행
  • 다익스트라와 유사함
  • 동작
    • V-1 만큼 반복문 수행
    • 1.시작 노드 방문 표시
    • 2.방문한 노드에 연결된 노드와의 가중치 업데이트
  • 시간복잡도
    • O(VE)
• 플로이드 와샬
• 모든 정점에서 모든 정점까지의 최단 경로를 구함
• 거쳐가는 정점을 기준으로 최단경로를 갱신
• 인접 행렬로 구성후 수행
• 동작
• for k : 1~v
•  for i : 1~v
•   for j : 1~v
•     dist(i,j) = min(dist(i,j), dist(i,k)+dist(k,j))
• k라는 점을 거쳐서 가는 경로가 i->j 가는 것보다 빠르면 갱신
• 시간 복잡도
  • O(n^3)
  • 거쳐가는 경로까지 모두 확인해야한다