XI 주요 알고리즘 정리

XI 주요 알고리즘 정리 _ Greedy, DP, Graph

seij 2024. 6. 11. 13:54

탐욕적 알고리즘

• 연속 배낭문제를 푸는 탐욕적 알고리즘

입력 : 배낭 용량 C, 아이템 개수 n, 아이템 무게 w[ ], 아이템 가치 p[ ] (단, 아이템은 무게당 가치로 내림차순 정렬되어 있다고 가정)
출력 : 배낭에 담는 아이템 비율 r[ ]

continuous_knapsack(w[], p[], C)
    i = 0; w_now = 0; max_profit = 0
    while(i < n && w_now < C) // 아이템 개수, 배낭 용량 초과 X
        if(w_now + w[i] <= C) // 현재 아이템을 담아도 용량을 초과하지 않는지 검사
            r = 1 // 초과하지 않을 경우, 해당 아이템을 전부 담는다
            w_now += w[i] // 아이템을 추가한 무게로 update
        else // 아이템을 전부 담을 수 없는 경우 <배낭 용량 초과>
            r = (C – w_now) / w[i] // 남은 용량에 아이템 무게로 나눠 담을 수 있을 수 있는 비율을 구한다
            w_now = C // 담을 수 있는 비율로 꽉 채워 담은 경우에 해당하므로 배냥 용량과 동일해진다
        max_profit += r * p[i] // 담은 비율 * 아이템의 가치 = 현재까지의 총 가치
        i++ // 다음 아이템으로 넘어가기 위해 1 증가
    return max_profit // 최종적으로, 배낭에 담은 아이템들의 총가치를 반환

동적 프로그래밍

• 피보나치 수열 (Fibonacci sequence) - 구현 3가지

• 분할정복 알고리즘 : 재귀관계식을 하향식으로 구현(재귀)

fib1(n)
if (n==0 || n==1) return n
return fib1(n-1) + fib1(n-2)

✓ 사례의 원래 크기와 거의 같은 크기를 가진 2개의 사례로 분할됨 ⇒ 지수시간! O(2^n)
f(n-1), f(n-2) 계산 과정에서 f(n-2)와 f(n-3)을 각각 여러번 호출하기 때문에 매우 비효율적이다.
✓ 재귀호출이 중복적으로 발생

입력 n에 대한 피보나치 수열 n번째 값을 계산하는 함수 fib1(n)
만약, n이 0또는 1이면, n을 그대로 반환해줘야 한다. 피보나치 수열 법칙에 따라 f(0) = 0, f(1) = 1이기 때문.
n이 0이나 1이 아닌 경우, n-1과 n-2를 "재귀적으로 호출"하여 그 결과를 더해서 반환해준다.

→ 이 문제를 풀기 위해, 메모이제이션 or 동적 프로그래밍 사용

• 동적 프로그래밍 알고리즘 : 재귀관계식을 상향식으로 구현(반복)

fib2(n)
f[0...n] 공간 확보 // 크기 n+1의 배열 f를 생성 = 피보나치 수 저장공간 확보
f[0] = 0 // f(0) = 0
f[1] = 1 // f(1) = 1
for (i=2; i<=n; i++) // i를 2부터 n까지 반복
f[i] = f[i-1] + f[i-2] // 현재 피보나치 수 f(i)는 이전 두 값, f(i-1), f(i-2)의 합으로 계산
return f[n]; // 구해진 n번째 피보나치 수 반환

✓ O(n) 시간 소요!
작은 문제부터 시작하여 점진적으로 큰 문제를 해결하므로 "상향식"
반복문을 사용하여 구현이 직관적이고 이해하기 쉽다.

☞ Memoization : 하향식 DP 알고리즘

solve(n, f[])
   if f[n] != -1 // f(n)이 이미 계산된 값이라면 (즉 n-1이 아니라면) 저장해뒀던 그 값을 반환
       return f[n]
   f[n] = solve(n-1, f) + solve(n-2, f) // f(n)이 계산되지 않은 경우, 재귀적으로 호출하여 값을 계산 후 저장
       return f[n]
