최단 경로 문제란

용씨·2023년 2월 23일
0

최단 경로 문제

목록 보기
1/1

최단 경로 문제란

  • 가중 그래프에서
  • 간선의 가중치의 합이
  • 최소가 되는 경로를 찾는 문제

문제의 종류

  • 단일 출발 최단 경로
    어떤 하나의 정점에서 출발하여 나머지 모든 정점 까지의 최단 경로를 찾는 문제
  • 단일 도착 최단 경로
    모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제
    그래프 내의 간선들을 뒤집으면 단일 출발 최단거리 문제로 바뀔 수 있다.
  • 단일 쌍 최단 경로
    어떤 정점 v에서 v'로 가능한 최단경로를 구하는 문제
  • 전체 쌍 최단 경로
    모든 정점 쌍들 사이의 최단 경로를 찾는 문제

주요 알고리즘

  • BFS(완전탐색 알고리즘)
    가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구하는 경우 가장 빠르다
  • 다익스트라 알고리즘
    음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제
  • 벨만-포드 알고리즘
    가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제
  • 플로이드-워셜 알고리즘
    전체 쌍 최단 경로 문제
profile
아침형 인간이 목표

0개의 댓글