Skip to main content
HashnodeMy dev journey

Command Palette

Search for a command to run...

From Dijkstra to A: A Deep Dive into Graph Algorithms 2

Updated
•43 min read
From Dijkstra to A: A Deep Dive into Graph Algorithms 2
H
Heesu Noh
Part of seriesComputer Algorithms

Contents

1️⃣위상 정렬 (Topological Sorting)
2️⃣최단 경로 알고리즘 (Shortest Path Algorithm)
3️⃣다익스트라 알고리즘 (Dijkstra's Algorithm)
4️⃣벨만-포드 알고리즘 (Bellman-Ford Algorithm)
5️⃣모든 쌍 최단 경로 (All-Pairs Shortest Path)
6️⃣강연결 요소 구하기 (Finding Strongly Connected Components, SCC)
7️⃣ A* 알고리즘 (A* Search Algorithm)

Summary: Graph Algorithms Review (그래프 알고리즘 리뷰)

1. Topological Sorting (위상 정렬)

  • Description (설명): Orders vertices in a Directed Acyclic Graph (DAG) such that no vertex points back to its predecessors (DAG에서 모든 간선의 방향과 위배되지 않도록 정점을 정렬).

  • Key Points (핵심 포인트):

    • Achievable using Depth-First Search (DFS) (DFS를 이용하여 구현 가능).

    • 간선이 순방향으로만 흐르도록 보장하며 순환 구조가 없음.

2. Shortest Path Algorithms (최단 경로 알고리즘)

  • Description (설명): Calculates the path with the minimum cost between two vertices (두 정점 사이의 경로들 중 간선의 가중치 합이 최소가 되는 경로를 구함).

  • Key Points (핵심 포인트):

    • DAG에서는 가중치가 양수여야 함.

    • 음의 가중치 합계가 포함된 사이클이 있으면 계산 불가.

3. Cycle-Free Shortest Path (사이클이 없는 최단 경로)

  • Description (설명): Uses topological sorting to ensure paths are acyclic (DAG에서의 최단 경로는 위상 정렬을 이용하여 수행 가능).

  • Key Points (핵심 포인트) 각 정점들마다 거리값을 업데이트하여 최소값을 구함.

4. Dijkstra's Algorithm (다익스트라 알고리즘)

  • Description (설명): Computes shortest paths from a single source vertex, only for non-negative weights (단일 시작점의 최단 경로 알고리즘으로 음의 가중치를 허용하지 않음).

  • Key Points (핵심 포인트): 출발 정점과 현재 정점 간의 최단 거리를 저장.

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

  • Description (설명): Handles graphs with negative weights, unlike Dijkstra’s (다익스트라 알고리즘과 달리 음의 가중치를 허용하는 최단 경로 알고리즘).

  • Key Points (핵심 포인트): 이중 for문으로 다익스트라 알고리즘에 비해 시간 복잡도가 높음.

6. All-Pairs Shortest Path (모든 쌍 최단 경로)

  • Description (설명): Finds shortest paths between all pairs of vertices (그래프의 모든 정점들 간의 상호 최단거리를 구하는 문제).

  • Key Points (핵심 포인트): 네비게이션 또는 네트워크 경로 탐색에서 유용.

7. Floyd-Warshall Algorithm (플로이드-워샬 알고리즘)

  • Description (설명): Uses dynamic programming to solve all-pairs shortest path problems (정점 집합을 하나씩 증가시키면서 동적 프로그래밍으로 최단 거리 구함).

  • Key Points (핵심 포인트): 음수 가중치도 허용되며, 밀집 그래프에서 효율적임.

8. Strongly Connected Components (강연결 요소 구하기 알고리즘)

  • Description (설명): Identifies maximal subgraphs where every pair of vertices is mutually reachable (강하게 연결된 부분 그래프를 DFS를 응용하여 구하는 알고리즘).

  • Key Points (핵심 포인트): 그래프와 역방향 그래프를 순차적으로 탐색하여 요소를 분리.

9. A Algorithm*

  • Description (설명): Combines path cost and heuristic estimates to find the shortest path efficiently (출발점에서 도착점까지 가는 최단 거리를 추정값을 활용하는 알고리즘).

  • Key Points (핵심 포인트):

    • 평가 함수: f(n) = g(n) + h(n)

      • g(n): 출발점에서 현재 노드까지의 실제 비용.

      • h(n): 목표 노드까지의 추정 비용.

    • 탐색과 최적화를 균형 있게 수행.

1️⃣위상 정렬

그래프 고급 알고리즘을 배우기에 앞서 우선 위상 정렬 (Topological Sorting)의 개념과 이를 설명하기 위한 DAG (Directed Acyclic Graph)에 대해 알아본다. DAG는 사이클이 없는 유향 그래프 (Directed Acyclic Graph)로, 방향이 있는 그래프이며 특정 정점 간 순서 관계를 나타낸다. “위상 정렬”은 이 DAG의 모든 정점을 일렬로 배치하는 알고리즘으로, 모든 간선의 방향이 위배되지 않도록 정렬하는 것을 목표로 한다.

topological: the study of shapes that can be stretched and moved while points on the shape continue to stay close to each other.

✅ DAG (Directed Acyclic Graph)란?

  • DAG는 방향이 있는 그래프 (Directed Graph)로, 사이클이 없는 (Acyclic) 구조를 가진다.

  • 즉, 정점에서 출발하여 간선을 따라가다 보면 다시 원래 정점으로 돌아올 수 없는 그래프이다.

  • DAG의 정점들은 특정 간선의 방향에 따라 정렬된다.

    • 예) 정점 A → 정점 B라면, A는 반드시 B보다 먼저 나오게 된.

✅ 위상 정렬 (Topological Sorting)이란?

  • 위상 정렬은 DAG에서 모든 정점을 순서대로 정렬하는 알고리즘 (Algorithm to order all nodes in sequence in a DAG)이다. 즉 DAG의 간선 방향에 따라 정렬된 순서를 만들게 된다.

  • 정렬된 순서에서 간선의 방향이 모두 올바르게 유지되도록 보장한다.

위상정렬 #1: 필요한 개념 (Key Concepts for Topological Sorting)

위상 정렬 (Topological Sorting)을 이해하기 위해 필수적인 두 가지 개념을 설명한다. 위상정렬을 실행 하려면 간선들이 들어오고 나가는지 파악해야 하는데 이는 u를 기준으로 한다.

✅ 진입 간선 (Incoming Edges)

  • 진입 간선은 특정 정점으로 들어오는 방향의 간선 (Edges pointing toward a node)이다.

    • 예: 정점 u에 도달하는 화살표가 “진입 간선(Incoming Edges)”이다.

✅ 진출 간선 (Outgoing Edges)

  • 진출 간선은 특정 정점에서 나가는 방향의 간선 (Edges pointing away from a node)이다.

    • 예: 정점 u에서 다른 정점으로 나가는 화살표가 진출 간선(Outgoing Edges)이다.

✅진입 차수 (In-degree)

  • 진입 차수는 정점으로 들어오는 간선의 개수 (The number of incoming edges)이다.

    • 예: 정점 u에 들어오는 화살표가 3개라면, u의 진입 차수는 3이 된다.

  • 진입 차수가 0이면:

    • 이 정점은 다른 정점에 의존하지 않고 가장 먼저 처리될 수 있다.

  • 진입 차수가 1 이상이면:

    • 이전에 처리해야 할 정점이 존재하며, 제약 조건이 발생하게 된다.

위상정렬 #2: 라면 끓이기 작업의 선후 관계 (Dependency Graph for Cooking Instant Ramen)

라면 끓이기 작업을 선후 관계에 따라 그래프로 표현한 것이다. 각 작업은 노드 (Nodes)로, 작업 간 관계는 간선 (Edges)으로 나타낸다. 위상 정렬이 어떻게 실생활 작업에 적용될 수 있는지를 보여준다.

선후 관계(Precedence Relationship): 어떤 사상 A가 일어난 뒤에 사상 B가 관측되는 관계를 뜻한다. the specific order in which certain components or joints of a product must be disassembled, based on their relationship to each other.

✅ 그래프 설명:

  • 초기 상태 (Step a): 진입 차수가 0인 노드 선택 (Choose Nodes with In-degree 0):

    • "냄비에 물 붓기"와 "라면 봉지 뜯기"는 진입 차수가 0이다.

    • 예제에서는 "냄비에 물 붓기"를 먼저 선택하였다.

  • 진출 간선 제거 (Step b): "냄비에 물 붓기"와 연결된 진출 간선 (Outgoing Edges)을 제거하였다. 이 작업으로 "점화"가 진입 차수 0이 되어 선택된다.

  • 점화 이후 (Step c): "점화"와 연결된 노드 3개가 활성화된다: "라면 넣기", "수프 넣기", "계란 풀어넣기". 하지만 이들은 여전히 다른 간선과 연결되어 있어 바로 선택할 수 없다.

  • 다음 작업 선택 (Step d): "라면 봉지 뜯기"는 더 이상 연결된 간선이 없으므로 선택되었다.

  • 라면과 수프 (Step e): "라면 넣기"와 "수프 넣기" 중에서 임의로 "수프 넣기"를 선택하여 제거한다. 순서에 상관없이 추가할 수 있다.

  • 마지막 단계 (Step f): 이제 남은 노드는 "계란 풀어넣기"로, 이를 제거하면 정렬이 완료된다.

✅ 위상 정렬의 활용:

  • 위상 정렬을 사용하면 선후 관계를 유지하면서 작업을 순서대로 수행할 수 있게 된다.

    • 예: 불 켜기 → 라면 봉지 뜯기 → 수프 또는 라면 추가.

  • 실생활 예시 (Real-world Analogy):

    • 서류를 작성해야 프린트를 할 수 있는 것처럼, 작업 간 의존성을 정리할 때 사용된다.

💡 중요 포인트 (Key Points)

  1. 작업 간 선후 관계 (Dependency Relationship)를 이해하는 것이 중요하다.

  2. 점화 (Start the Stove)는 모든 작업의 시작점이다.

  3. 특정 작업을 수행하려면 필요 조건 (Prerequisites)을 먼저 완료해야 한다.

  4. 위상 정렬은 이러한 순서를 결정해주는 효율적 알고리즘 (Efficient Algorithm)이다.

위상정렬 #3: 의사코드 (Pseudocode for Topological Sorting)

💡요약: 위상 정렬은 진입 차수가 0인 정점을 반복적으로 선택하여 결과 배열에 추가하고, 해당 정점과 연결된 간선을 제거하는 방식으로 진행된다. DAG 구조에서는 진입 차수가 0인 정점이 시작점이 되며, 정렬이 끝날 때까지 반복한다. 복수의 정렬이 가능한 이유는 진입 차수가 0인 정점이 동시에 여러 개 있을 수 있기 때문이다.

  • G: 그래프, v: 정점

  • 진입 차수 0인 정점 선택 (Choose a Node with In-degree 0): 그래프에서 진입 차수가 0인 정점 u를 선택한다. 그 이유는 DAG에서 a, g는 들어오는 간선이 없기 때문에 진입 차수가 0이 된다.

  • 결과 배열에 추가 (Add to Result Array): A[i] ← u 정점 u를 결과 배열 A[i]에 추가한다.

  • 간선 제거 (Remove Outgoing Edges): 정점 u에 진출한 간선을 모두 제거한다.연결된 다른 정점들의 진입 차수를 업데이트한다.

  • 반복 (Repeat): 정점의 개수만큼 위 과정을 반복하여 모든 정점을 정렬하게 된다.

  • 복수의 정렬 가능성: 만약 진입 차수 0인 정점이 여러 개 (Multiple Nodes with In-degree 0)라면, 임의로 하나를 선택해도 된다. 선택 순서에 따라 여러 위상 정렬 결과가 나올 수 있다.