fib3(n)
   f[0...n]을 –1로 모두 초기화
   f[0] = 0
   f[1] = 1
   return solve(n, f)

메모이제이션과 재귀호출을 통해 O(n) 유지, 재귀호출 스택이 필요하다.
fib3은 추가적인 스택 메모리를 사용한다.

• 최장 부분순서 구하기 (LCS)

✓ 테이블 C 를 역추적(traceback)하여 구하기

traceback(i, j)
if(i==0 or j==0) // 모두 0인 경우, LCS 길이가 0이므로 빈 문자열 반환
return ""

else if(X[i] == Y[j]) // 두 문자가 같으면 LCS에 포함된다.
return traceback(i-1, j-1) + X[i] // (문자열 연결 후 반환)
// traceback을 재귀호출하여 이전 인덱스의 값을 구하고, 현재 문자인 X[i]를 결과에 추가한다.

else // 두 문자가 같지 않은 경우

if(C[i][j-1] >= C[i-1][j]) // A가 B보다 크거나 같으면 (A = C[i][j-1], B = C[i-1][j])
return traceback(i, j-1) // A를 반환
else // B가 A보다 크면
return traceback(i-1, j) // B를 반환

if 모두 영 (기저 사례 처리)
else if 두 문자가 모두 같은 경우
else 두 문자가 다른 경우 (내부 if-else문)

기저 사례 = 재귀호출을 멈추고 즉시 결과를 반환하는 조건을 말한다.
재귀함수의 종료조건을 정의하여 무한 재귀호출을 방지하고, 문제의 가장 작은 부분을 처리한다.

그래프 탐색

• DFS(Depth-First Search : 깊이우선탐색)

• 시작정점을 방문한 후, 인접한 정점 중 방문하지 않은 정점을 다시 시작정점으로 하여 재귀적으로 깊이우선탐색
✓ 미로(maze) 탐색과 유사

**// 연결 그래프 G에 대한 깊이우선탐색 (시작 정점 : s)**

DFS(G, s) // 맨 처음, 그래프와 시작정점을 입력받는다.
     for v in V // 그래프 G의 모든 정점 v에 대해 반복
         visited[v] = NO // 모든 정점을 방문하지 않은 상태로 초기화
     aDFS(G, s) // 재귀도우미 함수 aDFS를 호출하여 시작정점 s부터 DFS 시작

★ //그래프 G의 정점 v로부터 시작하는 깊이우선탐색(재귀 도우미)

aDFS(G, v) // G와 현재 정점 v를 입력받아 DFS를 수행하는 재귀 도우미 함수
     visited[v] = YES // 현재 정점을 방문한 것으로 표시
     for w in L(v) // L(v) : 정점 v의 인접 리스트, 현재 정점의 인접리스트에 있는 모든 정점 w에 대해 반복
         if (visited[w] == NO) // 인접한 정점 w가 아직 방문되지 않았다면,
           edgeTo[w] = v // w로 가는 간선의 이전 정점을 v로 설정 = 이는 'w'로 가는 경로를 추적할 때 사용
           aDFS(G, w) // 재귀적으로 aDFS를 호출하여 정점 w에서 DFS를 계속 수행한다.

**// 그래프 G에 대한 깊이우선탐색(연결 그래프가 아닌 경우)**

DFS(G)
     for v in V // G의 모든 정점 v에 대하여 반복
         visited[v] = NO // 모든 정점 v를 방문하지 않은 상태로 초기화
     for v in V // 그래프 G의 모든 정점 v에 대해 다시 반복
         if (visited[v] == NO) aDFS(G, v) // 정점 v가 방문되지 않았다면,
aDFS를 호출하여 정점 v에서 DFS 수행

DFS(G, s): 시작 정점 s에서 깊이우선탐색을 수행한다. 모든 정점을 방문하지 않은 상태로 초기화한 후, aDFS(G, s)를 호출하여 탐색을 시작한다.
aDFS(G, v): 현재 정점 v에서 시작하는 깊이우선탐색을 재귀적으로 수행한다. 방문한 정점을 표시하고, 인접한 정점들을 탐색한다
DFS(G): 그래프 G가 연결되지 않은 경우에도 모든 정점을 탐색하기 위해 사용한다. 모든 정점을 방문하지 않은 상태로 초기화한 후, 방문되지 않은 정점에서 aDFS를 호출하여 탐색을 시작한다.

