다익스트라 알고리즘 (Dijkstra’s Algorithm)
다익스트라 알고리즘은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 주로 네트워크 경로 탐색, GPS 길 찾기, 소셜 네트워크 분석 등에서 사용됩니다. 이 알고리즘은 가중치가 있는 그래프에서 동작하며, 음의 가중치가 없는 경우에만 사용할 수 있습니다.
알고리즘의 주요 동작 원리:
- 시작 정점 설정: 시작 정점에서 자기 자신까지의 거리는 0으로, 나머지 정점까지의 거리는 무한대(∞)로 설정합니다.
- 우선순위 큐 사용: 거리가 짧은 정점부터 처리되도록 우선순위 큐를 사용하여 가장 짧은 거리를 가진 정점을 선택합니다.
- 경로 업데이트: 선택한 정점을 통해 다른 인접한 정점으로 가는 경로가 더 짧으면 그 경로로 거리를 업데이트합니다.
- 반복: 모든 정점이 방문될 때까지 위의 과정을 반복합니다.
다익스트라 알고리즘의 사용 예시
- 네트워크 라우팅: 네트워크에서 데이터 패킷이 최단 시간에 도착하도록 경로를 찾는 데 사용됩니다.
- GPS 내비게이션: 차량이나 사람이 목적지까지 가는 최단 경로를 계산하는 데 활용됩니다.
- 소셜 네트워크 분석: 특정 사용자들 사이의 최소 연결 경로를 분석할 때 사용됩니다.
JavaScript 예제 코드 (다익스트라 알고리즘)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue(vertex, priority) {
this.queue.push({ vertex, priority });
this.queue.sort((a, b) => a.priority - b.priority); // 우선순위에 따라 정렬
}
dequeue() {
return this.queue.shift().vertex;
}
isEmpty() {
return this.queue.length === 0;
}
}
function dijkstra(graph, start) {
let distances = {};
let pq = new PriorityQueue();
// 모든 거리를 무한대로 설정, 시작 정점은 0
for (let vertex in graph) {
if (vertex === start) {
distances[vertex] = 0;
pq.enqueue(vertex, 0);
} else {
distances[vertex] = Infinity;
}
}
// 우선순위 큐가 빌 때까지 반복
while (!pq.isEmpty()) {
let currentVertex = pq.dequeue();
for (let neighbor in graph[currentVertex]) {
let distance = graph[currentVertex][neighbor];
let newDist = distances[currentVertex] + distance;
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
pq.enqueue(neighbor, newDist);
}
}
}
return distances;
}
// 그래프 예시 (인접 리스트)
let graph = {
A: { B: 1, C: 4 },
B: { A: 1, C: 2, D: 5 },
C: { A: 4, B: 2, D: 1 },
D: { B: 5, C: 1 },
};
console.log(dijkstra(graph, "A")); // { A: 0, B: 1, C: 3, D: 4 }
Rust 예제 코드 (다익스트라 알고리즘)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::cmp::Ordering;
use std::usize;
#[derive(Copy, Clone, Eq, PartialEq)]
struct State {
cost: usize,
position: usize,
}
impl Ord for State {
fn cmp(&self, other: &Self) -> Ordering {
other.cost.cmp(&self.cost)
}
}
impl PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
fn dijkstra(adj_list: &Vec<Vec<(usize, usize)>>, start: usize) -> Vec<usize> {
let mut dist: Vec<usize> = vec![usize::MAX; adj_list.len()];
let mut heap = BinaryHeap::new();
dist[start] = 0;
heap.push(State { cost: 0, position: start });
while let Some(State { cost, position }) = heap.pop() {
if cost > dist[position] {
continue;
}
for &(neighbor, weight) in &adj_list[position] {
let next = State {
cost: cost + weight,
position: neighbor,
};
if next.cost < dist[neighbor] {
dist[neighbor] = next.cost;
heap.push(next);
}
}
}
dist
}
fn main() {
let graph = vec![
vec![(1, 1), (2, 4)], // A
vec![(0, 1), (2, 2), (3, 5)], // B
vec![(0, 4), (1, 2), (3, 1)], // C
vec![(1, 5), (2, 1)], // D
];
let start = 0; // 시작 정점 (A)
let distances = dijkstra(&graph, start);
println!("{:?}", distances); // 출력: [0, 1, 3, 4]
}
요약
- 다익스트라 알고리즘은 네트워크, 경로 탐색, 데이터 전송 최적화 등에 사용되는 알고리즘입니다.
- 시작 정점에서 모든 다른 정점까지의 최단 경로를 구하는 데 사용되며, 음의 가중치가 없는 그래프에서만 적용 가능합니다.
Dijkstra’s Algorithm
Dijkstra’s Algorithm is used to find the shortest path from a starting vertex to all other vertices in a weighted graph. It is commonly applied in network routing, GPS navigation, and social network analysis. The algorithm works on graphs with non-negative weights.
How the algorithm works:
- Set the starting vertex: The distance from the start vertex to itself is 0, and the distances to all other vertices are set to infinity (∞).
- Use a priority queue: A priority queue is used to select the vertex with the smallest distance first.
- Update paths: For each neighboring vertex, update the shortest distance if a shorter path is found through the current vertex.
- Repeat: Continue until all vertices have been visited.
Where to use Dijkstra’s Algorithm
- Network Routing: Finding the fastest path for data packets through a network.
- GPS Navigation: Calculating the shortest route for a vehicle or pedestrian.
- Social Network Analysis: Finding the minimum connection path between users.
JavaScript Example Code (Dijkstra’s Algorithm)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue(vertex, priority) {
this.queue.push({ vertex, priority });
this.queue.sort((a, b) => a.priority - b.priority); // Sort by priority
}
dequeue() {
return this.queue.shift().vertex;
}
isEmpty() {
return this.queue.length === 0;
}
}
function dijkstra(graph, start) {
let distances = {};
let pq = new PriorityQueue();
// Set distances to infinity, except for the start vertex
for (let vertex in graph) {
if (vertex === start) {
distances[vertex] = 0;
pq.enqueue(vertex, 0);
} else {
distances[vertex] = Infinity;
}
}
// Process the priority queue
while (!pq.isEmpty()) {
let currentVertex = pq.dequeue();
for (let neighbor in graph[currentVertex]) {
let distance = graph[currentVertex][neighbor];
let newDist = distances[currentVertex] + distance;
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
pq.enqueue(neighbor, newDist);
}
}
}
return distances;
}
// Example graph (adjacency list)
let graph = {
A: { B: 1, C: 4 },
B: { A: 1, C: 2, D: 5 },
C: { A: 4, B: 2, D: 1 },
D: { B: 5, C: 1 },
};
console.log(dijkstra(graph, "A")); // { A: 0, B: 1, C: 3, D: 4 }
Rust Example Code (Dijkstra’s Algorithm)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::cmp::Ordering;
use std::usize;
#[derive(Copy, Clone, Eq, PartialEq)]
struct State {
cost: usize,
position: usize,
}
impl Ord for State {
fn cmp(&self, other: &Self) -> Ordering {
other.cost.cmp(&self.cost)
}
}
impl PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
fn dijkstra(adj_list: &Vec<Vec<(usize, usize)>>, start: usize) -> Vec<usize> {
let mut dist: Vec<usize> = vec![usize::MAX; adj_list.len()];
let mut heap = BinaryHeap::new();
dist[start] = 0;
heap.push(State { cost: 0, position: start });
while let Some(State { cost, position }) = heap.pop() {
if cost > dist[position] {
continue;
}
for &(neighbor, weight) in &adj_list[position] {
let next = State {
cost: cost + weight,
position: neighbor,
};
if next.cost < dist[neighbor]) {
dist[neighbor] = next.cost;
heap.push(next);
}
}
}
dist
}
fn main() {
let graph = vec![
vec![(1, 1), (2, 4)], // A
vec![(0, 1), (2, 2), (3, 5)], // B
vec![(0, 4), (1, 2), (3, 1)], // C
vec![(1, 5), (2, 1)], // D
];
let start = 0; // Starting vertex (A)
let distances = dijkstra(&graph, start);
println!("{:?}", distances); // Output: [0, 1, 3, 4]
}
Summary:
- Dijkstra’s Algorithm is useful for network routing, pathfinding, and analyzing minimum connections in networks.
- It works on graphs with non-negative weights and finds the shortest path from a single source to all other vertices.