<aside> 💡 최단 경로(shortest path)문제는 정점 u와 정점 v를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 알고리즘

</aside>

최단 경로를 구해야하는 경우 사용할 수 있는 대표적인 알고리즘

1. 다익스트라 알고리즘

2. 벨만-포드 알고리즘

3. 플로이드 알고리즘

동작원리

탐색 방법

<aside> 💡 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘

</aside>

Dijkstra 알고리즘에서는

• 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단 거리를 기록하는 배열 //distance
• 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최소 비용의 합을 기록하는 배열 //weight
  • 정점 v → 정점 w로의 직접 간선이 없는 경우 weight 배열의 값은 무한대로 저장

1. 시작 정점을 v라고 했을 때, distance[v] = 0 이고 다른 정점에 대한 distance 값은 시작 정점과 해당 정점 간의 가중치가 된다.
   1. 가중치는 인접 행렬에 저장되므로 가중치 인접 행렬을 weight라 했을 때 distacne[w] = weight[v][w] 과 같이 사용
   2. 정점 v에서 정점 w로의 직접 간선이 없을 경우에는 무한대의 값을 저장
2. 시작 단계에서는 아직 최단 경로를 발견하지 못했으므로 S = { v } 와 같을 것이다.
   1. 즉 처음에는 시작 정점 v를 제외하고 최단거리가 알려진 정점이 없다.
   2. 알고리즘이 진행되면서 최단 거리가 발견되는 정점들이 S에 하나씩 추가
3. 매 단계에서 집합 S 안에 있지 않은 정점 중에서 가장 distance 값이 작은 정점을 S에 추가한다.
   1. 새로운 정점 u가 S에 추가되면, S에 있지 않은 다른 정점들의 distance 값을 수정한다.
   2. 시작 기준점이 u로 바뀌었기 때문에, 새로 추가된 정점 u를 거쳐서 정점까지 가는 거리와 기존의 거리를 비교한다.
4. 그 후 더 작은 거리값을 기준으로 distance값을 수정한다.
   1. distance[w] = min(distance[w], distance[u] + weight[u][w])  //두 값중 더 작은 값을 리턴한다.(최소 비용)

[waca's field]

1. 시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.
2. 방문한 정점들과 연결되어 있는 정점들 중, 비용이 가장 적게 드는 정점을 선택하고, 해당 정점을 방문한 정점으로 선택해준다.
3. 2번 과정에 의해서 갱신될 수 있는 정점들의 거리를 갱신시켜준다.
4. 2 ~ 3번 과정을 반복한다.