• BFS(Breadth-First Search : 너비우선탐색) 가까운 주변 정점부터 우선 방문

• 시작정점으로부터 가까운 정점들을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
   ✓ 방문한 정점과 인접한 정점 중 방문하지 않은 정점을 큐(FIFO)에 삽입

BFS(G, s) // s: 시작 정점
     for v in V // 그래프 G의 모든 정점 v에 대하여
          visited[v] = NO // 모든 정점 v를 방문하지 않은 것으로 초기화한다.
     visited[s] = YES // 시작정점 s를 방문한 것으로 표시
     enqueue(Q, s) // 큐에 s 삽입
     while (Q is not empty) // 큐가 빌 때까지 = 큐가 비어있지 않은 동안 지속
          v = dequeue(Q) // 큐에서 정점 v를 꺼낸다.
          for each w in L(v) // L(v): 정점 v의 인접 리스트에 있는 모든 정점 w에 대해 반복
               if (visited[w] == NO) // w가 방문되지 않았다면
                    visited[w] = YES // 방문했다고 표시한 후,
                    edgeTo[w] = v // w로 가는 간선의 이전 정점을 v로 설정한다.
                    enqueue(Q, w) // w를 큐에 삽입한다.

BFS(G, s): 시작 정점 s에서 너비우선탐색을 수행한다. 모든 정점을 방문하지 않은 상태로 초기화한 후, 시작 정점 s를 큐에 삽입하고 큐가 빌 때까지 탐색을 계속한다.
큐 사용: BFS는 큐(FIFO)를 사용하여 탐색 순서를 관리한다. 현재 정점의 인접한 정점들을 큐에 추가하고, 큐에서 꺼내면서 탐색을 진행하는 구조.
방문 표시: 이미 방문한 정점은 다시 탐색하지 않도록 visited 배열을 사용하여 방문 여부를 관리한다.
경로 추적: edgeTo 배열을 사용하여 각 정점으로 가는 경로를 추적한다.

BFS는 시작 정점에서 가까운 정점부터 차례대로 방문하므로, 최단 경로를 찾는 데 유용하다. 미로 탐색과 유사한 방식으로 동작하며, 그래프의 모든 정점을 효율적으로 탐색할 수 있다.

• 진입 차수(in-degree)를 이용한 위상정렬 알고리즘

TS(G)   //n : 정점의 개수 - 그래프 G를 입력으로 받아 위상정렬 수행
   // 진입차수 계산
   크기가 n인 배열 indegree을 생성하고 0으로 초기화
   for v in V
        for w in L(v) // 정점 v의 인접리스트에 있는 모든 정점 w에 대하여 반복
           indegree[w]++ // w의 진입차수를 1 증가시킨다 = v에서 w로 가는 간선이 존재함을 의미

   // 위상정렬
   결과를 저장할 result 리스트 생성
정점을 저장할 빈 Q를 생성
   for v in V // 그래프 G의 모든 정점 v에 대해 반복
        if (indegree[v] == 0) enqueue(Q, v) // v의 진입차수가 0일 때, v를 큐에 삽입
   while (Q is not empty) // 큐가 비어 있지 않은 동안 반복
        v = dequeue(Q) // v를 큐에서 삭제 (작업에서는 이제 삭제)
        result의 맨 뒤에 v를 추가 // result 리스트에는 맨 뒤에 v를 추가 (결과에 저장) (FIFO)
        for w in L(v) // 정점 v의 인접리스트 L(v)에 있는 모든 정점 w에 대해 반복
             indegree[w]-- // 인접 정점 w의 진입 차수를 감소 시킴
             if (indegree[w] == 0) enqueue(Q, w) // 진입차수가 0이 된 인접 정점 w는 큐에 삽입
        return result // 결과를 반환

