Skip to content

Commit e40421f

Browse files
isGeekCodeisGeekCode
committed
dijkstra
1 parent d72aea0 commit e40421f

2 files changed

Lines changed: 148 additions & 0 deletions

File tree

‎Algorithm/algorithm_000_AQuck.md‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -345,6 +345,7 @@ print(count)
345345
<br><br>
346346

347347
### MST
348+
- 모든 노드를 잇는데 최소비용이 드는 것
348349
- MST는 정형화된 풀이 방법이 있음
349350
- 대부분 양방향 간선이 있는 양방향 그래프 문제
350351
- 사용 알고리즘
@@ -597,8 +598,85 @@ print(rs)
597598
<br><br>
598599

599600
### 다익스트라
601+
- 그냥 외워서 사용할것
602+
- 중요한건.. 해당 문제가 다익스트라 문제인지 알아보는게 중요
603+
- 한 점에서 다른 모든 노드 까지 가는데 최소비용
600604

601605
```swift
606+
607+
let input = """
608+
5 6
609+
1
610+
5 1 1
611+
1 2 2
612+
1 3 3
613+
2 3 4
614+
2 4 5
615+
3 4 6
616+
"""
617+
618+
//let lines = input.split(separator: "\n").map { String($0) }
619+
//let firstLine = lines[0].split(separator: " ").map { Int($0)! }
620+
let firstLine = readLine()!.split(separator: " ").map{ Int($0)!}
621+
622+
let (v, e) = (firstLine[0], firstLine[1])
623+
//let startV = Int(lines[1])!
624+
let startV = Int(readLine()!)!
625+
626+
// 인접 리스트 초기화
627+
var edges = Array(repeating: [Edge](), count: v + 1)
628+
var distance = Array(repeating: Int.max, count: v + 1)
629+
distance[1] = 0 // 시작 노드의 거리는 0
630+
631+
for i in 1...e{
632+
// let edgeData = lines[i].split(separator: " ").map { Int($0)! }
633+
let edgeData = readLine()!.split(separator: " ").map { Int($0)! }
634+
let (a, b, c) = (edgeData[0], edgeData[1], edgeData[2])
635+
// 양방향(무방향) 그래프인 경우 a에서 b로, b에서 a로 두번 추가
636+
// edges[a].append((c, b))
637+
// edges[b].append((c, a))
638+
639+
edges[a].append(Edge(cost: c, node: b))
640+
// edges[b].append(Edge(cost: c, node: a))
641+
642+
}
643+
644+
var heap = Heap<Edge>()
645+
heap.insert(Edge(cost: 0, node: startV))
646+
647+
while !heap.isEmpty {
648+
// let (w, eachNode) = heap.removeFirst() // heap을 pop
649+
guard let edge = heap.extractMin() else { break }
650+
let (w, eachNode) = (edge.cost, edge.node)
651+
// w: 현재 비용
652+
// eachNode : 현재 노드
653+
/// 그 노드에 대한 거리가 최신의 최소 거리(distance[eachNode])와 일치하지 않으면
654+
if w != distance[eachNode] {
655+
continue
656+
}
657+
658+
for nextEdge in edges[eachNode] {
659+
// 현재 관리중인 노드의 거리가 더 크면 갱신
660+
if distance[nextEdge.node] > distance[eachNode] + nextEdge.cost {
661+
distance[nextEdge.node] = distance[eachNode] + nextEdge.cost
662+
let newEdge = Edge(cost: distance[nextEdge.node], node: nextEdge.node)
663+
heap.insert(newEdge)
664+
}
665+
}
666+
}
667+
668+
for i in 1...v {
669+
if distance[i] == Int.max {
670+
print("INF")
671+
} else {
672+
print(distance[i])
673+
}
674+
}
675+
676+
677+
678+
679+
602680
```
603681

604682
<br><br>

