그래프 - 최단경로

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다. 

최단경로 Shortest Path

그래프에서 정점 i와 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로

 

최단경로를 찾는 알고리즘

• Dijkstra 알고리즘
  • 하나의 시작정점에서 다른 정점까지의 최단 경로를 구함
• Floyd 알고리즘
  • 모든 정점에서 다른 모든 정점까지의 최단 경로를 구함

 

최단 경로 VS 최소비용트리

• 최소 비용 트리
  • 최소의 비용으로 모든 점을 다 연결할 때 사용한다.
  • 모든 점을 다 이은 경로가 최단 거리라고 말할 수 있지만, 임의의 두 점 간의 거리가 최단 거리라는 보장은 없다
• 최단 경로
  • 임의의 두 점 간의 최단 거리 구할 때 사용한다. 

cf) 이 부분은 아직도 확실하게 와닿지가 않는다...