✅ 중요 포인트 (Key Points)

  1. 진입 차수 0인 정점 (Nodes with In-degree 0): 그래프에서 시작점으로 사용할 수 있는 정점.

  2. 진출 간선 제거 (Remove Outgoing Edges): 정렬된 정점의 간선을 제거하며, 연결된 다른 정점들의 진입 차수를 업데이트

  3. 복수의 정렬 가능 (Multiple Sorting Orders): 선택 순서에 따라 결과가 달라질 수 있다.

  4. 시간 복잡도 (Time Complexity): O(E + V), 여기서 E는 간선 수, V는 정점 수를 뜻한다.

위상정렬 #4 : 자료구조 (Topological Sorting with Data Structures)

✅ 진입 차수 계산하기 (Calculate In-degree): 노드의 진입 차수를 계산하여 배열에 저장

  • 노드 1에서 2, 3으로 연결된 상태이다. D[2]와 D[3]의 진입 차수를 각각 1씩 증가시킨다.

  • 결과: 진입 차수 리스트 D[N]는 다음과 같이 설정된다

    • 1번 노드: 0 (들어오는 간선 없음).

    • 2번, 3번 노드: 1 (노드 1에서 들어오는 간선).

    • 4번, 5번 노드: 2 (다른 두 노드에서 들어오는 간선).

✅진입 차수 0인 노드 선택 (Select Nodes with In-degree 0)

  • 진입 차수(In-degree) 0인 노드를 선택하여 정렬 리스트에 저장한다.

    • 처음에는 노드 1이 진입 차수 0이므로 선택되었다.

    • 노드 1과 연결된 간선을 제거하면서, 2번과 3번의 진입 차수를 각각 1 감소시킨다.

    • 결과: 2번, 3번 노드의 진입 차수가 0이 된다.

✅ 과정 반복 (Repeat Until All Nodes are Processed)

  • 진입 차수 0이 된 2번 노드를 선택하고, 정렬 리스트에 추가한다.

    • 노드 2와 연결된 노드 4와 5의 진입 차수를 각각 1 감소시킨다.

  • 그다음 3번 노드를 선택하고, 진입 차수를 업데이트한다.

  • 4번 노드와 5번 노드가 순차적으로 선택되며, 정렬이 종료된다.

  • 2와 3의 순서는 임의로 선택할 수 있으므로 복수의 정렬 결과가 가능하다.

💡 중요포인트

  • 진입 차수 계산 (Calculate In-degrees): 각 노드의 진입 차수를 미리 계산하여 정렬 과정을 준비한다.

  • 진입 차수 0인 노드 선택 (Select Nodes with In-degree 0): 진입 차수 0인 노드를 우선 선택하여 처리한다. 연결된 간선을 제거하며 다른 노드들의 진입 차수를 업데이트한다.

  • 복수 정렬 가능성 (Multiple Valid Orders): 동일한 진입 차수를 가진 노드 순서는 임의로 선택할 수 있으므로, 여러 정렬 결과가 가능하다.

위상정렬 #5 : 의사코드 - DFS 버전 (Topological Sorting with DFS)

위상 정렬의 이 버전은 깊이 우선 탐색 (Depth-First Search, DFS) 알고리즘을 사용한다.

  • DFS는 끝까지 탐색한 후 뒤로 돌아오는 재귀적인 구조를 가집니다.

  • DFS 기반 위상 정렬은 깊이 우선 탐색을 사용하여, 노드의 방문 여부를 확인하며 모든 노드를 탐색하개 된다.

  • 따라서, 위상 정렬에서는 가장 마지막에 도달한 노드부터 정렬이 시작된다.

  • 거꾸로 정렬 (Reverse Order): DFS는 결과를 거꾸로 쌓으므로, 위상 정렬 리스트는 DFS의 반환 순서대로 앞에서부터 정렬되게 된다.

  • 초기화 (Initialization)

    • 모든 노드를 방문 하지 않았다는 v.visited←NO 로 초기화한다.

    • 정점의 순서는 중요하지 않으므로, 임의의 정점 (Arbitrary Node)부터 탐색을 시작한다.

  • DFS 호출 (DFS-TS): 아직 방문하지 않은 노드라면, DFS를 호출한다.

  • 깊이 우선 탐색 (Perform DFS):

    • 현재 노드를 방문했음을 표시한다: v.visited←YES

    • 현재 노드의 인접한 노드들 (Adjacent Nodes)을 탐색한다.

      • 방문하지 않은 인접 노드가 있다면, 해당 노드에서 다시 DFS를 호출한다.

  • 결과 리스트 삽입 (Insert into Result):

    • 모든 인접 노드의 탐색이 끝난 후, 현재 노드를 결과 리스트의 맨 앞에 삽입한다.

    • DFS의 특성상, 가장 마지막에 방문한 노드부터 정렬이 시작된다.

💡 중요 포인트 (Key Points):

  1. 깊이 우선 탐색 (Depth-First Search): DFS를 사용해 모든 노드를 탐색하며, 재귀적으로 호출한다.

  2. 정렬 순서 결정 (Order of Sorting): 가장 나중에 방문한 노드가 정렬 리스트의 앞에 위치한다.

  3. 재귀 호출 (Recursive Calls): 인접한 노드를 모두 탐색할 때까지 DFS를 계속 호출한다.

  4. 시간 복잡도 (Time Complexity):

    • O(V + E) 여기서 V는 정점 수, E는 간선 수이다.

위상정렬 #6 : 작동방식 - DFS 버전 (Topological Sorting with DFS)

  • (b) 수프 넣기 선택: DFS를 시작하며 "수프 넣기" 노드가 선택되었다.

  • (c) 계란 풀어넣기 발견:

    • DFS를 수행하며 "계란 풀어넣기"까지 탐색한다.

    • "계란 풀어넣기"는 정렬의 마지막 자리로 설정된다.

  • (d) 수프 넣기로 돌아가기:

    • 계란 풀어 넣기는 갈 곳이 없으므로 DFS 경로를 되돌아가며 "수프 넣기"를 정렬 리스트의 두 번째 자리에 설정하게 된다.

  • (e) 임의 선택 (냄비에 물 붓기):

    • DFS를 수행할 새로운 시작 노드로 "냄비에 물 붓기"를 선택하였다.

  • (f) 점화로 이동:

    • "냄비에 물 붓기"에서 DFS를 통해 "점화"로 이동한다.

  • (g) 라면 넣기 탐색:

    • "점화"에서 연결된 "라면 넣기"로 이동하며, "라면 넣기"가 DFS 종료 지점으로 설정된다.

    • "라면 넣기"는 정렬의 세 번째 자리를 차지한다.

  • (h) DFS 경로 거슬러 올라가기:

    • DFS를 되돌아가며 "점화"를 네 번째 자리로 설정한다.

  • (i) 냄비에 물 붓기 정렬:

    • "냄비에 물 붓기"가 정렬의 다섯 번째 자리에 설정된다.

  • (j) 라면 봉지 뜯기:

    • 마지막 남은 노드인 "라면 봉지 뜯기"가 정렬의 첫 번째 노드로 설정된다.

최종 순서 (Final Order):

  • "라면 봉지 뜯기"→"계란 풀어넣기"→"수프 넣기"→"라면 넣기"→"점화"→"냄비에 물 붓기"

💡 중요 포인트 (Key Points):

  1. DFS 특성 활용: 깊이 우선 탐색의 특성을 통해 가장 깊은 노드부터 역순으로 정렬되었다.

  2. 거꾸로 정렬 (Reverse Order): DFS 종료 시점부터 정렬 리스트에 추가하므로, 결과가 역순으로 쌓이게 된다.

  3. 임의 선택 가능 (Arbitrary Selection): 시작할 노드가 여러 개일 경우, 임의로 선택할 수 있으며 결과적으로 복수의 정렬 순서가 가능하다.

2️⃣최단 경로 알고리즘 (Shortest Path Algorithm)

💡정리: 최단 경로 (Shortest Path)란 두 정점 사이의 경로들 중 간선의 가중치 합 (Sum of Edge Weights)이 가장 작은 경로를 말한다. 예를 들어, 노드 A → 노드 B로 가는 여러 경로 중 가중치가 최소인 경로가 최단 경로가 된다.

최단 경로 알고리즘은 그래프 이론에서 중요한 개념으로, 실생활의 네트워크 경로 탐색, 물류 최적화, 길 찾기 등에서 널리 활용되고 있다.

✅ 최단 경로 알고리즘을 위한 조건

  1. 방향성 (Direction):

    • 그래프가 방향성을 가지면, A → B와 B → A의 경로가 달라진다.

    • 따라서 방향성을 명확히 정의해야 한다.

  2. 가중치 (Weights):

    • 각 간선은 특정 비용(가중치)을 가진다

    • 가중치는 경로의 총 비용을 계산하는 데 사용된다.

✅ 음수 가중치와 사이클

  1. 음수 가중치 (Negative Weights):

    • 간선의 가중치가 음수인 경우에도 최단 경로를 구할 수 있다.

    • 단, 사이클이 없는 경우에만 적용 가능하다.

  2. 음의 사이클 (Negative Cycle):

    • 사이클(순환)이 존재하며, 그 가중치 합이 음수일 경우 문제가 발생한다.

      • 예: 음수 가중치를 가진 간선을 따라 계속 순환하면 비용이 무한히 줄어드는 현상이 발생하게 된다.

    • 이럴 경우엔, 최단 경로를 정의할 수 없게 되며, 알고리즘이 무한 루프에 빠질 수 있다.

    • 하지만 음수 가중치가 있어도문제가 되지 않는다. 알고리즘을 통해 최단경로를 구할 수 있다. 사이클이 생기는 경우만 안되는 것이다.

  3. 음의 사이클 탐지 (Detecting Negative Cycles):

    • 이따 배울 벨만-포드 알고리즘 (Bellman-Ford Algorithm)은 음의 사이클 여부를 탐지할 수 있는 알고리즘이다. 최단 경로 문제를 해결하는 데 사용된다.

✅ 무방향 그래프와 방향 그래프

  • 무방향 그래프는 양방향 간선을 포함하는 방향 그래프로 변환하여 최단 경로 알고리즘을 적용할 수 있다. 예) A — B → A → B로 변환

최단 경로 알고리즘 #1 : 분류 (Type of Shortest Path Algorithm)

💡정리: 최단 경로 알고리즘은 크게 두 가지로 나뉜다. 알고리즘은 문제 상황에 맞게 선택되며, 다음 강의에서는 각 알고리즘의 구현 및 세부 원리를 배울 예정이다.

  1. 단일 시작점 최단 경로: 하나의 출발점에서 모든 노드까지의 최단 경로를 계산.

  2. 모든 쌍 최단 경로: 모든 노드 간의 최단 경로를 계산.

