길 찾기 알고리즘

#1. 문제 #2. 풀이 1. 다익스트라 알고리즘 [알고리즘]#2_길 찾기 알고리즘 #1. 개념 1. 길 찾기 알고리즘 [정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구 webddevys.tistory.com [정의] : 다익스트라 알고리즘은 길 찾기 알고리즘 중 하나로, 양의 가중치를 갖는 그래프에서 '단일-출발 최단 경로' 알고리즘입니다. [특징] : 다익스트라 알고리즘은 우선순위 큐를 활용해 현재 정점에서 인접한 정점들 중 우선적으로 탐색할 정점을 탐색하는데 활용하며, 각 정점은 시작 정점을 기준으로부터 최단 거리를 갱신합니다. [성능] : 다익스트라 알고리즘의 평균 시간 복잡도는 O((E+..

#0. 문제 #1. 풀이 1. 플로이드-워셜 알고리즘 [알고리즘]#2_길 찾기 알고리즘 #1. 개념 1. 길 찾기 알고리즘 [정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구 webddevys.tistory.com [정의] : 플로이드-워셜 알고리즘은 음수 가중치를 포함하는 가중치 그래프의 '전체-쌍 최단 경로'를 구하는 알고리즘입니다. [특징] : 플로이드-워셜 알고리즘은 DP와 세 개의 중첩 for 문을 통해 각 정점의 최단 경로 값을 구합니다. [성능] : 플로이드-워셜 알고리즘의 평균, 최악 시간 복잡도는 항상 O(n³)입니다. 2. 시작 정점, 시작-도착을 잇는 경로 정점, 도착 정점 첫 ..

#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구성된 그래프에서 최단 경로 혹은 특정 조건을 만족하는(최소 신장 트리, etc) 경로를 찾는 데 사용됩니다. 다양한 종류의 길 찾기 알고리즘이 있으며, 알고리즘의 선택은 그래프의 크기, 가중치의 종류, 실행 시간 제약 등을 고려합니다. 따라서, 알고리즘의 특징과 제약 사항 등을 이해해야 주어진 문제에 가장 적합한 알고리즘을 선택할 수 있습니다.[종류]1. "단일 출발(single-source)" :  주어진 단일 노드 v로부터 다른 모든 노드 사이의 최단 경로를 찾는 문제 2. "단일 쌍(single-pair)" :..