[2021.03.24] 최단경로알고리즘 학습

동영상 학습

• 최단 경로 알고리즘
  - 다익스트라 알고리즘
  - heap에 넣고 빼면서(그 다음 최소를 찾아) 거리를 업데이트 하는 방식
  - 다음 최소를 찾으면 거기는 이미 업데이트가 더이상 되지 않는 상태임 (그리드)
  - 한 점에서 모든 점의 최소거리를 구함
  • 플로이드 워셜 알고리즘
    • 모든 점에서 min(Pab, Pak + Pkb)를 구해 거리를 업데이트 하는 방식
      • 모든 점간의 최소거리를 구함 (최소 거리 테이블이 나옴)

문제풀이

• 합승택시요금
• 다익스트라 최단 경로 알고리즘 3회 사용하여 합치는 방법
• 다익스트라 구현 시 다음 최소 값을 찾을 때 min heap을 사용

고칠 점

• 노드는 1부터 시작했는데... 구현할 때는 0부터 시작하는 걸로 하다보니 중간에 꼬였었고.. 꼬인 부분을 그림과 매칭시킬 때 1씩 빼서 생각하는게 생각보단 쉽지 않았다.
• 가능하다면 인덱스를 일치시키는 것이 좀 더 디버깅에 유리할 듯 하다.