# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. Floyd 알고리즘 그래프에 존재하는 모든 정점 사이의 최단 경로를 한번에 모두 찾아주는 알고리즘 Dijkstra 알고리즘에서는 '하나의 정점'에서 '다른 모든 정점'으로의 최단 경로를 찾았다면, Floyd 알고리즘에서는 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구할 수 있다. 즉, 그래프의 모든 정점에 대한 최단 경로쌍을 구할 수 있다. 이 알고리즘의 핵심 원리는 '거쳐가는 정점'을 기준으로 최단 경로를 구한다. 알고리즘 HTML 삽입 미리보기할 수 없는 소스 생각의 순서 1. 하나의 정점에서 다른 정점으로 갈 때, 바로 갈 수 있으면 '기존 인접..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. Dijkstra의 최단 경로 알고리즘 하나의 시작 정점으로부터, 모든 다른 정점까지의 최단 경로를 찾는 알고리즘. ≫임의의 두 정점 간의 거리는 항상 최단거리가 된다. 생각의 순서 시작정점 = v 정점 v의 인접정점에 대해서, weight[v][*] 값으로 distance[*] 값 초기화 집합 S에 포함 안된 정점에 대해서, 최소 distance 정점 u를 찾는다. 정점 u를 집합 S에 추가한다. 정점 u의 인접 정점 && 집합 S에 없는 정점에 대해 기존의 거리보다 정점 u를 거쳐가는게 더 빠르면 distance[z] = distance[u] + weigh..

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다. # 해당 게시글에 대한 모든 피드백 환영합니다. 최단경로 Shortest Path 그래프에서 정점 i와 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로 최단경로를 찾는 알고리즘 Dijkstra 알고리즘 하나의 시작정점에서 다른 정점까지의 최단 경로를 구함 Floyd 알고리즘 모든 정점에서 다른 모든 정점까지의 최단 경로를 구함 최단 경로 VS 최소비용트리 최소 비용 트리 최소의 비용으로 모든 점을 다 연결할 때 사용한다. 모든 점을 다 이은 경로가 최단 거리라고 말할 수 있지만, 임의의 두 점 간의 거리가 최단 거리라는 보장은 없다 최단 경로 임의의 두 점 간의 최단 거리 구할 때 사용한..