최단 경로

wonjoogu·2021년 3월 22일
0

SSAFY TIL

목록 보기
5/18

최단 경로

  • 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 것
    (간선의 가중치가 없는 경로에서의 최단경로는 걸치고 걸치는 것이 최소인 것)

  • 하나의 시작 정점에서 끝 정점까지의 최단 경로

    • 다익스트라 알고리즘 : 음의 가중치 허용 x
    • 벨만-포드 알고리즘 : 음의 가중치 허용 o
  • 모든 정점들에 대한 최단 경로

    • 플로이드-워샬 알고리즘 (DP)
  • MST의 프림 알고리즘과 유사

  • 시작정점에서 거리가 최소인 정점을 선택해 나가서 정점 중심으로 해결해 나가는 알고리즘이다.
    -> 인접행렬, 인접리스트로 구현된 것이 편리

  • Dijkstras(s, A, D) -> s:시작 정점 , A 배열: 인접 행렬, D 배열: 시작정점에서의 거리

  • D는 시작정점에서 자신으로 오는 최소 비용

  • 프림에서의 minEdge : 신장트리에 포함된 정점에서 자신으로 연결하는 간선의 최소비용 ( 간선 중에 최소비용 )

  • 다익스트라 D-> 배열 0,1,2,3,4,5가 있으면 0은 0~0, 1은 0~1, 2는 0~2, 3은 0~3, 0~4, 0~5로 거쳐오는 비용 중에 가장 최소인 것을 고르는 것

  • 복습

  • MST - 크루스칼: 간선 - 간선들 마다 가중치 존재(전체 간선 중에 제일 비용이 적게 나가는 것부터 시작해서 모든 선들을 연결해놓는 것)
    - 프림 : 정점 - 정점을 정해놓고 시작해서 정점과 연결된 다른 정점 중에서 가장 최소의 비용을 갖는 것을 택하고 택하면서 해나가는 것

  • 다익스트라
    -> 음의 가중치x
    -> 시작 정점에서 부터 출발해서 또 다른 정점까지 가장 가깝게(짧게)가는 경로들을 계산(누적하고 그 값이 짧아질 때만 업데이트함)하는 것(어떤경로냐를 찾는 것, 최단 경로를 구하는 것 )(최소 비용)
    (다이렉트 or 누군가를 거쳐서 가는 경로)
    -> 경유지 개념 (해당 정점까지 다이렉트로 가거나 누구를 경유해서 가거나해서 경유지를 추가를 하면서 그게 더 짧은가?하면서 비교해가는 과정)
    D[v] <- A[s][v] : v라는게 모든 정점이 들어가있는 것
    U -> 선택된 정점 집합
    while U != V
    D[w]가 최소인 정점 w 포함 V-U를 선택

  • 맨 처음에는 시작점과 경유지가 같게 된다. 그러면 0이 된다.
    제일 작은 값인 1부터 시작해서 아직 방문하지 않은 정점들 중에서 D 배열에서 가장 작은 값을 찾아간다.

profile
SSAFY 5th

0개의 댓글