• 간선 가중치가 있는 방향 그래프

  • 두 정점 사이의 최단 경로

    • 두 정점 사이 가중치 값이 최소인 경로
    • 간선 가중치 합이 음인 싸이클이 있으면 문제가 정의되지 않음

  • 단일 시작점 최단 경로

  • 다익스트라 ( 음의 가중치 허용 X )

  • 벨만 포드 ( 음의 가중치 허용 )

  • 모든 쌍 최단경로

  • 플로이드-워샬 ( 모든 정점 쌍 사이의 최단 경로 )