<aside> 💡 최단 경로(shortest path) → 네트워크에서 정점 i와 정점 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로

</aside>

두 가지의 알고리즘이 존재한다!

1. Dijkstra 알고리즘 : 하나의 시작 정점에서 다른 정점까지의 최단 경로를 구한다.
2. Floyd 알고리즘 : 모든 정점에서 다른 모든 정점까지의 최단 경로를 구한다.

Dijkstra의 최단 경로 알고리즘

→ 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다.

• 최단 경로는 경로의 길이 순으로 구해진다.
  • 집합 S : 시작 정점 v 로부터의 최단경로가 이미 발견된 정점들의 집합
  • 1차원 배열 distance : 시작 정점에서 집합 S 에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 배열

Step 1

Step 2