진입차수 계산: 각 정점의 진입 차수를 계산하여 indegree 배열에 저장
초기 큐 설정: 진입 차수가 0인 모든 정점을 큐에 삽입
위상정렬 수행: 큐가 비어있지 않을 때까지 정점을 꺼내고, 결과 리스트에 추가. 꺼낸 정점의 인접한 정점들의 진입 차수를 감소시키고, 진입 차수가 0이 되면 해당 정점을 큐에 삽입
결과 반환: 위상정렬된 정점들의 순서를 반환

이 알고리즘은 위상정렬을 통해 방향 그래프의 모든 정점을 순서대로 나열하며, 주로 작업 스케줄링, 순서 결정 등의 문제를 해결하는 데 사용된다.

그래프 알고리즘

• union-find 연산 알고리즘

find(x) // 경로압축
     if(parent[x] ! = x)
          return find(parent[x])
     return x

union(x, y) // Union 두 집합 x, y를 합치는 연산 수행
    p = find(x) // x의 루트를 찾아 p에 저장
    q = find(y) // y의 루트를 찾아 q에 저장
    if(p != q) // 둘의 루트가 다르면 = 둘은 다른 집합에 속함을 의미한다
       if(rank[p] < rank[q]) // 랭크가 낮은 트리를 높은 트리의 자식으로 만든다
           parent[p] = q // 깊이가 작은 트리를 자식노드로! = p의 부모는 q가 된다.
       else if(rank[p] > rank[q])
           parent[q] = p
       else // p와 q의 랭크가 같으면
           parent[q] = p //랭크가 같으면 앞쪽 트리의 자식으로 뒤쪽 트리를 연결
           rank[p]++; // p의 랭크 1 증가

union
각각의 루트를 찾아 저장
둘의 루트가 다른 경우
랭크가 p가 더 작으면
q가 부모가 되고
랭크가 q가 더 작으면
p가 부모가 된다.
랭크가 같으면
앞쪽 트리인 p가 부모가 되고
rank[p]++; p의 랭크 증가

• 경로 압축(path compression)

find(x) // 정점 x의 루트(parent)를 찾는 연산
if(parent[x] ! = x) // 만약 x가 자기자신을 부모로 갖지 않는다면 = 자기자신이 루트가 아니라면
parent[x] = find(parent[x]) // x의 부모 정점 parent[x]에 대해 find를 재귀적으로 호출
// 이를 통해 경로를 압축하고, 최종적으로 x의 루트를 반환
return parent[x] // 조건문 밖 ; x가 자기자신을 부모로 갖는다면, x를 반환

union-find 알고리즘은 서로소 집합을 관리하는 자료구조로, 두 주요 연산인 find와 union을 제공한다. 여기서 find 연산은 경로 압축(Path Compression)을 사용하고, union 연산은 랭크를 기반으로 트리를 병합한다.
경로 압축은 find 연산의 효율성을 높이기 위해, 각 정점이 루트를 직접 가리키도록 트리를 평탄화한다.

• 최소신장트리 MST (Minimum Spanning Tree)

• 크루스칼 알고리즘 : Union-Find 데이터구조를 사용하는 알고리즘

• 먼저 모든 간선을 가중치를 기준으로 오름차순 정렬
• 차례로 간선을 선택하여, 사이클이 생기지 않으면 추가
• 사이클 판정
✓ 간선의 양 정점이 같은 서로소 집합에 속하면 사이클!!
✓ 즉 간선이 <i, j> 인 경우 find(i) == find(j)이면 사이클

입력 : 가중치가 있는 무방향 그래프 G=(V, E), |V| = n
출력 : 최소신장트리에 포함되는 간선의 집합 MST

