μ΅λ¨ κ²½λ‘ (Shortest Path)
μ΅λ¨ κ²½λ‘ (Shortest Path)¶
κ°μ¶
κ°μ€μΉκ° μλ κ·Έλνμμ λ μ μ μ¬μ΄μ μ΅λ¨ κ²½λ‘λ₯Ό μ°Ύλ μκ³ λ¦¬μ¦μ νμ΅ν©λλ€. Dijkstra, Bellman-Ford, Floyd-Warshall μκ³ λ¦¬μ¦μ λ€λ£Ήλλ€.
λͺ©μ°¨¶
- μ΅λ¨ κ²½λ‘ μκ³ λ¦¬μ¦ λΉκ΅
- λ€μ΅μ€νΈλΌ (Dijkstra)
- 벨λ§-ν¬λ (Bellman-Ford)
- νλ‘μ΄λ-μμ (Floyd-Warshall)
- 0-1 BFS
- μ°μ΅ λ¬Έμ
1. μ΅λ¨ κ²½λ‘ μκ³ λ¦¬μ¦ λΉκ΅¶
βββββββββββββββββββ¬ββββββββββββββ¬ββββββββββββββββ¬ββββββββββββββββββ
β μκ³ λ¦¬μ¦ β μκ° λ³΅μ‘λ β μμ κ°μ€μΉ β μ©λ β
βββββββββββββββββββΌββββββββββββββΌββββββββββββββββΌββββββββββββββββββ€
β BFS β O(V+E) β β β κ°μ€μΉ μμ β
β Dijkstra β O(E log V) β β β λ¨μΌ μΆλ°μ β
β Bellman-Ford β O(VE) β β β λ¨μΌ μΆλ°μ β
β Floyd-Warshall β O(VΒ³) β β β λͺ¨λ μ β
β 0-1 BFS β O(V+E) β 0,1λ§ β 0/1 κ°μ€μΉ β
βββββββββββββββββββ΄ββββββββββββββ΄ββββββββββββββββ΄ββββββββββββββββββ
2. λ€μ΅μ€νΈλΌ (Dijkstra)¶
κ°λ ¶
λ¨μΌ μΆλ°μ μμ λͺ¨λ μ μ κΉμ§μ μ΅λ¨ 거리
쑰건: μμ κ°μ€μΉ μμ
μ리:
1. μμμ 거리 = 0, λλ¨Έμ§ = β
2. λ°©λ¬Ένμ§ μμ μ μ μ€ μ΅λ¨ 거리 μ μ μ ν
3. ν΄λΉ μ μ μ ν΅ν΄ μΈμ μ μ 거리 κ°±μ
4. λͺ¨λ μ μ λ°©λ¬Έν λκΉμ§ λ°λ³΅
λμ μμ¶
(B)
/ 1 \
4 2
/ \
(A) (D)
\ /
2 1
\ 3 /
(C)
μμ: A
λ¨κ³ λ°©λ¬Έ dist[A] dist[B] dist[C] dist[D]
---- ----- ------ ------ ------ ------
0 {} 0 β β β
1 {A} 0 4 2 β β A λ°©λ¬Έ, B,C κ°±μ
2 {A,C} 0 4 2 5 β C λ°©λ¬Έ, D κ°±μ (2+3)
3 {A,C,B} 0 4 2 5 β B λ°©λ¬Έ
4 {all} 0 4 2 5 β D λ°©λ¬Έ
κ²°κ³Ό: AβB: 4, AβC: 2, AβD: 5
ꡬν (μ°μ μμ ν)¶
// C - μΈμ 리μ€νΈ + λ°°μ΄ (κ°λ¨ν λ²μ )
#define INF 1000000000
#define MAX_V 10001
typedef struct {
int to, weight;
} Edge;
Edge adj[MAX_V][MAX_V];
int adjSize[MAX_V];
int dist[MAX_V];
int visited[MAX_V];
int V, E;
void dijkstra(int start) {
for (int i = 0; i < V; i++) {
dist[i] = INF;
visited[i] = 0;
}
dist[start] = 0;
for (int i = 0; i < V; i++) {
// μ΅μ 거리 μ μ μ°ΎκΈ°
int u = -1;
int minDist = INF;
for (int j = 0; j < V; j++) {
if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}
if (u == -1) break;
visited[u] = 1;
// μΈμ μ μ κ°±μ
for (int j = 0; j < adjSize[u]; j++) {
int v = adj[u][j].to;
int w = adj[u][j].weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
}
// C++ - μ°μ μμ ν μ¬μ© (ν¨μ¨μ )
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> pii; // {거리, μ μ }
vector<int> dijkstra(const vector<vector<pii>>& adj, int start) {
int V = adj.size();
vector<int> dist(V, INT_MAX);
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
// μ΄λ―Έ μ²λ¦¬λ μ μ μ΄λ©΄ μ€ν΅
if (d > dist[u]) continue;
for (auto [v, weight] : adj[u]) {
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
return dist;
}
// μ¬μ© μ
// adj[u].push_back({v, weight}); // u β v, κ°μ€μΉ weight
// auto dist = dijkstra(adj, 0);
# Python
import heapq
from collections import defaultdict
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
pq = [(0, start)] # (거리, μ μ )
while pq:
d, u = heapq.heappop(pq)
# μ΄λ―Έ μ²λ¦¬λ μ μ μ΄λ©΄ μ€ν΅
if d > dist[u]:
continue
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(pq, (dist[v], v))
return dist
# μ¬μ© μ
# graph = defaultdict(list)
# graph[0].append((1, 4)) # 0 β 1, κ°μ€μΉ 4
# graph[0].append((2, 2)) # 0 β 2, κ°μ€μΉ 2
# dist = dijkstra(graph, 0)
κ²½λ‘ λ³΅μ¶
// C++
pair<vector<int>, vector<int>> dijkstraWithPath(
const vector<vector<pii>>& adj, int start) {
int V = adj.size();
vector<int> dist(V, INT_MAX);
vector<int> parent(V, -1);
priority_queue<pii, vector<pii>, greater<pii>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue;
for (auto [v, weight] : adj[u]) {
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
parent[v] = u; // κ²½λ‘ μ μ₯
pq.push({dist[v], v});
}
}
}
return {dist, parent};
}
// κ²½λ‘ μΆλ ₯
vector<int> getPath(const vector<int>& parent, int end) {
vector<int> path;
for (int v = end; v != -1; v = parent[v]) {
path.push_back(v);
}
reverse(path.begin(), path.end());
return path;
}
# Python
def dijkstra_with_path(graph, start):
dist = {node: float('inf') for node in graph}
parent = {node: None for node in graph}
dist[start] = 0
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
parent[v] = u
heapq.heappush(pq, (dist[v], v))
return dist, parent
def get_path(parent, end):
path = []
v = end
while v is not None:
path.append(v)
v = parent[v]
return path[::-1]
3. 벨λ§-ν¬λ (Bellman-Ford)¶
κ°λ ¶
λ¨μΌ μΆλ°μ μμ λͺ¨λ μ μ κΉμ§μ μ΅λ¨ 거리
νΉμ§: μμ κ°μ€μΉ νμ©, μμ μ¬μ΄ν΄ νμ§ κ°λ₯
μ리:
1. μμμ 거리 = 0, λλ¨Έμ§ = β
2. λͺ¨λ κ°μ μ λν΄ κ±°λ¦¬ κ°±μ (V-1ν λ°λ³΅)
3. Vλ²μ§Έ λ°λ³΅μμ κ°±μ λλ©΄ μμ μ¬μ΄ν΄ μ‘΄μ¬
λμ μμ¶
(B)
/ 1 \
4 2
/ \
(A) (D)
\ /
2 -5 β μμ κ°μ€μΉ
\ 3 /
(C)
κ°μ : (A,B,4), (A,C,2), (B,D,2), (C,B,1), (C,D,3)
λ°λ³΅ 1: dist = [0, 4, 2, 5]
λ°λ³΅ 2: dist = [0, 3, 2, 5] β CβBλ‘ B κ°±μ (2+1=3)
λ°λ³΅ 3: dist = [0, 3, 2, 5] β λ³ν μμ
κ²°κ³Ό: AβB: 3, AβC: 2, AβD: 5
ꡬν¶
// C
#define INF 1000000000
typedef struct {
int from, to, weight;
} Edge;
Edge edges[20001];
int dist[501];
int V, E;
int bellmanFord(int start) {
for (int i = 0; i < V; i++) {
dist[i] = INF;
}
dist[start] = 0;
// V-1λ² λ°λ³΅
for (int i = 0; i < V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = edges[j].from;
int v = edges[j].to;
int w = edges[j].weight;
if (dist[u] != INF && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// μμ μ¬μ΄ν΄ νμΈ
for (int j = 0; j < E; j++) {
int u = edges[j].from;
int v = edges[j].to;
int w = edges[j].weight;
if (dist[u] != INF && dist[u] + w < dist[v]) {
return -1; // μμ μ¬μ΄ν΄ μ‘΄μ¬
}
}
return 0;
}
// C++
struct Edge {
int from, to, weight;
};
vector<int> bellmanFord(int V, const vector<Edge>& edges, int start) {
vector<int> dist(V, INT_MAX);
dist[start] = 0;
// V-1λ² λ°λ³΅
for (int i = 0; i < V - 1; i++) {
for (const auto& e : edges) {
if (dist[e.from] != INT_MAX &&
dist[e.from] + e.weight < dist[e.to]) {
dist[e.to] = dist[e.from] + e.weight;
}
}
}
// μμ μ¬μ΄ν΄ νμΈ
for (const auto& e : edges) {
if (dist[e.from] != INT_MAX &&
dist[e.from] + e.weight < dist[e.to]) {
return {}; // μμ μ¬μ΄ν΄
}
}
return dist;
}
# Python
def bellman_ford(V, edges, start):
dist = [float('inf')] * V
dist[start] = 0
# V-1λ² λ°λ³΅
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# μμ μ¬μ΄ν΄ νμΈ
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # μμ μ¬μ΄ν΄
return dist
4. νλ‘μ΄λ-μμ (Floyd-Warshall)¶
κ°λ ¶
λͺ¨λ μ μ μ μ¬μ΄μ μ΅λ¨ 거리
νΉμ§: μμ κ°μ€μΉ νμ©, DP κΈ°λ°
μ리:
kλ₯Ό κ²½μ νλ κ²½λ‘ vs μ§μ κ²½λ‘
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
λͺ¨λ kμ λν΄ λ°λ³΅
λμ μμ¶
1 2
(0) ββ (1) ββ (2)
βββββββ3βββββββ
μ΄κΈ°:
0 1 2
0 [ 0, 1, 3]
1 [INF, 0, 2]
2 [INF, INF, 0]
k=1 (1μ κ²½μ ):
dist[0][2] = min(3, dist[0][1]+dist[1][2])
= min(3, 1+2) = 3
κ²°κ³Ό: 0β2 μ΅λ¨κ±°λ¦¬ = 3
ꡬν¶
// C
#define INF 1000000000
#define MAX_V 500
int dist[MAX_V][MAX_V];
int V;
void floydWarshall() {
// kλ₯Ό κ²½μ μ μΌλ‘
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] != INF && dist[k][j] != INF) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
}
// μ΄κΈ°ν
void initGraph() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (i == j) dist[i][j] = 0;
else dist[i][j] = INF;
}
}
}
// C++
void floydWarshall(vector<vector<int>>& dist) {
int V = dist.size();
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] != INT_MAX && dist[k][j] != INT_MAX) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}
// μ΄κΈ°ν
vector<vector<int>> initDist(int V) {
vector<vector<int>> dist(V, vector<int>(V, INT_MAX));
for (int i = 0; i < V; i++) {
dist[i][i] = 0;
}
return dist;
}
# Python
def floyd_warshall(V, edges):
INF = float('inf')
# μ΄κΈ°ν
dist = [[INF] * V for _ in range(V)]
for i in range(V):
dist[i][i] = 0
for u, v, w in edges:
dist[u][v] = w
# νλ‘μ΄λ-μμ
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
κ²½λ‘ λ³΅μ¶
// C++
void floydWarshallWithPath(vector<vector<int>>& dist,
vector<vector<int>>& next) {
int V = dist.size();
// μ΄κΈ°ν
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] != INT_MAX && i != j) {
next[i][j] = j;
} else {
next[i][j] = -1;
}
}
}
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] != INT_MAX && dist[k][j] != INT_MAX &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = next[i][k];
}
}
}
}
}
vector<int> getPath(const vector<vector<int>>& next, int from, int to) {
if (next[from][to] == -1) return {};
vector<int> path = {from};
while (from != to) {
from = next[from][to];
path.push_back(from);
}
return path;
}
5. 0-1 BFS¶
κ°λ ¶
κ°μ κ°μ€μΉκ° 0 λλ 1μΈ κ·Έλνμμ μ΅λ¨ 거리
β λ±(Deque) μ¬μ©νμ¬ O(V+E)μ ν΄κ²°
μ리:
- κ°μ€μΉ 0μΈ κ°μ : λ± μμ μΆκ°
- κ°μ€μΉ 1μΈ κ°μ : λ± λ€μ μΆκ°
ν¨κ³Ό: νμ μ΅μ 거리 μ μ μ΄ μμ μμΉ
ꡬν¶
// C++
vector<int> zeroOneBFS(const vector<vector<pii>>& adj, int start) {
int V = adj.size();
vector<int> dist(V, INT_MAX);
deque<int> dq;
dist[start] = 0;
dq.push_front(start);
while (!dq.empty()) {
int u = dq.front();
dq.pop_front();
for (auto [v, weight] : adj[u]) {
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
if (weight == 0) {
dq.push_front(v);
} else {
dq.push_back(v);
}
}
}
}
return dist;
}
# Python
from collections import deque
def zero_one_bfs(graph, start, n):
dist = [float('inf')] * n
dist[start] = 0
dq = deque([start])
while dq:
u = dq.popleft()
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
if weight == 0:
dq.appendleft(v)
else:
dq.append(v)
return dist
6. μ°μ΅ λ¬Έμ ¶
λ¬Έμ 1: νΉμ 거리μ λμ μ°ΎκΈ°¶
μμ λμμμ μ νν K κ±°λ¦¬μΈ λͺ¨λ λμλ₯Ό μ°ΎμΌμΈμ.
μ λ΅ μ½λ
import heapq
def cities_at_distance_k(n, edges, start, k):
graph = [[] for _ in range(n + 1)]
for a, b in edges:
graph[a].append(b) # λ¨λ°©ν₯
dist = [float('inf')] * (n + 1)
dist[start] = 0
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v in graph[u]:
if dist[u] + 1 < dist[v]:
dist[v] = dist[u] + 1
heapq.heappush(pq, (dist[v], v))
result = [i for i in range(1, n + 1) if dist[i] == k]
return sorted(result) if result else [-1]
λ¬Έμ 2: μμ μ¬μ΄ν΄ ν짶
μμ μ¬μ΄ν΄μ΄ μ‘΄μ¬νλμ§ νμΈνμΈμ.
μ λ΅ μ½λ
def has_negative_cycle(V, edges):
dist = [0] * V # λͺ¨λ μ μ μμ μμ κ°λ₯
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
return True
return False
μΆμ² λ¬Έμ ¶
| λμ΄λ | λ¬Έμ | νλ«νΌ | μκ³ λ¦¬μ¦ |
|---|---|---|---|
| ββ | μ΅λ¨κ²½λ‘ | λ°±μ€ | Dijkstra |
| ββ | Network Delay Time | LeetCode | Dijkstra |
| βββ | νμλ¨Έμ | λ°±μ€ | Bellman-Ford |
| βββ | νλ‘μ΄λ | λ°±μ€ | Floyd-Warshall |
| βββ | κ²½λ‘ μ°ΎκΈ° | λ°±μ€ | Floyd-Warshall |
| ββββ | Cheapest Flights | LeetCode | λ³ν Dijkstra |
μκ³ λ¦¬μ¦ μ ν κ°μ΄λ¶
μ§λ¬Έ 1: κ°μ€μΉκ° μλκ°?
βββ No β BFS (O(V+E))
βββ Yes β
μ§λ¬Έ 2: μμ κ°μ€μΉκ° μλκ°?
βββ No β Dijkstra (O(E log V))
βββ Yes β
μ§λ¬Έ 3: μμ μ¬μ΄ν΄ νμ§κ° νμνκ°?
βββ Yes β Bellman-Ford (O(VE))
βββ No β
μ§λ¬Έ 4: λͺ¨λ μ μ΅λ¨κ±°λ¦¬κ° νμνκ°?
βββ Yes β Floyd-Warshall (O(VΒ³))
βββ No β Bellman-Ford (O(VE))
μΆκ°: κ°μ€μΉκ° 0, 1λ§ μμΌλ©΄ β 0-1 BFS (O(V+E))
λ€μ λ¨κ³¶
- 15_Minimum_Spanning_Tree.md - Kruskal, Prim, Union-Find
μ°Έκ³ μ룶
- Dijkstra Visualization
- Shortest Path Problems
- Introduction to Algorithms (CLRS) - Chapter 24, 25