[Algorithm] Shortest Path - 최단경로 알고리즘

seohyun-j·2022년 4월 20일
0

알고리즘

목록 보기
4/4
post-thumbnail
  1. 최단 경로 알고리즘이란,
    최단 경로 알고리즘으로 주어진 노드와 간선들 중 가장 짧은 경로를 찾는 알고리즘

  2. 최단 경로 문제의 종류

    • 하나의 정점에서 다른 하나의 정점까지 최단 경로를 구하는 문제
    • 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
    • 각 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
  3. 최단 경로 알고리즘의 종류

    • 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
      • 간선의 가중치가 모두 같은 그래프일 경우 : BFS 이용
      • 간선의 가중치가 각각 다른 그래프일 경우 : Dijkstra, Bellman-Ford(음수의 가중치 간선 존재하는 경우) 이용
    • 각 모든 정점에서 다른 모든 정점까지 최단 경로를 구하는 문제 : Floyd-Warshall 이용
  4. Dijkstra Algorithm

    • A→C로 갈 때 A→B→C로 가는 경로의 가중치 합이 A→C의 가중치 합보다 작다면 B를 거쳐가는 경로를 선택하는 알고리즘
  5. Bellman-Ford Algorithm

    • 음의 가중치가 있을 때에 사용할 수 있는 알고리즘
  6. Floyd-Warshall Algorithm

    • A, B, C의 정점이 있다면 A와 B, C 정점 간의 최단경로, 또 B와 A, C 정점 간의 최단경로 C와 A, B 간의 최단 경로를 구함
    • 즉, 모든 정점에서 다른 모든 정점 간의 최단 경로를 구하는 알고리즘

0개의 댓글