Kruskal(G)
    모든 간선들을 가중치 순서로 오름차순 정렬
    MST = ∅; // MST에 포함될 간선들의 집합을 빈 집합으로 초기화
    union-find 초기화   // parent를 모두 자기자신으로 설정한단 의미 = parent[i] = i, Rank는 모두 0
    while(MST에 포함된 간선의 수 < n - 1) // 간선의 수가 n-1개가 될 때까지 반복, n = 정점의 개수
        e = 남아 있는 간선 중 가중치가 최소인 간선    // e=<i, j>    맨 앞에 있는 것을 선택하는 것
        p = find(i) // 정점 i의 루트 찾기 = i가 속한 집합의 대표자 찾기, 대표자 = p 반환
        q = find(j) // 정점 j의 루트 찾기 = j가 속한 집합의 대표자 찾기, 대표자 = q 반환
        if(p != q) // p == q 이면 Cycle 이므로, 같지 않을 경우에만 union 연산 수행
            union(p, q) // i와 j가 속한 두 집합을 병합. 즉, 두 정점을 같은 집합으로 만듦
            e를 MST에 추가 // 간선 e를 최소신장트리에 추가

• 시간복잡도 : O(|E|log|E|)

간선 정렬: 모든 간선을 가중치 순서로 오름차순 정렬
MST 초기화: MST를 빈 집합으로 초기화하고, Union-Find 자료구조를 초기화
간선 선택: 가중치가 가장 작은 간선을 선택하고, 그 간선이 사이클을 형성하지 않으면 MST에 추가
사이클 판정: find 연산을 통해 두 정점이 같은 집합에 속하는지 확인하고, 다르면 union 연산을 통해 두 집합을 병합
반복 종료: MST에 포함된 간선의 수가 n - 1개가 될 때까지 반복

크루스칼 알고리즘은 간선을 가중치 순서대로 정렬하고, 순서대로 간선을 선택하며 사이클을 피하는 방식으로 최소 신장 트리를 구축한다. 이 알고리즘의 시간복잡도는 O(|E| log |E|)로, 간선의 개수가 많은 경우에도 효율적으로 동작한다.

1)
모든 간선 가중치 순서로 오름차순 정렬
MST = 공집합
Union-Find 초기화 (모든 정점의 부모를 자기자신으로 설정, 랭크는 모두 0으로 설정)

2)
while(MST에 포함된 간선의 수 < n-1)
e = 남은 간선 중 가중치 최소인 간선 (선택)

p = find(i)
q = find(j)

3)
if (p != q)
union(p, q)
e를 MST에 추가