✅단일 시작점 최단 경로 (Single-Source Shortest Path)

  • 개념: 그래프에서 하나의 시작점에서 출발하여 모든 노드까지의 최단 경로(최솟값)를 구하는 알고리즘이다.

    • 시작점에서 종료점을 정하지 않고, 시작점에서 그래프의 모든 정점으로 가는 경로를 계산한다.

  • 특징: 좀 복잡해 보이는 과정이다. 비교적 복잡도가 낮은 알고리즘을 사용할 수 있지만, 그래프의 크기에 따라 여전히 복잡도가 높은 편이다.

  • 주요 알고리즘:

    1. 다익스트라 알고리즘 (Dijkstra's Algorithm):

      • 간선 가중치가 모두 양수일 때 사용한다.

      • 시간 복잡도: O(V log V + E) (우선순위 큐 활용 시).

    2. 벨만-포드 알고리즘 (Bellman-Ford Algorithm):

      • 음수 가중치를 포함한 그래프에서도 사용 가능하다.

      • 음의 사이클 탐지 가능하다.

      • 시간 복잡도: O(V⋅E)

    3. 사이클이 없는 그래프 (Acyclic Graph):

      • 그래프에 사이클이 없을 경우, 더 간단하고 효율적인 알고리즘 사용이 가능하다.

      • 위상 정렬 기반으로 구현한다.

      • Acyclic : Not displaying or forming part of a cycle.

✅ 모든 쌍 최단 경로 (All-Pairs Shortest Path)

  • 개념: 그래프 내 모든 정점 쌍 사이의 최단 경로를 계산하는 알고리즘이다.

    • 단일 시작점보다 복잡도가 당연하게도 훨씬 높다.

  • 특징: 모든 노드와 모든 노드 사이의 경로를 고려하므로, 그래프의 크기가 클수록 계산량이 기하급수적으로 증가하게 된다.

  • 주요 알고리즘:

    1. 플로이드-워샬 알고리즘 (Floyd-Warshall Algorithm):

      • 모든 쌍 최단 경로를 계산하는 대표적인 알고리즘이다.

      • 시간 복잡도: O(V³)

    2. 존슨 알고리즘 (Johnson's Algorithm):

      • 음수 가중치를 포함한 그래프에서도 사용 가능한 알고리즘이다.

      • 다익스트라 알고리즘과 벨만-포드 알고리즘을 조합하여 효율적으로 계산할 수 있다.

      • 시간 복잡도: O(V² log V + V ⋅ E)

💡 알아야 할 핵심

  1. 최단 경로 알고리즘의 두 가지 분류:

    • 단일 시작점 최단 경로 (Single-Source Shortest Path):
      시작점에서 모든 노드까지의 최단 경로.

    • 모든 쌍 최단 경로 (All-Pairs Shortest Path):
      그래프의 모든 정점 쌍 사이의 최단 경로.

  2. 각 알고리즘의 목적에 따른 사용:

    • 시작점과 종료점이 명확하면 단일 시작점 알고리즘을 사용.

    • 전체 그래프의 모든 정점 쌍 경로가 필요하면 모든 쌍 최단 경로 알고리즘을 선택.

  3. 주요 알고리즘 목록:

    • 단일 시작점: 다익스트라, 벨만-포드, 위상 정렬 기반 알고리즘.

    • 모든 쌍: 플로이드-워샬.

최단 경로 알고리즘 #2 : 알아야 할 개념, 완화 (Concept you should know in Single-Source Shortest Path Algorithms)

“완화(relaxation)”란?

최단 경로 알고리즘에서 현재 계산된 거리 값을 더 작은 값으로 갱신하는 과정이다. 이 과정은 새로운 정점이나 경로를 추가적으로 고려했을 때 더 짧은 거리 경로를 발견할 가능성이 있을 때 수행된다.

  1. 현재 상태:

    • 시작점 r에서 특정 정점 v까지의 거리 A는 이미 계산되어 있다.

    • u는 현재 탐색 중인 정점이다.

    • w_u,v는 u에서 v로의 간선 가중치를 의미한다.

  2. 새로운 경로 탐색:

    • r → u 까지의 거리 B가 이미 계산되어 있다고 가정한다.

    • u → v 를 거쳐 r → u 의 거리를 계산하면, 총 거리는 B+w{u,v}​가 된다.

  3. 완화 조건:

    • 기존 거리 A와 새로운 경로 거리w_{u,v}를 비교한다.

    • 만약 새로운 경로의 거리가 기존 거리보다 작다면:

      • A > B + w{u,v}

      • v까지의 최단 거리 값을 A에서 B + w_{u,v}로 업데이트한다.

  4. 업데이트:

    • 갱신된 거리 값은 A ← B + w{u,v} ​로 저장된다.

    • 이 과정을 모든 가능한 간선에 대해 반복하여 최적의 경로를 찾아가게 된다.

✅ 완화의 목적

완화는 기존에 계산된 거리 값이 정확하지 않을 가능성을 염두에 두고, 새로운 경로를 통해 더 짧은 거리 값을 찾아내는 과정이다. 최종적으로 모든 간선을 완화하여 최단 경로를 도출할 수 있다.

💡 이미지의 주요 포인트

  1. 기존 거리 A: 시작점 r에서 정점 v까지의 거리.

  2. 새로운 거리 B + w_{u,v}: r에서 u를 거쳐 v까지 가는 거리.

  3. 비교 조건: 새로운 경로가 더 짧으면 기존 값을 갱신.

  4. 결과: 최단 거리 리스트에서 정점 v의 값을 업데이트.

  5. 다익스트라(Dijkstra) 및 벨만-포드(Bellman-Ford) 알고리즘에서 이 완화 과정을 활용하여, 인접 노드 간의 최단 거리를 반복적으로 갱신해 나간다.

최단 경로 알고리즘 #4 : 최단 경로 알고리즘의 동적 프로그래밍 적용

✅ DP 테이블

  • 정의: 시작점 r로부터 특정 정점 v까지의 거리를 저장한다. 이를 v.dist로 표시한다.

✅ 점화식(Recurrence relation)

  • 점화식의 목적은 현재까지 계산된 거리 값을 새로운 경로를 통해 최소화하는 것이.

    • v.dist : 현재까지 계산된 시작점에서 정점 v까지의 거리.

    • u.dist : 시작점에서 정점 u까지의 거리.

    • w_{u,v}​: 정점 u에서 v로 이동하는 간선의 가중치.

  • 현재 상태:

    • 시작점 r에서 u까지의 거리 u.dist는 이미 계산된 값이다.

    • u에서 v까지의 간선 가중치 w_{u,v}​를 추가로 고려한다.

  • 새로운 거리 계산:

    • 시작점 r에서 v까지의 기존 거리 v.dist와 새로운 경로를 통해 계산된 거리 u.dist + w_{u,v}​를 비교한다.

  • 최소 거리 선택:

    • 기존 거리 v.dist와 새로운 거리 u.dist + w{u,v} 중 더 작은 값을 v.dist로 업데이트한다.

  • 결과:

    • u를 거친 새로운 경로가 더 짧다면 DP 테이블에서 v.dist 값을 갱신하게 된다.

최단 경로 알고리즘 #5 : 사이클이 없는DAG(Directed Acyclic Graph) 최단 경로를 구하는 알고리즘

사이클이 없는(DAG) 최단 경로 알고리즘은 DFS 기반 위상 정렬과 같이 위상 정렬 기반으로 동작하는 알고리즘이다. 양수 및 음수 가중치를 모두 허용하며, 음수 사이클이 없는 DAG에서 안전하게 동작한다.

  1. 초기화 (Initialization):

    • 모든 정점 u ∈ V의 초기 거리 값을 무한대 (∞)로 설정한다. u.dist ← ∞ u

    • 시작점 r의 거리 값은 0로 설정한다 : r.dist ← 0

  2. 위상 정렬 (Topological Sort):

    • 그래프 G의 정점들을 위상 정렬 순서로 나열한다.

    • 위상 정렬은 DAG에서 모든 정점의 선행 관계를 유지하며 정렬한다.

  3. 거리 갱신 (Relaxation):

    • 위상 정렬된 순서대로 각 정점 u를 순회한다.

    • 각 정점 u의 인접 리스트에 포함된 모든 정점 v ∈ u.adjlist에 대해:

      • 만약 u.dist + w{u,v} < v.dist 이면, v.dist 값을 u.dist + w{u,v}로 업데이트 한다.

      • v.prevv를 u로 설정하여 최단 경로를 추적 가능하도록 유지한다.

  4. 최종 결과:

    • v.dist는 시작점 r에서 각 정점 v까지의 최단 거리를 저장한다.

    • v.prev 를 통해 각 정점에 도달하는 최단 경로를 역추적할 수 있게 된다.

최단 경로 알고리즘 #6: 사이클이 없는DAG(Directed Acyclic Graph) 최단 경로를 구하는 알고리즘의 동작 예

1단계: 그래프 입력 및 시작 정점 설정

  • DAG(Directed Acyclic Graph)가 주어졌다.

  • 시작 정점은 r로 설정되었다.

  • 모든 간선은 가중치가 있으며, 정점 간의 방향이 지정되어 있다.

2단계: 위상 정렬 수행

  • DAG에서 위상 정렬을 수행하여 정점들의 처리 순서를 정한다.

  • 위상 정렬 순서는 r → 원형 정점 → 하트 정점 → 마름모 정점 → 삼각형 정점으로 결정된다.

3단계: 거리 초기화

  • 시작 정점(r)의 거리는 0으로 설정되고, 나머지 정점의 초기 거리는 무한대(∞)로 설정된다.

  • 초기 상태: r: 0 , 나머지 정점: ∞

4단계: 정점 r의 거리 갱신

  • 정점 r(0)에서 인접 정점으로 거리 값을 갱신한다.

    • r → 원형 정점: 거리 3, r → 하트 정점: 거리 7

    • 결과: r: 0, 원형: 3, 하트: 7, 나머지 정점: ∞

5단계: 원형 정점의 거리 갱신

  • 정점 원형에서 인접 정점으로 거리 값을 갱신한다.

    • 원형 → 하트 정점: 기존 거리 7과 새로운 거리 3 + 4 = 7 비교 → 갱신 필요 없음.

    • 결과: r: 0, 원형: 3, 하트: 7, 나머지 정점: ∞

6단계: 하트 정점의 거리 갱신

  • 정점 하트에서 인접 정점으로 거리 값을 갱신한다.

    • 하트 → 마름모 정점: 거리 7 + (-2) = 5

    • 결과: r: 0, 원형: 3, 하트: 7, 마름모: 5, 삼각형: ∞

7단계: 마름모 정점의 거리 갱신

  • 정점 마름모에서 인접 정점으로 거리 값을 갱신한다.

    • 마름모 → 삼각형 정점: 거리 5 + (-3) = 2

    • 결과: r: 0, 원형: 3, 하트: 7, 마름모: 5, 삼각형: 2

8단계: 최종 결과

  • 모든 정점의 최단 거리가 계산되었다. 최단 경로는 아래와 같다:

    • r → 원형(3)

    • r → 하트(7)

    • r → 하트 → 마름모(5)

    • r → 하트 → 마름모 → 삼각형(2)

  • 굵은 간선으로 최단 경로를 표시하였다.

💡시작점이 있는 최단 경로 알고리즘의 유형

단일 시작점 최단 경로(Single Source Shortest path)란?

  • 그래프에서 하나의 시작점 (Single Source)에서 출발하여, 모든 정점 (All Nodes)까지의 최단 경로를 구하는 알고리즘이다.

  • 이번 시간에는 두 가지 주요 알고리즘을 배우게 된다:

    1. 다익스트라 알고리즘 (Dijkstra's Algorithm)

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

✅ 다익스트라 알고리즘 (Dijkstra's Algorithm)

  • 특징: 음의 가중치 (Negative Weights)를 허용하지 않음 (Not Allowed).

    • 예: 간선의 가중치가 -2인 경우 사용 불가.

    • 시작점에서 가장 가까운 정점부터 탐색하며 비용을 갱신 (Update Costs)하는 알고리즘이다..

  • 수행 시간 (Time Complexity):

    • O(E log V) 여기서 E는 간선의 개수, V는 정점(vertex, node)의 개수이다.

    • 매우 빠른 알고리즘이다.

    • 정점(vertex) node를 의미한다. 간선(edge) 노드 간에 연결되어 있는 선을 의미

  • 사용 조건:

    • 모든 간선의 가중치가 양수일 때 (All Positive Weights) 사용한다.

    • 대규모 그래프에서 효율적이다.

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

  • 특징: 음의 가중치 (Negative Weights)를 허용한다.

    • 예: 간선의 가중치가 -2인 경우에도 사용 가능하다.

    • 모든 간선을 반복적으로 확인하며 비용을 갱신 (Update Costs)한다.

  • 수행 시간 (Time Complexity):

    • O(E ⋅ V), 상대적으로 느린 알고리즘이다.

  • 사용 조건:

    • 그래프에 음의 가중치 (Negative Weights)가 포함되어 있을 경우 사용한다.

    • 음의 가중치 사이클(무한히 비용을 감소시키는 경로)을 탐지할 수도 있다.

3️⃣다익스트라 알고리즘(Dijkstra's Algorithm)

다익스트라 알고리즘의 과정 (Detailed Analysis of Dijkstra's Algorithm)

1. 초기화 (Initialization):

  • 시작점에서 출발하기 위해, 시작점을 제외한 모든 정점의 거리 (Distance)를 무한대 (Infinity)로 설정한다.

    • 이 단계는 알고리즘이 최단 경로를 찾기 시작하기 위한 준비 단계이다.

2. 신규 정점 선택 (Select New Node):

  • 방문하지 않은 정점 중에서 거리가 가장 짧은 정점 (Node with the Shortest Distance)을 선택한다.

    • 예: 시작점 A에서 출발하여 인접한 노드 B, C 중에서 가장 비용이 작은 노드를 선택한다.

    • 이 과정을 "신규 정점 탐색 (New Node Selection)"이라고 한다.

3. 거리 완화 (Distance Relaxation):

  • 선택된 정점(노드)의 인접한 노드들 (Adjacent Nodes)을 탐색하며 거리를 업데이트 (Update Distance)합니다.

    • 만약 새로운 경로를 통해 도달하는 비용이 더 작다면, 그 값을 갱신한다.

    • 예: A → B의 비용이 5이고, A → C → B를 통해 비용이 4라면, B의 거리 값을 4로 갱신한다.

4. 반복 (Repeat Until All Nodes Are Visited):

  • 모든 정점이 방문될 때까지 위 과정을 반복한다

    • 새로운 정점을 선택 → 인접한 정점의 거리 업데이트

5. 종료 (Termination):

  • 모든 정점의 최단 경로가 계산되었으면 알고리즘이 종료되게 된다.

    • 결과적으로, 시작점에서 모든 정점으로 가는 최단 경로가 계산된다.

✅중요 포인트 (Key Points)

  • 다익스트라 알고리즘은 단계별로 정점과 거리를 갱신 (Update Step by Step)하며 최단 경로를 계산하는 방식이다.

  • 매 단계마다 최단 경로를 확정하기 때문에 효율적이고 빠르다. 단순한 구조 덕분에 널리 사용된다.

  • 음의 가중치가 없을 때만 사용 가능하며, O(E log V)의 시간 복잡도를 가진다.

다익스트라 알고리즘 #1: 의사코드 분석 (Analysis of Dijkstra's Algorithm Pseudocode)

1. 알고리즘 초기화 (Initialization):

  • 방문한 정점 집합 S (Visited Nodes Set):

    • 초기 상태에서는 아무 정점도 방문하지 않았으므로, S는 공집합 (Empty Set)으로 설정된다. S←ϕ

    • ϕ는 수학에서 공집합 (empty set)을 나타내는 기호이다. 이는 비어 있는 집합을 의미하며, 집합 안에 어떤 요소도 포함되지 않은 상태를 나타낸다. 알고리즘이 진행되면서 방문한 정점들은 S에 추가되어, 점점 채워지게 된다.

  • 거리 초기화 (Distance Initialization):

    • 시작점을 제외한 모든 정점의 거리를 무한대 (Infinity)로 초기화한다. u.dist ← ∞

    • 시작점의 거리를 0으로 설정한다. r.dist ← 0

2. 반복문 (Main Loop):

  • 반복문은 모든 정점이 방문될 때까지 실행되게 된다.

    • 방문한 정점의 집합 S가 전체 정점 집합 V와 같아질 때 종료된다. while (S ≠ V)

3. 방문하지 않은 정점 중 최소 거리 정점 선택 (ExtractMin):

  • 방문하지 않은 정점 중에서 최단 거리 값을 가진 정점 u를 선택한다: u ← extractMin(V−S)

    • 이 과정은 앞에서 배운 그리디 알고리즘 (Greedy Algorithm)의 특성을 따른다.

4. 방문 집합에 추가 (Add to Visited Set):

  • 선택된 최단 거리 값을 가진 정점 u를 방문한 집합 S에 추가한다: S ← S∪{u}

  • S: 이미 방문한 정점들의 집합

  • {u}: 새롭게 방문한 정점 u를 포함하는 집합.

  • S ∪ {u}: 현재 집합 S에 새 정점 u를 합쳐 새로운 방문 집합을 만든다는 뜻.

  • 특정 정점 u를 방문한 것으로 기록하는 과정을 수학 기호로 표시하였다.

5. 거리 완화 (Distance Relaxation):

  • u와 인접한 노드들 (Adjacent Nodes)의 거리를 업데이트한다.

    • 새로운 경로를 통해 비용이 더 작아지는 경우, 거리 값을 갱신하게 된다:

      • v.dist ← u.dist + wuv

      • v.prev ← u

    • 이 과정을 완화 (Relaxation)이라고 부른다.

  • 💡 v.dist ← u.dist + wuv 추가 설명

    • 현재 정점 u를 통해 정점 v로 가는 새로운 경로를 고려하여, v까지의 거리 값(v.dist)을 갱신한다는 뜻이다.

    • u.dist: 시작점에서 정점 u까지의 최단 거리이다.

    • w{uv}: 정점 u에서 v로 가는 간선의 가중치이다.

    • u.dist + w{uv}: 시작점에서 u를 거쳐 v까지 가는 경로의 총 거리를 뜻한다.

    • v.dist: 기존에 저장된 시작점에서 v까지의 최단 거리 값이다.

  • 💡v.prev ← u 추가 설명

    • 정점(노드) v까지의 최단 경로에서 바로 이전 정점(노드)이 u임을 기록하는 곳이다.

    • v.prev는 최단 경로를 추적하기 위해 사용된다.

    • 갱신된 경로로 v.dist가 더 짧아졌다면, u가 v의 직전 노드임을 저장하는 곳이다.

💡중요 포인트 (Key Points)

  1. 다익스트라 알고리즘은 그리디 알고리즘 (Greedy Algorithm)으로 작동한다.

    • 현재 상태에서 최적의 선택(최소 거리 정점)을 반복적으로 수행하게 된다.

  2. 시간 복잡도 (Time Complexity):

    • O(E log ⁡V)(우선순위 큐를 사용할 경우).

  3. 음의 가중치 허용 불가 (Negative Weights Not Allowed):

    • 음수 가중치가 있는 그래프에서는 사용 불가능하다.

다익스트라 알고리즘 #2: 그래프 예제 (Dijkstra's Algorithm in Action)

1. 초기화 (Initialization): 시작점 노드 0에서 알고리즘이 시작된다.

  • 노드 0의 거리 값은 0 (0.dist = 0)으로 설정되고, 나머지 노드들의 거리 값은 무한대 (Infinity)로 초기화된다.

2. 첫 번째 단계 (Step 1): 0에서 인접한 노드들(8, 9, 11)의 거리 값을 업데이트한다.

  • 업데이트 결과: 노드 8: 0 + 8 = 8, 노드 9: 0 + 9 = 9, 노드 11: 0 + 11 = 11

  • 방문한 노드(0)는 고려하지 않는다. 가장 작은 거리 값(8)을 가진 노드 8이 선택된다.

3. 두 번째 단계 (Step 2): 노드 8에서 인접한 노드를 탐색하여 거리 값을 업데이트한다.

  • 8 → 10 : 8 + 10 = 18

    • 업데이트 결과: 노드 10의 거리 값이 무한대에서 18로 설정되었다.

    • 다음으론 나머지 노드에서 가장 작은 거리 값(9)을 가진 노드 9가 선택된다.

4. 세 번째 단계 (Step 3): 노드 9에서 인접한 노드를 탐색한다.

  • 9 → 10: 기존 거리 값(18)보다 새로운 값(9 + 1 = 10)이 더 작으므로 업데이트한다.

  • 기존의 값이 더 작은 경우에는 업데이트 되지 않으므로 11은 변하지 않고 그대로이다.

    • 업데이트 결과: 노드 10: 18 → 9+1 = 10

    • 다음으로 가장 작은 거리 값(10)을 가진 노드 10이 선택되게 된다.

5. 네 번째 단계 (Step 4): 노드 10에서 인접한 노드를 탐색한다.

  • 10 → 12: 기존 거리 값(무한대)에서 새로운 값(10 + 2 = 12)로 업데이트된다.

    • 업데이트 결과: 노드 12: 무한대 → 10 + 2 = 12

    • 업데이트 결과를 확인 한 후, 다음으로 가장 작은 거리 값(11)을 가진 노드 11이 선택된다. (이미 방문한 10은 선택 옵션에서 제외되었다)

6. 다섯 번째 단계 (Step 5): 노드 11에서 인접한 노드를 탐색합니다.

  • 11 → 19: 업데이트.

    • 업데이트 결과: 11이 바라보는 노드 2개, 19 : 무한대 → 11 + 8 = 19

    • 비용값이 최소인 값을 보니 다음으로 가장 작은 거리 값(12)을 가진 노드 12가 선택된다.

7. 여섯 번째 단계 (Step 6): 노드 12에서 인접한 노드를 탐색한다.

  • 12하고 연결된 노드는 16 하나밖에 없으므로 기존의 값보다 더 작은 16으로 설정이 된다.

  • 12 → 16: 기존 거리 값보다 새로운 값(12 + 4 = 16)로 업데이트한다.

    • 업데이트 결과: 노드 16: 19 → 12 + 4 = 16

    • 다음으로 가장 작은 거리 값(16)을 가진 노드 16이 선택된다.

8. 마지막 단계 (Step 7): 노드 16에서 인접한 노드를 탐색한다.

  • 16 → 19: 이미 방문한 노드로 더 이상 업데이트가 필요없다.

  • 모든 노드를 방문했으므로 알고리즘이 종료된다.

  • 시작점 노드 0에서 모든 노드까지의 최단 경로가 계산되었다.

  • 최적 경로 그래프: 각 노드로 가는 최단 경로가 붉은색 화살표로 표시되었다.

💡 중요 포인트 (Key Points)

  1. 다익스트라 알고리즘은 그리디 방식 (Greedy Approach)으로 최적의 해를 단계적으로 선택한다.

  2. 거리 값이 작은 노드부터 업데이트를 진행한다.

  3. 업데이트(완화) 과정 (Relaxation): 기존 거리 값보다 작은 값이 발견되면 갱신된다.

💡👀다익스트라(Dijkstra)❓

다익스트라는 이를 만든 수학자의 이름에서 유래되었다. 에츠허르 비버 다익스트라(Edsger Wybe Dijkstra)라는 네덜란드의 유명한 컴퓨터 과학자이다. 다익스트라는 컴퓨터 과학 발전에 큰 기여를 한 인물로, 특히 그래프 알고리즘과 소프트웨어 엔지니어링 분야에서 잘 알려져 있다. 1956년에 고안되어 오늘날까지도 다양한 응용 분야에서 사용되고 있다.

다익스트라 알고리즘 #3 : 자료구조 (Dijkstra's Algorithm Data Structure Example)

1. 인접 리스트로 그래프 구현 (Graph Representation Using Adjacency List)

adjacencyThe fact of being very near, next to, or touching something

  • 그래프를 인접 리스트 (Adjacency List)로 표현한다.

    • 각 노드는 자신과 연결된 인접 노드와 가중치 (Adjacent Node and Weight)를 저장한다.

      • 노드 1 → [노드 2(8), 노드 3(3)]

      • 노드 2 → [노드 4(4), 노드 5(15)]

      • 노드 3 → [노드 4(13)]

      • 노드 4 → [노드 5(2)]

  • 파이썬에선 리스트이지만 일반적으론 배열이다.

  • 2. 최단 거리 리스트 초기화 (Initialize Distance List): 최단 거리 리스트 (Distance List)를 초기화한다.

    • 시작 노드(1번)의 거리는 0으로 설정한다. D[1] = 0

    • 나머지 노드의 거리는 무한대 (Infinity)로 초기화한다. ∞

3. 가장 작은 거리 노드 선택 (Select Node with Minimum Distance)

  • 초기화된 리스트에서 가장 작은 값을 가진 노드를 선택한다.

    • 첫 번째로 선택되는 노드는 항상 시작점(1번)이다.

    • 선택된 노드(1번)와 연결된 인접 노드(2번, 3번)의 거리를 업데이트 (Update)한다.

      • 2번 노드: D [2] = min⁡ (∞, 0 + 8) =8

      • 3번 노드: D [3] = min ⁡(∞, 0 + 3) = 3

4. 거리 완화 (Relaxation): 선택된 노드와 연결된 노드들의 거리를 계속 업데이트한다.

  • 인접 리스트를 탐색하며, 새로운 경로가 더 짧다면 거리 값을 갱신한다.

  • 완화 과정:

    • 선택된 노드의 거리 값 + 간선의 가중치가 기존 거리 값보다 작다면 갱신.

    • 방문한 노드는 다시 선택되지 않도록 방문 리스트를 관리합니다.

5. 반복 (Repeat Until All Nodes Are Visited)

  • 위 과정을 모든 노드를 방문할 때까지 반복한다.

    • 1번 → 3번 → 2번 → 4번 → 5번 순서로 진행된다.

    • 각 단계에서 선택된 노드와 인접한 노드의 거리 값을 업데이트한다.

    • 모든 노드를 방문하면 알고리즘이 종료된다.

💡중요 포인트 (Key Points)

  1. 인접 리스트 사용: 그래프를 효율적으로 표현하고 탐색한다. (리스트 = 배열)

  2. 거리 완화: 최단 거리 값을 갱신하며 최적의 경로를 찾는다.

  3. 반복: 모든 노드를 방문할 때까지 최소 거리 노드를 반복적으로 선택하고 업데이트한다.

다익스트라 알고리즘 #4 : 상세 의사 코드 (Detailed Pseudocode of Dijkstra's Algorithm)

1. 주요 데이터 구조 (Key Data Structures):

  1. 노드와 엣지 (Nodes and Edges):

    • V: 노드 개수 (Number of Nodes)

    • E: 엣지 개수 (Number of Edges)

    • K: 출발 노드 (Start Node)

  2. 거리 리스트 (Distance List):

    • 각 노드로부터의 최단 거리 (Shortest Distance)를 저장.

    • 초기 값은 무한대 (Infinity)로 설정된다.

  3. 방문 리스트 (Visited List):

    • 각 노드가 방문되었는지 확인하는 체크리스트 (Checklist)이다.

  4. 인접 리스트 (Adjacency List):

    • 각 노드와 연결된 노드와 가중치를 저장한다.

    • 예: 노드 1 → [(노드 2, 가중치 8), (노드 3, 가중치 3)]

  5. 우선순위 큐 (Priority Queue):

    • 노드의 거리 값을 기준으로 가장 작은 값을 자동으로 선택해주는 큐.

    • 예: 거리 값이 작은 순서로 데이터를 출력한다.

2. 알고리즘 실행 과정 (Algorithm Steps):

  1. 초기화 (Initialization):

    • 거리 리스트: 출발 노드의 거리를 0으로 설정, 나머지는 무한대로 초기화.

    • 우선순위 큐: 출발 노드를 큐에 넣는다.

    • 위에서 설명했듯이 우선선위 큐는 노드의 거리 값을 기준으로 가장 작은 값을 자동으로 선택해주는 큐이다. 자동으로 거리가 최소인 노드를 선택하는 것이다. 출발노드의 거리는 0이므로 최소인 노드가 된다.

  2. 노드 선택 (Select Node):

    • 우선순위 큐에서 가장 작은 거리 값을 가진 노드를 선택한다.

    • 이미 방문한 노드인지 확인한다.

  3. 거리 업데이트 (Distance Update - Relaxation):

    • 선택된 노드와 연결된 인접 노드들의 거리 값을 확인한다.

    • 현재 노드의 거리 값 + 엣지 가중치와 기존 거리 값을 비교하여 더 작은 값으로 갱신한다.

  4. 우선순위 큐 업데이트 (Update Priority Queue):

    • 거리 값이 갱신된 인접 노드를 우선순위 큐에 추가한다.

  5. 반복 (Repeat): 위 과정을 모든 노드가 방문될 때까지 반복한다.

  6. 종료 (Termination): 모든 노드의 최단 거리 값이 계산되면 알고리즘이 종료된다.

💡중요 포인트 (Key Points)

  1. 우선순위 큐 (Priority Queue): 노드 선택 시 가장 작은 거리 값을 자동으로 제공하므로 효율적이다.

  2. 거리 완화 (Relaxation): 현재 노드와 연결된 노드의 거리를 비교하여, 더 작은 값으로 갱신한다.

  3. 시간 복잡도 (Time Complexity): O (E log ⁡V) (우선순위 큐 사용시)

4️⃣벨만-포드 알고리즘 (Bellman-Ford Algorithm)

벨만 포드알고리즘 과정에 대해서 살펴본다. 벨만포드는 음의 가중치를 허용한다는 특징이있다.

1. 초기화 (Initialization): 시작점 외 모든 정점의 거리 (Distance)를 무한대 (Infinity)로 설정한다.

  • 시작점의 거리는 0으로 설정한다.

  • 이 과정은 다익스트라 알고리즘과 동일하다.

2. 모든 간선 완화 (Relax All Edges)

다익스트라에서는 for문을 활용하여 알고리즘을 최적화 하는 방향이있었다. 하지만 벨만 포드는 음의 가중치를 허용하다 보니 같은 방식으로 진행이 불가능하다. 이유는 최소 비용을 선택 하였는데 음의 가중치가 있다면 그것보다 더 작은 값이 나타나게 되므로 음의 가중치를 허용하지 않는 다익스트라의 특성이 적용되기 때문이다 . 이로인해 모든 간선들을 순서대로 거리를 업데이트 하게 된다. 다익스트라보다 더 많은 완화과정이 필요한 단점이 있다.

  • 벨만-포드 알고리즘은 모든 간선을 반복적으로 완화 (Relaxation)한다. 다익스트라처럼 가장 작은 값을 가진 노드를 선택하지 않고, 모든 간선을 하나씩 확인하며 거리 값을 갱신한다

    • 이유❓

      • 음의 가중치 (Negative Weight)가 포함된 그래프에서는, 특정 경로를 선택하더라도 더 작은 값이 나올 가능성이 있기 때문이다.

      • 따라서 모든 간선을 탐색하며 거리 값을 업데이트하는 방식으로 작동한다.

  • 완화 과정 (Relaxation Process):

    • 각 간선을 탐색하며, 다음을 수행한다.

    • 새로운 거리 값 = 현재 거리 + 간선의 가중치

    • 만약 새로운 거리 값이 기존 거리 값보다 작다면, 거리 값을 업데이트한다.

3. 음의 사이클 여부 확인 (Detect Negative Cycle):

  • 벨만-포드 알고리즘의 장점은 음의 사이클 (Negative Cycle)을 탐지할 수 있다는 점이다.

    • 음의 사이클이란? 반복적으로 탐색할수록 비용이 계속 줄어드는 사이클.

      • 예: 한 사이클을 돌 때마다 비용이 -10씩 감소.

  • 탐지 방법:

    • 모든 간선에 대해 반복적으로 완화 과정을 수행한 뒤,

    • 또다시 거리 값을 업데이트했는데도 비용이 줄어든다면, 음의 사이클이 존재한다는 뜻이다.

  • 음의 사이클 여부에 따른 결과:

    • 사이클 있음 (Negative Cycle Exists): 경로가 무한히 줄어들기 때문에, 최단 경로를 정의할 수 없다.

    • 사이클 없음 (No Negative Cycle): 지금까지 계산된 최단 거리를 출력하며 알고리즘이 종료된다.

✅벨만-포드 알고리즘과 다익스트라 알고리즘 비교 (Comparison)

벨만-포드 알고리즘 #1: 의사코드 (Bellman-Ford Algorithm Pseudocode)

1. 초기화 (Initialization):

  • 시작점에서 출발하기 위해, 모든 정점의 거리를 무한대 (Infinity)로 설정한다.

  • 시작점의 거리 (Start Node Distance)는 0으로 초기화한다: r.dist ← 0

  • 이 과정은 다익스트라 알고리즘과 동일하다.

2. 정점 반복 (Vertex Loop):

  • 정점의 수가 V라면, V−1 반복한다 for i ← 1 to ∣V∣−1

    • 이유: 그래프에 정점이 4개라면, 최단 경로를 완전히 계산하기 위해 최대 3번의 거리 업데이트가 필요하기 때문이다.

3. 간선 완화 (Relaxation of Edges):

  • 각 정점 반복 내부에서는 모든 간선 (Edges)을 따라가며 거리 값을 업데이트한다: for each (u, v) in E

  • 완화 조건 (Relaxation Condition): if (u.dist + wuv < v.dist)

      • 현재 노드 u를 거쳐 v로 가는 경로가 기존 경로보다 짧다면,

        • v.dist ← u.dist + wuv

        • v.prev ← u (최단 경로의 이전 노드 기록).

  • 이 과정은 다익스트라와 비슷하지만, 모든 간선을 탐색한다는 점에서 차이가 있다. (for each)

4. 음의 사이클 탐지 (Negative Cycle Detection):

  • 정점 반복이 끝난 후, 추가로 한 번 더 모든 간선을 탐색한다.

  • 만약 다음 조건이 참이라면, 음의 사이클 (Negative Cycle)이 존재한다는 뜻이다:

    • if (u.dist + wuv < v.dist) 이미 계산이 끝난 상태에서 더 작은 값이 발견되었다면, 이는 음의 사이클로 인해 발생한 것이다.

      • 출력: "음의 사이클 발견, 해 없음 (Negative Cycle Detected, No Solution)".

5. 알고리즘 종료 (Termination):

  • 음의 사이클이 없는 경우, 계산된 최단 거리 값을 출력하며 종료한다.

벨만-포드 알고리즘 #2: 작동 예제 (Bellman-Ford Algorithm in Action)

1. 초기 상태 (Initial State): 노드 0이 시작점이다.

  • 시작점의 거리는 0, 나머지 노드들의 거리는 무한대 (Infinity)로 초기화된다.

2. 첫 번째 라운드 (First Round): 0번 노드와 연결된 모든 노드를 업데이트한다.

  • 0 → 8: 거리 값은 0 + 8 = 8 0 → 9: 거리 값은 0 + 9 = 9 0 → 11: 거리 값은 0 + 11 = 11

  • 결과: D[8] = 8, D[9] = 9, D[11] = 11

3. 두 번째 라운드 (Second Round): 모든 간선을 따라 거리 값을 업데이트 한다.

    • 9 → 10: 기존 값(∞)보다 새로운 값 9 + 1 = 10 으로 업데이트 되었다. 그 뒤에

      • 9 → -15: 기존 값(8)보다 작은 9−15 =−6 으로 업데이트 되었다.

      • 9 → 11: 9 + 3 = 12가 되어 더 큰값이므로 작은값인 11이 계속 유지된다.

      • 11 → 19: 기존 값(∞)보다 새로운 값 11 + 8 = 19 두개의 노드가 업데이트 되었다.

  • 결과: D[−6], D[10], D[19] 가 새롭게 계산된다.

4. 반복 과정 (Iterations):

  • 다음 라운드들:

    • 모든 간선을 탐색하며 거리 값을 반복적으로 갱신한다.

    • 벨만-포드는 정점의 수(V)가 5라면 V−1 = 4번 반복.

    • 각 라운드에서 모든 간선의 거리 값을 계산하고 일률적으로 업데이트한다.

    • 중요한 점은 다익스트라에서는 가장 작은 값을 선택해서 그것에 인접한 노드를 업데이트하는 반면 벨만포트는 간선들을 모두 일률적으로 업데이트한다는 점이다. 실질적으로 순서가 중요하진 않고 의사코드의 과정이 중요하다.

5. 최종 결과 (Final Result):

  • 각 노드로의 최단 거리가 계산된다.

  • 벨만-포드는 모든 간선을 탐색하며 최단 경로를 확인하므로, 특정 순서에 의존하지 않는다.

✅ 벨만-포드와 다익스트라의 차이 (Difference from Dijkstra):

방식 (Method):

  • 다익스트라는 가장 작은 값을 가진 노드부터 업데이트한다.

  • 벨만-포드는 모든 간선을 반복적으로 탐색하며 업데이트한다.

음의 가중치 (Negative Weights):

  • 다익스트라는 음의 가중치를 허용하지 않는다.

  • 벨만-포드는 음의 가중치를 허용하며 음의 사이클도 탐지할 수 있다.

벨만-포드 알고리즘 #3: 자료구조( Data Structure in Bellman-Ford Algorithms)

1. 초기화 (Initialization): 벨만-포드 알고리즘은 간선(Edge)을 중심으로 작동한다.

  • 간선의 정보를 담기 위해 엣지 리스트 (Edge List)를 사용한다.

    • 엣지 리스트는 다음과 같이 구성된다: 출발 노드 (Start Node),종료 노드 (End Node), 가중치 (Weight)

  • 최단 거리 리스트 (Shortest Distance List):

    • 시작점(0번 노드)의 거리는 0으로 설정.

    • 나머지 모든 노드의 거리는 무한대 (Infinity)로 초기화.

    • 초기화된 리스트는 알고리즘의 첫 번째 단계가 된다.

2. 반복적 업데이트 (Iterative Updates): 모든 간선을 확인하며, 각 간선을 따라 거리 값을 업데이트한다.

  • 업데이트 횟수 (Number of Updates):

    • 정점의 수(V)가 5라면, V − 1 = 4번 반복.

    • 이유: 정점 간 최단 경로는 최대 V−1개의 간선을 거칠 수 있기 때문이다.

  • 업데이트 과정:

    • 첫 번째 라운드: 시작점(0)과 연결된 2, 3번 노드의 비용이 갱신된다.

    • 두 번째 라운드: 4,5 번 노드와 연결된 노드들의 비용이 갱신된다.

    • 이렇게 순차적으로 모든 간선을 탐색하며, 최단 거리 리스트를 갱신한다.

3. 음수 사이클 탐지 (Negative Cycle Detection):

  • 음수 사이클 (Negative Cycle): 특정 경로를 반복해서 탐색할 때, 비용이 계속 줄어드는 경우

  • 탐지 방법:

    • V−1번 반복 후, 한 번 더 모든 간선을 탐색한다.

    • 만약 추가 업데이트가 발생하면, 음수 사이클이 존재한다는 뜻이다.

    • 따라서 아래와 같이 결과를 출력한다.

      • "음수 사이클 존재 (Negative Cycle Exists)"

벨만-포드 알고리즘 #4: 파이썬 코드 (Bellman-Ford Algorithm Python Code Example)

1. 데이터 초기화 (Initialize Data):

  • 노드(N)와 간선(M) 읽기: 그래프의 노드 개수 N과 간선 개수 M을 입력받는다.

      N, M = map(int, input().split())

  • 간선 리스트와 거리 리스트 선언 (Edge List and Distance Array):

      edges = []  
  distance = [sys.maxsize] * (N + 1)

    • edges: 간선 정보를 저장하는 리스트.

    • distance: 각 노드까지의 최단 거리를 저장하는 리스트.

      • sys.maxsize로 초기화하여 무한대 값을 나타낸다.

  • 엣지 데이터 입력받기 (Store Edge Data):

      for _ in range(M):  
      start, end, time = map(int, input().split())  
      edges.append((start, end, time))

    각 간선의 출발 노드, 도착 노드, 가중치를 입력받아 edges 리스트에 저장한다.

3. 음수 사이클 여부 확인 (Negative Cycle Detection):

pythonCopy codemCycle = False  
for start, end, time in edges:  
    if distance[start] != sys.maxsize and distance[end] > distance[start] + time:  
        mCycle = True

반복 이후에도 값이 더 작아지면 음수 사이클(Negative Cycle)이 존재한다는 뜻이다.

4. 결과 출력 (Output Results):

if not mCycle:  
    for i in range(2, N + 1):  
        if distance[i] != sys.maxsize:  
            print(distance[i])  
        else:  
            print(-1)  
else:  
    print(-1)

  • 음수 사이클이 없으면, 각 노드까지의 최단 거리를 출력한다.

  • 음수 사이클이 있으면, -1을 출력한다.

5️⃣모든 쌍 최단 경로(All-Pairs Shortest Path)

✅ 모든 쌍 최단 경로 소개 (All-Pairs Shortest Path):

  • 이전에는 단일 시작점 최단 경로 (Single-Source Shortest Path)를 배웠다. 단일 시작점 최단 경로란 특정 시작점에서 다른 모든 노드까지의 최단 경로를 구하는 방법이다.

  • 이제는 모든 쌍 (All-Pairs)을 대상으로 하는 경로이다.

    • 그래프에 있는 모든 노드 쌍 간의 최단 경로를 계산한다.

    • 예: A → B, A → C, B → C 등 모든 경로

  • 언제 사용하나요? (When to Use):

    • 네비게이션 (Navigation): 도시 간의 최단 경로를 구하는 경우.

    • 네트워크 통신 (Network Communication): 데이터가 여러 서버 간에 전송될 때 가장 빠른 경로를 계산하는 경우

  • 특징 (Key Characteristics):

    • 이 알고리즘은 모든 노드 쌍 간의 최단 경로를 구하므로 계산량이 많다.

    • 복잡도가 높다 (High Complexity): 계산량이 커서 시간 소모가 크다.

✅ 대표 알고리즘 (Representative Algorithm):

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

    • 모든 쌍 간의 최단 경로를 구하는 대표적인 알고리즘이다.

    • 동적 프로그래밍 (Dynamic Programming) 방식을 사용한다.

    • 그래프에 음수 가중치가 있어도 동작 가능하지만, 음수 사이클은 허용되지 않는다.

모든 쌍 최단 경로 #1: 동적 프로그래밍 적용(Dynamic Programming for All-Pairs Shortest Path)

✅ 동적 프로그래밍 (Dynamic Programming) 적용:

즉, 경로를 점진적으로 늘려가며 계산한다.

  • 최소 간선부터 시작해서 처음에는 노드 간의 직접 연결된 거리만 확인한다. m=1

  • m > 1일 때, 추가 경로를 통해 더 짧아질 수 있는지를 확인한다.

  • m = 1: 노드 vi 와 vj 간의 직접 거리.

  • m > 1: 중간 노드 k를 통해 vi → k 로 이동할 때 거리

모든 쌍 최단 경로 #2: 단순 최단 경로 알고리즘(Simple Shortest Path Algorithm)

💡요약 (Summary)

  1. 목표: 모든 정점 쌍 간의 최단 경로 계산.

  2. 방법: 모든 정점에서 경로를 확장하면서 거리 비용을 업데이트.

  3. 문제: 시간 복잡도가 O(n4)로 비효율적.

  4. 개선: 플로이드-워샬 알고리즘으로 최적화.

✅ 단순 최단 경로 알고리즘:

  • 그래프에서 모든 정점 쌍 간의 최단 경로를 계산한다.

  • 경로를 점진적으로 확장하면서 최단 거리 비용을 업데이트한다.

✅동작 과정 (How It Works):

  1. 초기화 (Initialization):

    • 모든 정점 쌍의 가중치를 초기화한다. (dij = wij)

    • 직접 연결된 거리를 사용하거나 연결이 없는 경우 무한대 (∞)로 설정한다.

  2. 모든 정점 탐색 (All Nodes Exploration):

    • 정점 k를 하나씩 추가하면서 i → k → j 로 이동하는 경로를 확인한다.

    • 기존 거리 dij 와 dik + wkj​를 비교하여 더 짧은 값을 업데이트한다.

  3. 점화식 (Recurrence Formula):

    • dij: 정점 i에서 j로 가는 최단 거리.

    • k: 중간에 추가된 노드

✅ 문제점 및 개선 방법:

  • 단점 (Drawbacks): 성능이 느림 (Slow Performance)

    • 이중 루프와 중첩된 계산으로 인해 시간 복잡도가 O(n4)로 매우 비효율적이다.

  • 개선 방법 (Optimized Approach): 플로이드-워샬 알고리즘 (Floyd-Warshall Algorithm)

    • 중간 정점 집합을 활용하여 계산을 최적화하고 수행 시간을 단축할 수있다.

모든 쌍 최단 경로 #2: 플로이드-워샬 알고리즘의 동적 프로그래밍 적용 (Floyd-Warshall Algorithm with Dynamic Programming)

플로이드-워샬 알고리즘은 그래프의 모든 정점 쌍 간 최단 경로를 효율적으로 계산하는 알고리즘이다.

✅ 목적 (Goal): 모든 정점 vi에서 vj로 가는 최단 경로를 찾는 것.

✅ 특징 (Feature): 이전 단계에서 계산한 최단 거리 값을 재활용하여 시간 복잡도를 줄인다.

✅DP 테이블 정의 (DP Table Definition)

    • n개의 간선이 아닌 vertex set을 명확하게 지정한다. 정점 집합 {v1,v2,⋯ ,vk}만 거쳐 vi에서 vj로 가는 최단 거리이다.

      • 초기값으로 직접 연결된 거리 wij를 사용하거나 연결이 없으면 무한대 (∞)로 설정한다.

✅점화식 (Recurrence Formula):

  • 기본 경우 (Base Case): k = 1 일 때

  • 일반 경우 (General Case): k ≥ 1 일 때

    • 해석 (Interpretation):

      • dijk−1​: vk ​를 거치지 않고 vi ​에서 vj ​로 가는 최단 거리.

      • dikk−1 + dkjk−1 : vk를 거쳐가는 경로의 거리.

      • 이 둘 중 더 짧은 값을 선택한다.

  • 정점 집합 활용 (Vertex Set Utilization):

    • 정점 집합을 점진적으로 확장하며 최단 거리를 업데이트한다.

    • 불필요한 계산을 줄여 효율성을 높일 수 있다.

✅주요 특징 및 장점:

  • 효율성 향상 (Improved Efficiency): 이전의 단순 알고리즘보다 O(n4)에서 n³ 로 시간 복잡도로 최적화되었다.

  • 재활용 (Reusability): 이전 단계에서 계산된 거리 값을 활용하여 중복 계산을 줄인다.

모든 쌍 최단 경로 #3: 플로이드-워샬 알고리즘의 점화식 이해 (Understanding the Recurrence Formula in Floyd-Warshall Algorithm)

핵심 아이디어: 플로이드-워샬 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾기 위해 점화식을 사용할 수 있다. 특정 정점 k를 경유할 때와 경유하지 않을 때의 최단 거리를 비교하여 더 짧은 값을 선택한다.

✅ 점화식 해석:

  1. 기존 경로 ( i ➡️ j )

    • i에서 j까지 k를 경유하지 않은 상태에서의 최단 거리이다.

  2. 경유 경로 ( i ➡️ k ➡️ j)

    • i에서 k를 거쳐 j로 가는 경로의 거리이다.

    • 이 경로는 k−1 단계까지의 계산된 최단 거리를 사용한다.

  3. 최종 선택:

    • k를 경유하지 않는 기존 경로와 k를 경유하는 새로운 경로를 비교한다.

    • 위 두 값 중 더 작은 값을 선택하여 최단 거리를 업데이트하게 된다.

    • O(n3)로 효율적이다.

All-Pairs Shortest Path #3: 플로이드-워샬 알고리즘의 의사코드 (Understanding the Pseudocode in Floyd-Warshall Algorithm)

✅알고리즘 구조 설명

  1. 초기화 (Initialization):

    • 그래프의 각 간선 가중치를 초기 거리 값으로 설정한다. dij = wij

    • 정점 i와 j가 직접 연결되어 있지 않은 경우, 초기값을 무한대로 설정한다. ∞

    • 간선(Edge) : 노드와 노드를 연결하는 선

  2. 중간 정점 추가 (Adding Intermediate Vertices):

    • 정점(Vertex) : 각 노드를 뜻한다.

  • 바깥쪽 for문 (k): 중간에 포함할 정점의 범위를 1에서 n−1지 확장한다. for k ← 1 to n-1

  • 중간 for문 (i): 모든 시작 정점 i를 확인한다.

  • 안쪽 for문 (j): 시작 정점 i에서 도착 정점 j로 가는 최단 거리를 점화식으로 업데이트한다.

  1. 점화식 (Recurrence Formula):

    • k를 포함하지 않은 경로와 k를 포함한 경로의 거리를 비교한다.

    • 작은 값을 선택하여 최단 경로를 갱신한다.

  2. 결과: 알고리즘이 종료되면, dij에는 i에서 j까지의 최단 경로가 저장된다.

All-Pairs Shortest Path #4: 플로이드-워샬 알고리즘의 자료구조 순 (Floyd-Warshall Data Structure Example)

1️⃣ 초기화 (Initialization)

  • 우선 그래프의 각 노드 쌍에 대해 최단 거리 리스트를 초기화한다.

  • 자기 자신으로 가는 거리는 0으로 설정하고, 나머지 경로는 무한대(∞)로 설정한다.

2️⃣그래프 데이터 저장 (Store Graph Data)

  • 초기 리스트는 가중치로 초기화 된다. 그래프의 경로 정보를 리스트에 저장한다.

  • 예를 들어, 1에서 2로 가는 경로의 가중치가 8이라면 D[1][2] = 8로 설정한다.

  • D[2][4] = -4에서 볼 수 있듯이 음수 가중치도 처리할 수 있는 장점이 있다.

3️⃣점화식 업데이트 (Update with Recurrence Relation)

  • 모든 경로를 탐색하며, 중간 노드(K)를 거쳤을 때 더 짧은 경로가 있는지 확인한다.

  • 점화식: D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

  • 이 과정에서 D[S][E]와 D[S][K] + D[K][E] 중에서 더 작은 값을 리스트를 업데이트한다.

4️⃣결과 출력 (Output the Final List)

  • 모든 경로를 반복적으로 탐색한 후, 최종적으로 완성된 최단 거리 리스트를 출력한다.

  • 이 리스트는 각 노드 쌍 간의 최단 거리를 포함한다.

💡중요한 부분과 요약본

  • 플로이드-워샬은 모든 정점 쌍의 최단 거리를 구한다. (Floyd-Warshall calculates the shortest path between all pairs of nodes.)

  • 초기화, 그래프 저장, 점화식 업데이트, 최종 결과 출력 순으로 진행한다. (It proceeds in the order of initialization, storing graph data, updating with a recurrence relation, and printing the final result.)

  • 점화식을 이용해 더 짧은 경로를 반복적으로 갱신한다. (Uses a recurrence relation to iteratively update to shorter paths.)

  • 음수 가중치를 허용하지만, 음수 사이클은 처리할 수 없다.

All-Pairs Shortest Path #5: 플로이드-워샬 알고리즘의 파이썬 코드 (Floyd-Warshall Algorithm in Python)

💡정리: 첫 번째 이미지는 그래프의 최단 거리를 초기화하고, 플로이드-워샬 알고리즘의 핵심 반복문인 for 루프를 통해 완화 과정을 구현한다. 두 번째 이미지는 최종 결과를 출력하는 부분으로, 각 정점 쌍의 최단 거리를 행렬 형태로 보여주고 있다.

  • 초기화 (Initialization)

    • 각 정점에서 자기 자신으로 가는 거리 (distance[i][i])는 0으로 설정한다.

    • 두 정점 사이에 간선이 있으면 그 가중치로 초기화한다. 만약 간선이 없으면 초기 값으로 무한대 (infinity)를 설정한다.

    • 간선(Edge) : 노드와 노드를 연결하는 선

    • 정점(Vertex) : 각 노드를 뜻한다.

  • 반복문을 통한 완화 (Relaxation through Loops):

    • 세 개의 for 루프를 사용한다:

      • 가장 바깥쪽 루프는 중간 경유지 (k)를 반복한다.

      • 그 안쪽 두 개의 루프는 출발 정점 (i)과 도착 정점 (j)의 쌍을 반복한다.

    • 점화식 (distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]))을 통해, 현재 계산된 최단 거리와 경유지를 거쳤을 때의 거리를 비교해 더 작은 값으로 업데이트한다.

결과 출력 (Output):

  • 모든 정점 쌍에 대해 최단 거리 행렬을 출력한다.

  • 만약 두 정점 간 경로가 존재하지 않으면 0으로 출력하게 된다.

6️⃣강연결 요소 구하기 (Finding Strongly Connected Components, SCC)

강연결 요소 구하기(Finding Strongly Connected Components)는 그래프 이론과 알고리즘에서 매우 중요한 개념이다. 방향 그래프에서 강하게 연결된 요소는 같은 부분 집합 내의 모든 정점이 해당 집합의 다른 모든 정점으로 방향 간선을 따라 도달할 수 있는 정점들의 부분 집합을 의미한다. 그래프의 SCC를 찾는 것은 그래프의 구조와 연결성을 이해하는 데 중요한 통찰력을 제공하며, 이는 소셜 네트워크 분석, 웹 크롤링, 네트워크 라우팅 등 다양한 분야에 응용될 수 있다. 또한 이 알고리즘은 Kosaraju's Algorithm의 핵심 아이디어를 따른다.

강연결 요소 (Strongly Connected Components, SCC)는 유향 그래프에서 특정 조건을 만족하는 노드들의 집합이다.

✅ 조건: 강하게 연결된 부분 그래프란, 그래프의 모든 정점 쌍에 대해 양방향으로 이동할 수 있는 경로가 존재하는 경우를 의미한다.

  • 예를 들어) A → B로 가는 경로가 있고, 동시에 B → A로 가는 경로도 존재한다면, A와 B는 강하게 연결되어 있다고 한다.

✅ SCC 찾기의 목표: 그래프를 강연결 요소들로 나누어 각 요소의 경로 특성을 분석한다.

✅ 시간 복잡도: 이 알고리즘은 DFS를 두 번 사용하며, 수행 시간 복잡도는 O(V+E)로 매우 효율적이다.

  • 첫 번째 그래프:

    • 노드 11, 12, 13이 서로 강하게 연결(Strongly connected)되어 있다.

    • 예) 11에서 12로 가는 경로와 12에서 11로 가는 경로가 존재하기 때문에 양방향 연결이 가능하다다.

  • 두 번째 그래프:

    • 전체 그래프는 여러 강연결 요소로 나뉜다.

    • 단일 노드의 SCC: 노드 9와 10은 다른 노드들과 강하게 연결되지 않아 독립적인 요소를 형성한다.

    • 강하게 연결된 서브그래프:

    • 노드 6, 7, 8은 서로 강하게 연결되어 하나의 요소를 만든다.

강연결 요소 구하기 #1: 의사코드 (Pseudocode in Finding Strongly Connected Components, SCC)

  1. 그래프 탐색 (DFS 수행):

    • 그래프 G에서 DFS(깊이 우선 탐색)를 수행한다.

    • 각 정점 v의 완료시간 f[v]를 계산한다.

      • f[v]: DFS 탐색 중 정점 v에서 더 이상 갈 곳이 없을 때 기록되는 시간

      • 이 완료시간은 이후 역방향 그래프에서 탐색 순서를 결정하는 데 중요하다.

      • 간선(Edge) : 노드와 노드를 연결하는 선

      • 정점(Vertex) : 각 노드를 뜻한다.

  2. 역방향 그래프 생성 (Reverse the Graph):

    • 그래프 G의 모든 간선 방향을 뒤집어 새로운 그래프 Gr를 만든다.

    • Gr: G의 모든 간선이 반대로 연결된 그래프.

  3. 다시 탐색 시작 (DFS on Gr):

    • Gr에서 다시 DFS를 수행한다.

    • 이번에는 완료시간 f[v]가 가장 큰 정점부터 탐색을 시작한다.

      • 완료시간이 크다는 것은 G에서 가장 나중에 종료된 정점임을 의미한다.

  4. 강연결 요소 반환 (Return SCCs):

    • Gr에서 탐색을 통해 분리된 트리(서브그래프)를 구한다.

    • 각 트리는 하나의 강연결 요소 (SCC)가 된다.

💡 중요한 점 요약 (Key Points Summary)

  1. DFS 완료시간 (Finish Time): DFS 수행 중 완료된 순서를 기준으로 역방향 탐색을 시작한다.

  2. 역방향 그래프 (Reverse Graph): 원래 그래프의 간선을 반대로 뒤집어 새로운 그래프를 생성한다.

  3. DFS 재탐색: 완료시간 f[v]이 큰 정점부터 탐색을 시작하여 SCC를 구한다.

  4. 결과: 분리된 트리 형태로 강연결 요소들이 반환된다.

강연결 요소 구하기 #2: 작동 과정 (Components Process in Finding Strongly Connected Components, SCC)

1️⃣ DFS 수행

그래프 G에서 각 정점에 대해 깊이 우선 탐색(DFS, Depth First Search) 을 수행한다.

  • DFS를 통해 각 정점의 완료 시간 f[v]을 기록한다.

  • 완료된 순서가 1 → 2 → 3 → ... 순으로 설정된다.

2️⃣ 간선 방향 뒤집기

  • 그래프의 모든 간선 방향을 뒤집어 역 그래프(G^R) 를 만든다.

  • G^R는 G의 모든 연결 방향을 반대로 한 것이다.

3️⃣강연결요소 구하기

  • GR에서 f[v] 값이 가장 큰 정점부터 시작해 DFS를 다시 수행한다.

  • 한 번의 DFS 탐색으로 묶인 노드들이 하나의 강연결요소(SCC) 를 형성한다.

  • 이 과정을 모든 정점이 방문될 때까지 반복한다.

4️⃣ 결과 출력

  • G^R에서 DFS로 묶인 각 부분 집합이 강연결요소이다.

  • 위 이미지에서 강연결요소는 서로 다른 색으로 구분된다.

7️⃣ A* 알고리즘 (A* Search Algorithm)

💡요약: A* 탐색 알고리즘은 경로 탐색 및 그래프 순회에서 가장 우수하고 널리 사용되는 기술 중 하나이다. 왜 A 탐색 알고리즘을 사용하는가?라고 묻는다면 A* 탐색 알고리즘은 다른 순회 기법과는 달리 "뇌(brains)"를 가지고 있다. 이는 정말로 똑똑한 알고리즘이라는 의미이며, 이를 통해 다른 전통적인 알고리즘과 차별화된다. 또한 많은 게임과 웹 기반 지도에서 이 알고리즘을 사용하여 매우 효율적으로(근사값으로) 최단 경로를 찾게 된다.

✅ 최단경로 문제의 복잡성

  • 최단경로 구하는 문제는 매우 복잡한 문제로 최적화를 짧은시간에 구하는것은 어렵다.

  • 최단경로를 찾는 문제는 계산량이 매우 많고, 시간이 오래 걸리는 알고리즘이다.

  • 예를 들어, 벨만-포드나 플로이드-워셜 알고리즘은 여러 중첩된 for문으로 구성되어 있으며, 수행 시간이 길어질 수 있다.

✅ A 알고리즘의 접근 방식

  • 네비를 따라 운전하다 보면 좀 이상하다?싶을 때가 있을 것 이다. 특히 이상한 길을 안내할 때 더욱 그렇다. 이렇게 최단 경로를 구하는 것은 매우 어렵기때문에 A* 알고리즘은 정확한 최단경로를 찾는 대신, 효율성을 높이기 위해 근사값(Heuristic) 을 사용한다.

  • 특정 정점에서 목표 정점까지의 비용을 예측하는 함수 h(x)를 활용한다.

  • 이 값은 목표에 "얼마나 가까운가"를 추정하며, 정확하지는 않지만 경로 탐색을 더 효율적으로 만든다.

✅ 활용 예시

  • 네비게이션 시스템에서 최적의 경로를 찾을 때 자주 사용된다.

  • 예를 들어, 도로 상태, 거리, 예상 시간 등을 고려하여 실제 최적의 길을 안내할 때이다.

  • 하지만 휴리스틱 함수 h(x)가 부정확하면, 예상치 못한 "이상한 경로"를 안내할 수도 있다.

💡 중요한 부분 (Key Points)

  • 휴리스틱 함수 h(x): 목표 정점까지의 비용을 추정하며, 탐색의 효율성을 높이는 핵심.

  • A 알고리즘의 장점: 정확한 비용 계산 없이도 최적 경로에 가까운 결과를 빠르게 제공한다.

  • 단점: h(x)가 부정확하거나 잘못 정의되면 최적 경로를 보장하지 못한다.

A* 알고리즘 #1: 자세한 설명 (Detailed Explanation of the A * Search Algorithm)

💡요약: 네비게이션 시스템은 A* 알고리즘을 활용해 최단경로를 탐색한다.

  • 최단 거리를 기준으로 한다면: h(n)은 "직선 거리"를 기준으로 계산된다.

  • 최단 시간을 기준으로 한다면: h(n)은 "예상 시간"을 기준으로 계산된다. 이처럼 h(n)의 정의가 달라지면 결과도 달라질 수 있다.

A* 알고리즘은 이 두 정보를 결합해, 최단 경로를 찾으면서도 효율적으로 계산하려는 시도이다.

✅ 평가 함수 f(n)

  • A* 알고리즘은 평가 함수 f(n) = g(n) + h(n)을 사용한다.

  • g(n): 출발점에서 정점 n까지의 실제 경로 비용

    • 예: 지금까지 이동한 거리나 시간.

  • h(n): 정점 n에서 도착점까지의 추정 경로 비용

    • 정확한 값이 아닌, 도착점까지 얼마나 가까운지 "예상"하는 값입니다.

    • h(n)은 알고리즘의 성능을 좌우하는 중요한 요소이다.

✅ 작동 과정

  • f(n) 값을 기준으로 가장 비용이 적은 정점을 선택해 탐색을 진행한다.

  • 탐색은 다음 두 가지 정보를 기반으로 진행된다.

    • 지금까지 이동한 거리 g(n)

    • 앞으로 남은 예상 거리 h(n)

  • 최적 경로는 f(n) 값을 최소화하는 경로를 찾는 것이다.

✅ h(n)의 역할

  • h(n)이 정확 할수록 탐색이 효율적이고 빨라진다.

  • 반대로, h(n)이 부정확하면 잘못된 경로로 탐색하거나 효율이 떨어질 수 있다.

  • 예를 들어, 네비게이션 시스템의 A* 알고리즘은 도로 거리나 예상 시간을 h(n)으로 사용한다.

✅ 예시: 네비게이션의 차이점

  • 네비게이션 앱 간의 길 안내가 다른 이유는 h(n)을 정의하는 방식이 다르기 때문이다.

    • 어떤 앱은 최단 거리를 기준으로 하고,

    • 다른 앱은 최단 시간을 기준으로 h(n)을 정의하기 때문이다.

  • 도로 상황, 교통량, 속도 제한 등을 반영하는 방식이 달라 알고리즘 결과가 조금씩 차이가 나게 된다.

✅ 장점과 단점

  • 장점: 실제 경로 비용과 예상 비용을 함께 고려해 더 효율적이고 현실적인 탐색이 가능하다.

  • 단점: h(n)을 설계하는 것이 까다롭고, 정확도에 따라 성능이 달라지게 된다. 경우에 따라 시간 복잡도가 높아질 수 있다.

A* 알고리즘 #2: 의사코드 (Pseudo-code of A Algorithm)

  1. 초기화 (Initialization)

    • 시작 노드의 비용 g(start_node)+h(start_node)를 계산하여 우선순위 큐 (priority queue)에 삽입한다.

      • 우선순위 큐는 비용이 가장 작은 노드부터 처리하도록 정렬된 데이터 구조이다. 시작점에서 출발하여 탐색을 시작한다.

  2. 탐색 반복 (While loop)

    • 우선순위 큐가 비어 있지 않은 동안 반복한다.

      1. 큐에서 가장 작은 비용의 노드를 꺼낸다. (node=pq.dequeue)

      2. 현재 노드가 목표 노드인지 확인한다.

        • 목표 노드라면 탐색을 종료한다.

      3. 목표 노드가 아니라면 현재 노드에서 이동 가능한 다음 노드들을 확인한다.

  3. 다음 노드 탐색 (Exploring Next Nodes)

    • for 루프를 사용해 현재 노드에서 이동 가능한 모든 이웃 노드를 확인한다.

      1. 각 이웃 노드의 비용을 계산합니다:

        • f(next_node)=g(node)+cost+h(next_node)

        • cost: 현재 노드에서 이웃 노드로 이동하는 비용.

        • h(next_node): 이웃 노드에서 목표 노드까지의 예상 비용 (휴리스틱).

      2. 계산된 비용을 우선순위 큐에 삽입한다 pq.enqueue(...)

    • 이 과정을 반복하며 비용이 낮은 경로를 따라 탐색한다.

  4. 목표 도달 후 종료 (Termination)

    • 목표 노드에 도달하면, 해당 경로의 총 비용을 출력하고 알고리즘을 종료하게 된다.

💡 주요 코드 설명 (Key Steps)

  • 우선순위 큐 (Priority Queue): 비용이 가장 낮은 노드를 우선적으로 처리해 탐색 효율성을 높인다.

  • 평가 함수: f(n)=g(n)+h(n)을 결합해 최적의 노드를 선택한다.

  • 휴리스틱 h(n): 도착점까지의 예상 비용으로, 정확도가 높을수록 알고리즘 성능이 개선된다.

Computer Algorithms

Part 3 of 19

Through this subjects, I will be learning how to think systematically through algorithms and develop problem-solving skills. Also, I'm hoping to learn how to perform programming quickly and efficiently by applying computer algorithms.

Up next

Graph Algorithms: BFS, DFS, Spanning Tree (Prim's and Kruskal's Algorithms)

Contents 1️⃣그래프의 개요(Overview of Graph)2️⃣그래프의 유형 (Type of Graph)3️⃣그래프의 표현 (Graph Representation)4️⃣너비 우선 탐색 (Breadth First Search)5️⃣깊이 우선 탐색 (Depth First Search)6️⃣최소 신장 트리(Shortest Spanning Tree) 1️⃣그래프의 개요(Overview of Graph) 💡요약: 그래프(Graph)는 개...

More from this blog

My dev journey

125 posts