728x90 반응형 플로이드-워셜 알고리즘1 알고리즘 - 최단 경로 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘) 알고리즘 - 최단 경로 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘) 1. 최단 경로 알고리즘 최단 경로 문제란 가중 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다. 1) 최단 경로 문제의 종류 단일 출발 (single-source) 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점 까지의 최단 경로를 찾는 문제 단일 도착 (single-destination) 최단 경로 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제로 그래프 내의 간선들을 뒤집으면 단일 출발 최단거리 문제로 바뀔 수 있다. 단일 쌍(single-pair) 최단 경로 모든 정점 쌍들 사이의 최단 경로를 찾는 문제 2) 주요 알고리즘 BFS (완전탐색 알고리.. 2021. 2. 3. 이전 1 다음 728x90 반응형