이곳은 개발을 위한 베타 사이트 입니다.
기여내역은 언제든 초기화될 수 있으며, 예기치 못한 오류가 발생할 수 있습니다.
기여내역은 언제든 초기화될 수 있으며, 예기치 못한 오류가 발생할 수 있습니다.
최단 경로 문제
덤프버전 :
1. 개요[편집]
그래프 상에서 정점과 정점 간의 최단 거리를 구하는 문제.
2. 관련 알고리즘[편집]
- 너비 우선 탐색: 비가중치 그래프 상에서 단일 소스로 부터 다른 정점까지의 최단 경로를 구하는 알고리즘
- 다익스트라 알고리즘: 음의 가중치가 존재하지 않는 가중치 그래프 상에서 단일 소스로 부터 다른 정점까지의 최단 경로를 구하는 알고리즘
- 플로이드-워셜 알고리즘: 음의 가중치가 존재하지 않는 가중치 그래프 상에서 모든 정점간의 최단 경로를 구하는 알고리즘
- 벨만-포드 알고리즘: 음의 사이클이 존재하지 않는 가중치 방향성 그래프 상에서 모든 정점간의 최단 경로를 구하는 알고리즘