본문 바로가기

floyd warshall1

[개념 정리] 최단거리 알고리즘 - 플로이드 와샬 가중치가 없는 그래프의 최단거리 문제는 대부분 BFS로 해결할 수 있습니다. 하지만, 간선에 가중치가 존재한다면 BFS가 아닌 최단거리 알고리즘을 통해 접근해야 합니다. 일반적으로 가중치 그래프의 최단거리 문제는 다음과 같은 유형이 존재합니다. 두 정점 간의 최단 거리를 구하는 문제 하나의 정점에서 다른 모든 정점과의 최단거리를 구하는 문제 하나의 정점으로 가는 모든 최단 경로를 구하는 문제 정점 간의 모든 최단 경로를 구하는 문제 이 중 4번을 해결하기 위한 플로이드-와샬 알고리즘에 대해 알아보고자 합니다. 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘은 모든 정점간의 최단경로를 구하는 알고리즘입니다. 앞으로의 설명에서 사용될 그래프는 다음과 같은 가중치를 가지고 있습니다. 초기 가중치 값을 저장하는 .. 2021. 3. 16.

이전 1 다음

티스토리툴바