최단 경로 찾기(Shortest Path)

최단 경로 찾기(Shortest Path)

• 가중치 그래프의 어느 한 출발점에서 도착점까지의 최단 경로를 찾는 문제이다.

• 대표적으로 다익스트라 최단 경로 알고리즘이 있다.

---

다익스트라(Dijkstra) 최단 경로 알고리즘

• 프림의 최소 신장 트리(MST) 알고리즘과 비슷하다.

• 주어진 출발점에서부터 최단 거리인 점을 하나씩 확정해가며 각 점까지의 최단 거리를 점차 업데이트하는 방식이다.

• 입력으로 주어지는 그래프에는 각 점과 선분에 대한 정보가 있다고 가정한다.

  Pseudo Code

  ShortestPath(Graph g, Node start)
  {
    int dist[n];  // 최단 거리를 저장한 배열
    dist[start] = 0;
    start를 제외한 나머지는 inf로 초기화시킨다.
    while (최단 거리가 확정되지 않은 점이 있다면)
    {
      start로부터 최단 거리가 확정되지 않은 점들 중 최소 거리인 점 v_min에 대해 dist[v_min]을 확정시킨다.
      start로부터 v_min을 통해 갈 수 있는 각 점 w에 대해 dist[w]를 갱신한다.
    }
    return dist;
  }

  

---

시간 복잡도

• 반복문이 (n - 1)번 반복되고, dist 배열에서 v_min을 찾을 때 O(n) 시간이 걸리므로 시간 복잡도는 O(n²)이다.