• 프림 알고리즘(Prim's algorithm) 정점을 모아가는 방식

크루스칼 = 가중치가 가장 작은 간선을 선택
프림 = 정점을 선택해서 모은다는 개념 (포함된 정점과 포함되지 않은 정점으로 분리해서 생각)
• 우선순위 큐(최소힙)를 사용하는 알고리즘
✓ 간선의 가중치를 우선순위로 하여, 우선순위 큐에서 삭제 연산을 하여 추가할 간선 후보를 선정
✓ 보통 우선순위 큐의 우선순위는 첫 번째 원소이므로 PQ에 간선을 삽입할 때는 (w, i, j) 형식으로 추가,
       정점 i와 정점 j를 잇는 간선의 가중치가 w

입력 : 가중치가 있는 무방향 그래프 G=(V, E), |V| = n
출력 : 최소신장트리에 포함되는 간선의 집합 MST

Prim(G, s) // 그래프 G와 시작 정점 s를 입력받는다
    MST = ∅ // MST에 포함될 간선 집합을 빈 집합으로 초기화
    visited[0...(n-1)] = 0 // 크기가 n인 배열 visited 생성 후 모든 요소를 0으로 초기화 (방문 여부를 ep)
    visited[s] = 1    // 시작정점만 1로 놓고 시작 = 시작 정점 s를 방문한 것으로 표시
    정점 s에 인접한 모든 간선을 PQ에 삽입 // PQ는 간선을 가중치 순서로 정렬
    while(MST에 포함된 간선의 수 < n - 1) // MST에 포함된 간선의 수가 n-1개가 될 때까지 반복
        e = PQ에서 삭제한 간선 // e=(w, i, j) 정점 i와 j를 잇는 간선의 가중치가 w
// PQ에서 가중치가 가장 작은 간선 e를 삭제
        if(visited[j] == 0) // 만약 정점 j가 아직 방문되지 않았다면
            visited[j] = 1 // 정점 j를 방문 처리 하고
            MST에 (i, j, w) 추가 // 정점 j와 인접한 정점 중 방문하지 않은 정점과의 간선들을 모두 PQ에 삽입
            for (k, w) in L(j) // 정점 j의 인접리스트에 있는 정점 k와 그 가중치 w에 대해 반복
                if visited[k] == 0 // 정점 k가 아직 방문되지 않았다면 다음을 수행
                    PQ에 (w, j, k) 삽입 // 정점 j와 k를 잇고 가중치가 w인 간선 추가

• 시간복잡도
✓ 최소 간선을 구하기 위해 정렬을 사용하는 경우 :O(|V| * |E|log|E|), 비효율적
✓ 우선순위 큐(최소힙)를 사용하는 경우 : |E|log|E|

초기화: MST를 빈 집합으로 초기화하고, 모든 정점을 방문하지 않은 상태로 설정, 시작 정점 s만 방문한 것으로 표시하고, s에 인접한 모든 간선을 PQ에 삽입
반복: MST에 포함된 간선의 수가 n - 1이 될 때까지 다음을 반복
1. PQ에서 가중치가 가장 작은 간선을 선택하고 삭제
2. 간선의 한쪽 정점이 아직 방문되지 않았다면, 그 정점을 방문한 것으로 표시하고 간선을 MST에 추가
3. 새로 방문한 정점과 인접한 모든 방문되지 않은 정점과의 간선을 PQ에 삽입
사이클 방지: 이미 방문된 정점은 다시 큐에 삽입하지 않음으로써 사이클을 방지

Prim의 알고리즘은 이와 같이 시작 정점에서 출발하여 최소 가중치 간선을 반복적으로 선택하며 MST를 구축합니다. 이 과정에서 우선순위 큐를 사용하여 효율적으로 간선을 관리한다.

• 다익스트라 알고리즘

✓ 양의 가중치를 가지는 방향 그래프를 대상으로 함
✓ 단일 출발점 최단 경로 문제를 푸는 탐욕적 알고리즘
✓ 단계마다 현재까지 최단 경로를 구한 정점의 집합 Y에 속한 정점만 거쳐 갈 수 있는 가장 짧은 거리의 정점을 추가

입력 : 그래프 G = (V, E), |V| = n, 출발점 s
출력 : distTo[ ], edgeTo[ ]

Dijkstra(G, s)
    distTo[0...(n-1)] = ∞ // distTo 배열의 크기를 정점의 개수 n만큼 생성하고, 모든 요소를 무한대(∞)로 초기화
// distTo[v]는 출발점 s에서 정점 v까지의 현재까지 알려진 최단 거리를 저장한다.
    distTo[s] = 0 // 출발점 s에서 자기 자신까지의 거리를 0으로 설정
    edgeTo[s] = s // s에서 s로 가는 경로는 s 자체로 초기화
    PQ에 (0, s)을 삽입 // 우선순위 큐(PQ)에 (0, s)를 삽입, 여기서 0은 거리, s는 정점
    while (PQ is not empty) // PQ가 비어 있지 않은 동안 반복
       i = PQ에서 삭제한 정점 // PQ에서 가중치가 가장 작은 i를 삭제
// w는 현재 정점 i까지의 최단 거리
       for (j, w) in L(i) // 정점 i의 인접 리스트 L(i)에 있는 모든 정점 j와 그 가중치 w에 대해 반복
           if distTo[i]+w < distTo[j] //새로운 정점 추가로 더 짧아진 경로

현재 정점 i를 거쳐서 정점 j로 가는 경로의 거리가 distTo[j]보다 짧다면, 즉 distTo[i] + w가 distTo[j]보다 작다면 다음을 수행

                distTo[j] = distTo[i] + w // 출발점 s에서 정점 j까지의 최단 거리를 갱신
                edgeTo[j] = i // 출발점 s에서 정점 j로 가는 최단 경로에서 직전 정점을 i로 설정
               PQ에 (distTo[j], j)를 삽입 // 갱신된 최단 거리를 우선순위 큐에 삽입,
여기서 distTo[j]는 현재까지의 최단 거리, j는 정점

• 2개의 보조 배열 distTo[]와 edgeTo[] 사용 : 결과 저장
✓ distTo[v] : s로부터 v로 가는 최단 경로의 길이
✓ edgeTo[v] : s로부터 v로 가는 최단 경로에서 직전 정점

초기화: 모든 정점까지의 거리를 무한대로 초기화하고, 출발점 s의 거리를 0으로 설정, 시작 정점을 PQ에 삽입
반복: PQ가 빌 때까지 다음을 반복
1. PQ에서 가중치가 가장 작은 정점 i를 꺼낸다.
2. 정점 i에 인접한 모든 정점 j에 대해, i를 통해 j로 가는 경로가 현재 알려진 경로보다 짧으면 distTo와 edgeTo를 갱신
3. 갱신된 최단 거리를 PQ에 삽입
결과: distTo 배열은 출발점 s에서 각 정점까지의 최단 거리를 저장하고, edgeTo 배열은 최단 경로에서의 직전 정점을 저장한다.

다익스트라 알고리즘은 이와 같이 탐욕적인 접근 방식을 통해, 단계마다 최단 경로를 확정하며 효율적으로 최단 경로를 찾는다.

• 플로이드-워셜(Floyd-Warshall) 알고리즘

• 모든 정점에서 다른 모든 정점으로의 최단 경로(길이)를 구하는 알고리즘
• 동적 프로그래밍(DP) 알고리즘
• 인접 행렬 W 사용 : 정점의 개수 n
• 동적 프로그래밍을 위한 재귀관계식 : 중간 정점의 집합을 하나씩 늘려감

입력 : 그래프 G 의 인접 행렬 W, |V| = n
출력 : 모든 정점 간의 최단 경로 길이 행렬 D

floyd(W, n) D = W

     for k = 0, 1, ..., n-1 // 중간 정점 k를 0부터 n-1까지 반복, k는 경유할 정점을 의미
         for i = 0, 1, ..., n-1 // 출발 정점 i를 0부터 n-1까지 반복
             for j = 0, 1, ..., n-1 // 도착 정점 j를 0부터 n-1까지 반복
                 D[i][j] = min(D[i][j], D[i][k] + D[k][j])
     return D // 모든 정점 간의 최단 경로 길이 행렬 D를 반환

floyd 함수는 그래프 G의 인접 행렬 W와 정점의 개수 n을 입력으로 받아, 모든 정점 간의 최단 경로 길이 행렬 D를 반환한다.

D[i][j] = min(D[i][j], D[i][k] + D[k][j])
i에서 j로 가는 현재의 최단 거리 D[i][j]와 i에서 k를 거쳐 j로 가는 경로의 거리 D[i][k] + D[k][j] 중에서 더 작은 값을 D[i][j]에 저장한다. 이 단계는 k를 중간 경유지로 고려하여 최단 경로를 업데이트한다.

초기화: 최단 경로 길이 행렬 D를 인접 행렬 W로 초기화
중간 정점 고려: k를 중간 정점으로 고려하여, i에서 j로 가는 최단 경로를 업데이트
- k를 경유지로 추가함으로써, i에서 k를 거쳐 j로 가는 경로가 더 짧은지 확인하고, 더 짧은 경로를 D[i][j]에 저장
반복 구조: 세 개의 중첩된 for 루프를 통해 모든 정점 쌍 (i, j)에 대해, 모든 중간 정점 k를 고려한다.
결과 반환: 최종적으로, 모든 정점 간의 최단 경로 길이를 담고 있는 행렬 D를 반환

플로이드-워셜 알고리즘은 동적 프로그래밍 기법을 사용하여 모든 정점 쌍에 대한 최단 경로를 효율적으로 계산한다. 이 알고리즘은 시간 복잡도가 O(n^3)으로, 정점의 개수가 많은 경우에도 비교적 효율적으로 작동한다.