Loading [MathJax]/jax/output/CommonHTML/jax.js

본문 바로가기

플로이드워셜1

알고리즘 - 플로이드-워셜

$Floyd-Warshall$ 들어가며Baekjoon 11403 문제를 접하게 되면서 플로이드 워셜에 대해 알게되었고 그에 대해 간단하게 공부해보려고 한다.플로이드 워셜

$Floyd-Warshall$ 이란?모든 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘. 즉 모든 노드간의 최단 경로를 구하는 알고리즘이다. 시간 복잡도는

$O\left ( V^{3} \right )$ 이며, 다익스트라 알고리즘과 다르게 음의 가중치를 가지는 그래프에서도 사용할 수 있다.거쳐가는 정점을 기준으로 한다 예시)위와 같은 그래프가 존재한다고 생각합시다. 이때 만나지 못하는 정점의 관계는 무한, 자기자신의 정점은 0으로 두고 각각 정점을 기준으로 표로 정리하게 되면. 1234105무한82709무한32무한044무한무한30현재까지 계산된 최소 비용.. 2024. 6. 18.

이전 1 다음

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

블로그 게시글

글 수정 $권한 있는 경우$	`E` `E`
댓글 영역으로 이동	`C` `C`

모든 영역

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.