최단 경로 문제
덤프버전 :
1. 개요[편집]
그래프 상에서 정점과 정점 간의 최단 거리를 구하는 문제.
2. 관련 알고리즘[편집]
- 너비 우선 탐색: 비가중치 그래프 상에서 단일 소스로 부터 다른 정점까지의 최단 경로를 구하는 알고리즘
- 다익스트라 알고리즘: 음의 가중치가 존재하지 않는 가중치 그래프 상에서 단일 소스로 부터 다른 정점까지의 최단 경로를 구하는 알고리즘
- 플로이드-워셜 알고리즘: 음의 가중치가 존재하지 않는 가중치 그래프 상에서 모든 정점간의 최단 경로를 구하는 알고리즘
- 벨만-포드 알고리즘: 음의 사이클이 존재하지 않는 가중치 방향성 그래프 상에서 모든 정점간의 최단 경로를 구하는 알고리즘
이 문서의 내용 중 전체 또는 일부는 2023-12-19 01:07:03에 나무위키 최단 경로 문제 문서에서 가져왔습니다.