최단 경로 문제

최단 경로 문제

다익스트라 알고리즘

• 시작점부터 출발해 목표점까지의 거리 구하기

  구하는 방법

• 우선순위 큐 사용

  다익스트라 코드

All-Pairs Shortest Paths

• 모든 쌍에 대하여 최단 경로 구하는 알고리즘

  증명 방법

  1. 다익스트라 알고리즘을 n번 호출(음의 가중치X)
  • O(VElogV)
    1. Bellman-Ford 알고리즘을 n번 호출
  • O(V(VE))
    1. Floyd-Warshall 알고리즘 사용
  • O(V(V(V)))
  • 수도코드

    // D: 최단거리를 저장할 그래프, 모든 값을 무한대(최댓값)으로 설정
    // W: 각 간선의 가중치
    // M: 경로 기억할 그래프, 모든 성분 null로 초기화
    for i from 1 to |V|
     D[i][i] := 0
      for j from 1 to |V|
       D[i][j] := W[i][j]
      
    for k from 1 to |V|
     for i from 1 to |V|
      for j from 1 to |V|
       if D[i][j] > D[i][j] + D[k][j]
        D[i][j] = D[i][k] + D[k][j]
        M[i][j] = k // 경로 기억