다이크스트라
- 가중치가 모두 양수인 그래프에서 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘
- 음수 가중치에서는 더 저렴한 비용이 뒤늦게 발견될 수 있어서 탐색 순서가 깨짐 -> 플로이드-워셜 알고리즘 사용
배열을 이용한 다이크스트라 문제풀이
fun solution(v: Int, k: Int, edges: List<List<Int>>): String {
// 1. 인접리스트 생성
val adjList = List(v + 1) { mutableListOf<Pair<Int, Int>>() }
// 2. 인접리스트에 간선 기록
edges.forEach {
val (u, v, w) = it
adjList[u].add(v to w) // 단방향 기록
}
// 3. 다이크스트라 세팅
val minPrice = IntArray(v + 1) { Int.MAX_VALUE }
val visited = BooleanArray(v + 1) { false }
val nextVisit = mutableSetOf<Int>()
var visitedCount = 0
var currentVertex = k
minPrice[currentVertex] = 0 // 시작점의 비용은 0
// 4. 다이크스트라 로직 실행
while (visitedCount < v) {
// 4-1. 방문 체크
visited[currentVertex] = true
visitedCount++
// 4-2. 인접 정점에 대한 최소비용 갱신
for ((nextVertex, weight) in adjList[currentVertex]) {
if (visited[nextVertex]) continue
nextVisit.add(nextVertex)
minPrice[nextVertex] = minOf(
minPrice[nextVertex],
minPrice[currentVertex] + weight,
)
}
// 4-3. 미방문한 인접 정점 중 가장 최소비용인 곳으로 이동
if (nextVisit.isEmpty()) break
currentVertex = nextVisit.minBy { minPrice[it] }
nextVisit.clear()
}
// 5. 결과 출력
val result = mutableListOf<String>()
val inf = "INF"
for (i in 1..v) {
val price = minPrice[i]
if (price < Int.MAX_VALUE) {
result.add(price.toString())
} else {
result.add(inf)
}
}
return result.joinToString("\n")
}
fun main() = with(System.`in`.bufferedReader()) {
fun readIntList() = readLine().split(" ").map { it.toInt() }
val (v, e) = readIntList()
val k = readLine().toInt()
val edges = List(e) { readIntList() }
println(solution(v, k, edges))
}우선순위 큐를 이용한 다이크스트라
import java.util.PriorityQueue
fun solution(v: Int, k: Int, edges: List<List<Int>>): String {
// 1. 인접리스트 생성
val adjList = List(v + 1) { mutableListOf<Pair<Int, Int>>() }
// 2. 인접리스트에 간선 기록
edges.forEach {
val (u, v, w) = it
adjList[u].add(v to w) // 단방향 기록
}
// 3. 다이크스트라 세팅
val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
val minPrice = IntArray(v + 1) { Int.MAX_VALUE }
val visited = BooleanArray(v + 1) { false }
pq.add(k to 0)
minPrice[k] = 0 // 시작점의 비용은 0
// 4. 다이크스트라 로직 실행
while (pq.isNotEmpty()) {
val (cur, _) = pq.poll()
if (visited[cur]) continue
visited[cur] = true
for ((next, nextCost) in adjList[cur]) {
if (minPrice[next] > minPrice[cur] + nextCost) {
minPrice[next] = minPrice[cur] + nextCost
pq.add(next to minPrice[next])
}
}
}
// 5. 결과 출력
val result = mutableListOf<String>()
val inf = "INF"
for (i in 1..v) {
val price = minPrice[i]
if (price < Int.MAX_VALUE) {
result.add(price.toString())
} else {
result.add(inf)
}
}
return result.joinToString("\n")
}
fun main() = with(System.`in`.bufferedReader()) {
fun readIntList() = readLine().split(" ").map { it.toInt() }
val (v, e) = readIntList()
val k = readLine().toInt()
val edges = List(e) { readIntList() }
println(solution(v, k, edges))
}
