[자료구조] 21. 최단 경로 문제

1. 최단 경로 문제

1) 최단 경로(Shortest Path)

• 최단 경로란, 그래프 상의 두 정점 사이를 연결하는 경로 중에서 가장 짧은 경로를 의미한다.
• 여기서 "짧다"는 것은 물리적 거리 외에도 시간, 비용 등 다양한 기준으로 해석될 수 있다.
• 실생활에서 다양하게 사용되는 중요한 알고리즘 중 하나이며, 그래프의 정점은 장소나 건물, 간선은 길로 표현된다.

 

응용 분야

• 지도 서비스(구글 맵, 네이버 지도 등)
• 자동차 내비게이션
• 대중교통 경로 탐색 앱
• 건물 내 효율적 동선 설계
• 군사 공학, 통신망 설계, VLSI 설계 등

 

2) 최단 경로 알고리즘 종류

• 다익스트라(Dijkstra) 알고리즘: 시작 정점에서 다른 모든 정점까지의 최단 경로를 구함.

• 플로이드(Floyd) 알고리즘: 모든 정점에서 다른 모든 정점까지의 최단 경로를 구함.

 

 

2. 다익스트라 알고리즘

1) 개요

• 다익스트라 알고리즘은 하나의 시작 정점에서 출발하여 다른 모든 정점까지의 최단 경로를 계산하는 방식이다.
• 음수 가중치는 사용할 수 없으며, 가장 가까운 정점부터 확정하면서 최단 경로를 확장해 나간다.

 

핵심 개념

• S 집합: 시작 정점으로부터 최단 경로가 확정된 정점들의 집합
• distance 배열: 정점 v로부터 각 정점까지의 최단 경로 길이를 저장

 

2) 알고리즘 절차

shortest_path(G, v)
  S ← {v}
  for 각 정점 w ∈ G do
    distance[w] ← weight[v][w]

  while 모든 정점이 S에 포함되지 않으면
    u ← S에 속하지 않는 정점 중에서 distance가 최소인 정점
    S ← S ∪ {u}

    for u에 인접한 각 정점 z (단, z ∉ S) do
      if distance[u] + weight[u][z] < distance[z] then
        distance[z] ← distance[u] + weight[u][z]

 

 

3. 플로이드 알고리즘

1) 개요

• 플로이드 알고리즘은 모든 정점에서 다른 모든 정점까지의 최단 경로를 계산한다.
• 2차원 배열을 이용해 모든 경로를 초기화하고, 세 정점의 관계를 반복적으로 비교하며 경로를 최적화한다.

 

2) 알고리즘 절차

floyd(G)
  for k ← 0 to n - 1
    for i ← 0 to n - 1
      for j ← 0 to n - 1
        A[i][j] = min(A[i][j], A[i][k] + A[k][j])

 

• 핵심 원리: 중간 정점 k를 거쳐 가는 경로가 더 짧다면 기존 경로를 갱신한다.

 

 

4. 위상 정렬 (Topological Sort)

1) 개요

• 위상 정렬은 방향성 그래프에서 정점들의 순서를 정하는 정렬 방식이다.
• 단, 사이클이 없는 방향 그래프(DAG)에서만 적용 가능하다.

 

2) 특징 및 조건

• 간선이 정점 x에서 y로 연결되어 있으면, 정렬 결과에서 x는 y보다 반드시 앞에 위치해야 한다.
• 그래프의 정점들을 선행 순서를 지키면서 나열한다.
• 하나의 방향 그래프에 대해 여러 개의 위상 정렬 순서가 존재할 수 있다.

 

---

이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.