6. Graph (3) - Shortest Path

Graph 를 활용한 Shortest Path (최단 경로) 구하기

그래프의 정점 간에 가장 짧은 거리를 구하는 알고리즘.
가중치 그래프에서 “짧다”는 의미는 가중치의 합이 최소라는 뜻임.

Shortest Path를 구하는 문제 유형에는 SSSP와 APSP가 있

유형	설명	대표알고리즘
Single Source Shortest Path (SSSP)	한 정점에서 모든 정점까지 최단 경로 찾기	BFS, Dijkstra, Bellman–Ford
All Pair Shortest Path (APSP)	모든 정점 쌍 간 최단 경로 찾기	Floyd–Warshall

 

---

1. Single Source Shortest Path

 (1) BFS (가중치가 없는 경우)

가중치가 모두 1이거나 동일한 그래프에서는 BFS로 최단 경로를 구할 수 있음.
이유는 BFS가 가까운 정점부터 차례로 방문하기 때문.

== BFS는 가까운 정점부터 차례로 탐색하므로, 탐색 순서 자체가 최단 거리 순서가 됨.

 

• 가중치가 모두 동일할 때만 사용 가능
• 시간 복잡도: O(V + E)
• BFS 탐색 순서가 곧 최단 거리 순서임

 

처리과정

queue 사용	방문처리방법
시작점에서 거리 0으로 시작 큐(Queue)에 넣고, 방문할 때마다 이전 거리 + 1로 업데이트	시작 정점의 거리를 0으로 두고 큐에 넣음 인접 정점을 방문할 때마다 거리 = 현재 거리 + 1 이미 방문한 정점은 다시 방문하지 않음

 

코드)

void shortestPathBFS(vector<int> adj[], int start, int V) {
    vector<int> dist(V, -1);
    queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    for (int i = 0; i < V; i++)
        printf("dist[%d] = %d\n", i, dist[i]);
}

---

 (2) Dijkstra’s Algorithm (다익스트라 알고리즘)

가중치가 양수인 그래프에서 가장 짧은 거리를 효율적으로 구함.
Greedy(탐욕적) 접근으로, 매번 현재까지 가장 짧은 거리의 정점을 선택함.

== "방문하지 않은 정점 중, 현재까지 가장 짧은 거리인 정점을 선택하고 

그 정점과 인접한 정점들의 거리를 갱신한다."

 

• 가중치가 모두 양수일 때만 사용 가능 (음수 가중치 X)
• 시간 복잡도: O(V²) (배열 기반) / O(E log V) (Heap 기반)
• 빠르고 직관적이지만 음수 간선이 있으면 오작동 함.

다익스트라 알고리즘 :: 바바썬 <- 자세한 내용은 과거 정리 내용 참고

 

처리과정

1. 시작 정점의 거리를 0으로 초기화
2. 나머지 정점은 ∞ (무한대)로 설정
3. 방문하지 않은 정점 중 최단 거리를 가진 정점 선택
4. 그 정점을 기준으로 인접한 정점들의 거리를 갱신
5. if dist[u] + weight(u,v) < dist[v]: dist[v] = dist[u] + weight(u,v)
6. 모든 정점을 방문할 때까지 반복

 

단계별 동작 예시

예시 그래프)

 A -(4)- B 
 |       |
(2)     (1)
 |       |
 C -(5)- D

1. A 시작 → 거리: A(0), B(4), C(2), D(∞)
2. 가장 짧은 C(2) 선택 → D 거리 = 2+5=7
3. B(4) 선택 → D 거리 = min(7, 4+1)=5
4. 모든 정점 방문 완료 → 결과: D까지 5

코드)

void Dijkstra(vector<pair<int,int>> adj[], int start, int V) {
    vector<int> dist(V, INF);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int cost = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (cost > dist[u]) continue;

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 0; i < V; i++)
        printf("dist[%d] = %d\n", i, dist[i]);
}

 

---

 (3) Bellman-Ford Algorithm (벨만-포드 알고리즘)

음수 가중치가 존재하는 그래프에서도 동작하는 알고리즘.
모든 간선을 V-1번 반복 검사하며 더 짧은 경로가 있으면 계속 갱신함.

 == “한 간선을 여러 번 완화(relaxation)하면서 최단 거리를 점진적으로 계산한다.” 

 == “모든 간선을 (V-1)번 반복해서 검사하며 더 짧은 경로가 있다면 계속 갱신한다.”

다익스트라보다 느리지만, 음수 가중치가 있어도 작동함.

 

• 음수 가중치 허용 (단, 음수 사이클 불)
• 시간 복잡도: O(VE)
• 단순하고 확실하지만 느려서 큰 그래프엔 부적합함.

Bellman–Ford 알고리즘 :: 바바썬 <- 자세한 내용은 과거 정리 내용 참고

 

처리과정

 

 1. 시작 정점 거리 = 0, 나머지는 ∞

 2. 모든 간선을 (V-1)번 반복 검사 (모든 간선 (u, v)에 대해)

if (dist[u] + w < dist[v])
    dist[v] = dist[u] + w

 3. 한 번 더 검사해서 값이 바뀌면 → 음수 사이클 존재

 

코드)

 

void BellmanFord(int n, int v) {
    for (int i = 0; i < n; i++)
        dist[i] = length[v][i];

    for (int k = 2; k <= n - 1; k++)
        for (each edge (i, u))
            if (dist[u] > dist[i] + length[i][u])
                dist[u] = dist[i] + length[i][u];
}

---

2. All Pair Shortest Path

 (1) Floyd–Warshall Algorithm (플로이드–워셜 알고리즘)

모든 정점 쌍 (i, j)에 대해 k번째 정점을 중간 경유지로 거칠 때의 최소 비용을 반복적으로 갱신함.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

 ==  “정점 i에서 j로 가는 경로 중, k를 거치는 것이 더 짧은가?”를 반복 검사.

Floyd–Warshall 알고리즘 :: 바바썬  <- 자세한 내용은 과거 정리 내용 참고

 

처리과정

1. dist[i][j]를 초기화
   • i == j → 0
   • 간선이 있으면 그 가중치
   • 없으면 INF
2. 모든 정점 k에 대해 반복:
3. for i in V: for j in V: if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j]

 

단계별 동작 예시

예시 그래프)

A → B (4)
A → C (11)
B → C (2)
C → D (1)

 

dist[A][D] 의 경우

A 0	A에서D로 바로 이동	불가능	∞
A 1	정점 하나 거쳐서 D로 이동	A → C → D	11 + 1 = 12	A 0 과 비교 후 12 선택
A 2	정점 두개 거쳐서 D로 이동	A → B → C → D	4 + 2 + 1 = 7	A 1과 비교 후 7 선책

==> 최종 dist[A][D] = 7

 

코드)

void FloydWarshall(int dist[][N], int V) {
    for (int k = 0; k < V; k++)
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
}

---

정리하자면,

알고리즘	적용	음수 가중치	시간복잡도	특징
BFS	비가중치 그래프	X	O(V+E)	단순하고 빠름
Dijkstra	양수 가중치 그래프	X	O(E log V)	효율적, Heap 사용
Bellman–Ford	음수 가중치 포함	O (음수 사이클 X)	O(VE)	느리지만 확실
Floyd–Warshall	모든 정점 쌍	O (음수 사이클 X)	O(V³)	전체 경로 계산