‎Algorithm/algorithm_009_essential_Dijkstra.md‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
# 필수 알고리즘 - 다익스트라 (Dijkstra)
2+
3+
한 노드에서 다른 노드까지 가는데 최소비용
4+
5+
<img width="461" alt="스크린샷 2024-06-06 오전 1 32 42" src="https://github.com/isGeekCode/TIL/assets/76529148/222082c3-afe3-43a8-b896-330f9673995c">
6+
7+
8+
1 -> 2 :: 2가 든다.
9+
1 -> 3 :: 3이 든다.
10+
1 -> 4 :: (1)번으로 선택 :: 7이 든다.
11+
- (1) 1 -> 2 -> 4 :: 2 + 5 :: 7
12+
- (2) 1 -> 3 -> 4 :: 3 + 6 :: 9
13+
1 -> 5 :: 단방향만 가능하므로 갈 수 없다.
14+
15+
최소비용 ::: `[2, 3, 7, X]`
16+
17+
## 작동원리
18+
- 간선(edge)저장 :: 인접리스트, 거리배열 : 초기값은 무한대로 설정, 힙 시작점 추가 [(0,1)]
19+
20+
거리배열 초기값:::[INF, INF, INF, INF, INF]
21+
22+
<img width="461" alt="스크린샷 2024-06-06 오전 1 32 42" src="https://github.com/isGeekCode/TIL/assets/76529148/222082c3-afe3-43a8-b896-330f9673995c">
23+
24+
힙 :::[(0,1)] // 시작점.. 1번에서 1만큼 가려면 0만큼 든다...
25+
26+
힙은 가장 앞에있는 것으로 최대값 최소값을 구한다.
27+
거리배열 갱신 : [0, INF, INF, INF, INF]
28+
- 힙에서 노드를 때면서 간선을 통할때, 거리가 짧아진다면!
29+
30+
->1번 노드를 빼서,, 1번과 간선으로 연결된 노드들을 갈때, 거리가 더 짧아진다면
31+
1 -> 2 ::: 2가 든다.
32+
거리배열 갱신 : [0, 2, INF, INF, INF]
33+
그리고 힙에 추가
34+
힙 갱신:::[(2,2)]
35+
1 -> 3 ::: 3이 든다.
36+
거리배열 갱신 : [0, 2, 3, INF, INF]
37+
힙 갱신:::[(2,2), (3,3)]
38+
39+
여기까지 1번 노드에 대한 진행이 끝
40+
41+
이제 힙에 최소값인 2번 노드에 연결된 간선을 처리한다.
42+
->2번 노드를 빼서,, 2번과 간선으로 연결된 노드들을 갈때, 거리가 더 짧아진다면
43+
2 -> 4 ::: 이것은 1 -> 2 -> 4 로 가는 거기 때문에 기존의 2 + 5 ::: 7이 든다.
44+
거리배열 갱신 : [0, 2, 3, 7, INF]
45+
힙 갱신:::[(3,3), (7,4)]
46+
2 -> 3 ::: 이것은 1 -> 2 -> 3 으로 가는 것이 2 + 4 ::: 6 인데 이것 보다 1 -> 3 이 3이드는 비용이 더 적다.
47+
그렇기 때문에 이미 거리배열에서 3만큼 간다고 되어있어서 갱신할 필요가 없다.
48+
여기까지 2번 노드에 대한 진행이 끝
49+
50+
이제 힙에 최소값인 3번 노드에 연결된 간선을 처리한다.
51+
->3번 노드를 빼서,, 3번과 간선으로 연결된 노드들을 갈때, 거리가 더 짧아진다면
52+
3 -> 4 ::: 이것은 1 -> 3 -> 4 로 가는 거기 때문에 기존의 3 + 6 ::: 9기 든다. 하지만 4로 가는 것은 1 2 4로가는게 기존에 이미 7이 더 적다고 판단되어있기 때문에 갱신 X
53+
거리배열 그대로 : [0, 2, 3, 7, INF]
54+
힙 갱신:::[(7,4)]
55+
2 -> 3 ::: 이것은 1 -> 2 -> 3 으로 가는 것이 2 + 4 ::: 6 인데 이것 보다 1 -> 3 이 3이드는 비용이 더 적다.
56+
그렇기 때문에 이미 거리배열에서 3만큼 간다고 되어있어서 갱신할 필요가 없다.
57+
여기까지 3번 노드에 대한 진행이 끝
58+
59+
60+
61+
이제 힙에 최소값인 4번 노드에 연결된 간선을 처리한다.
62+
->4번 노드를 빼서,, 4번과 간선으로 연결된 노드들을 갈때, 거리가 더 짧아진다면
63+
4번에서는 갈 수 있는 그래프가 없음.
64+
거리배열 그대로 : [0, 2, 3, 7, INF]
65+
힙 갱신:::[]
66+
67+
마지막 1번에서는 5번으로 갈 수 있는 길 자체가 없기 대문에 INF 그대로 남겨둔다.
68+
결과 [0, 2, 3, 7, INF]
69+
70+
## 핵심 코드

0 commit comments

Comments
 (0)