다익스트라, 플루이드 워셜

다익스트라

하나의 시작점에서 여러 도착점까지 최단거리를 찾기

• 초기화
  • graph에 (노드, 거리) 형식으로 연결 정보 저장
  • distance에 각 노드까지 최소 거리 저장 (리스트)
• 다익스트라
  • heapq 사용
  • 초기화
    • 시작점을 q에 heapq.heappush로 넣음
      • heapq.heappush(q, (거리, 노드)) : q는 넣을 리스트, ()에서 첫 자리는 기준 가중치
    • distance[시작점] = 0
  • q에서 하나씩 빼면서, 뺀 곳을 거쳐서 간다고 생각하고 처리
  • distance에 저장된 값이 q에서 뺀 값보다 작으면 무시
    • heapq.heappop()으로 빼는 것이므로 이전에 처리한 내용임
  • q에서 뺀 곳과 연결된 곳을 봄 (graph를 통해서)
    • 시작점에서 q에서 뺀 곳까지 거리 + q에서 뺀 곳에서 연결된 곳까지 거리 -> cost
    • cost가 distance에 저장된 값보다 작으면
      • distance 업데이트 및 heapq에 추가

플루이드 워셜

여러 시작점에서 여러 도착점까지 최단거리 찾기

• 2차원 리스트로 보기
• DP의 일종
• map_lst[i][j] 는 i에서 j로 가는데 드는 가중치 저장
  • map_lst[i][i] 는 자기 자신에게 가므로 0
  • 입력 받은 가중치를 모두 반영하기
• 모든 노드에 대해서 거쳐가는 역할이 되는 경우 확인
  • 시작점에서 중간점까지 거리 + 중간점에서 도착점까지 거리와
  • 기존에 저장된 값이랑 비교해서 작은 값 저장하기