최단 경로 알고리즘 - 다익스트라 알고리즘(Dijkstra's Algorithm)

1. 문제

• 간선의 가중치가 존재하는 그래프의 최단 경로를 찾는 다익스트라 알고리즘을 구현

2. 문제 설계

• 처음 각 노드에 대한 최단 경로를 큰 값으로 초기화 하고,
• 시작점의 최단 경로 값을 0으로 시작하고, 방문 처리를 한 후 시작점으로부터의 최단 경로 값과 인접한 정점들의 최단 경로의 합 중 더 작은 값으로 저장
• 이후 다시 아직 방문하지 않은 정점에 대한 최단 경로 값의 최소값을 찾고 방문 처리를 함
• 위 과정을 모든 정점에 대해 반복하게 되면 시작점으로부터 모든 정점에 대한 최단 경로를 구할 수 있음

3. 전체 코드

//MARK: - 다익스트라 알고리즘

//MARK: - Framework
import Foundation

//MARK: - Type
struct Graph {
    //MARK: - Property
    var edges: [Int]
    var costs: [Int]
    
    //MARK: - Initializer
    init() {
        self.edges = []
        self.costs = []
    }
}

//MARK: - Variable
var graph: [Graph] = []
var visited: [Bool] = []

//MARK: - Function
func dijkstra(_ N: Int, _ start: Int, _ end: Int) -> Int {
    var distances: [Int] = Array(repeating: 987987987, count: N + 10)
    distances[start] = 0
    
    for _ in 0..<N {
        var minCost, minIndex: Int
        minCost = 987987987
        minIndex = -1
        
        for j in 0..<N {
            if !visited[j] && minCost > distances[j] {
                minCost = distances[j]
                minIndex = j
            }
        }
        visited[minIndex] = true
        
        for j in 0..<graph[minIndex].edges.count {
            let y: Int = graph[minIndex].edges[j]
            let cost: Int = graph[minIndex].costs[j]
            
            if distances[y] > distances[minIndex] + cost {
                distances[y] = distances[minIndex] + cost
            }
        }
    }
    
    return distances[end]
}

func solution() -> Void {
    //MARK: - Input
    guard let input: [String] = readLine()?.components(separatedBy: " ") else { return }
    let N: Int = input.map { Int($0) }[0] ?? 0
    let M: Int = input.map { Int($0) }[1] ?? 0
    let start: Int = input.map { Int($0) }[2] ?? 0
    let end: Int = input.map { Int($0) }[3] ?? 0
    var result: Int = 0
    
    graph = Array(repeating: Graph(), count: N + 10)
    visited = Array(repeating: false, count: N + 10)
    
    for _ in 0..<M {
        guard let inputData: [String] = readLine()?.components(separatedBy: " ") else { return }
        let a: Int = inputData.map { Int($0) }[0] ?? 0
        let b: Int = inputData.map { Int($0) }[1] ?? 0
        let c: Int = inputData.map { Int($0) }[2] ?? 0
        
        graph[a].edges.append(b)
        graph[b].edges.append(a)
        graph[a].costs.append(c)
        graph[b].costs.append(c)
    }
    
    //MARK: - Process
    result = dijkstra(N, start, end)
    
    //MARK: - Output
    print(result)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.