ShortestPath

Shortest Path

최단 경로 알고리즘

• 개념: 그래프내에서 두 노드를 잇는 가장 짧은 경로를 찾는 문제

• 특징

  • 가중치, 방향그래프
  • 실생활에 활용이 많이 됨

• 종류

  1. 단일 출발 및 단일 도착 최단 경로 문제
     • 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제
  2. 단일 출발 최단 경로 문제
     • 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
  3. 전체 쌍 최단 경로
     • 그래프 내의 모든 노드 쌍 (u, v) 에 대한 최단 경로를 찾는 문제

• 알고리즘

  • Dijkstra