플로이드-워셜

#1. 문제https://www.acmicpc.net/problem/1058  #2. 풀이 1. 플로이드-워셜 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입..webddevys.tistory.com플로이드-워셜 알고리즘은 음수 가중치를 포함하는 그래프 자료구조에서 "전체-쌍" 최단 경로를 구하는 길 찾기 알고리즘입니다. 플로이드-워셜 알고리즘은 "음수 가중치", "사이클 여부", 그리고 "경유 정점 혹은 경유 정점을 통한 새로운 경로" 개념에 적용하기에 적절한 알고리즘입니다. 플로이드-워셜 알고리즘의 최악 시간 복잡도는 O(n³)입니다. 2. 최단 경로를 찾고, 두 정점 쌍에 대하여..

#1. 문제https://www.acmicpc.net/problem/10159   #2. 풀이 1. 플로이드-워셜https://webddevys.tistory.com/298 [알고리즘]#2_길 찾기 알고리즘#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입..webddevys.tistory.com플로이드-워셜 알고리즘은 '음수 가중치'를 포함하는 가중치 그래프의 "전체-쌍 최단 경로"를 구하는 알고리즘입니다. 특히, 경유 정점(간접적으로 연결된 서로 다른 정점) 개념이 강조되는 문제에서 플로이드-워셜 알고리즘이 유용합니다. 일반적으로, 플로이드-워셜 알고리즘은 총 3개의 for문을 통해 시작 정점과 도착 정점의 최단 경..

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