[Swift] Swift로 짜보는 다익스트라 알고리즘 (최단경로를 찾아요)

우선 다익스트라 알고리즘은 

- Cycle ( 두 정점이 서로를 향하고 있는 것 ) 이 없는 그래프

- Weighted 그래프 ( 그래프의 간선에 가중치를 준 가중 그래프 ) 에서 쓸 수 있다. 

   하지만 음의 가중치가 있으면 안된다. 만약 음의 가중치를 가진 그래프에서 최단 경로를 찾고 싶으면 벨만 - 포드 알고리즘을 사용하면 된다 

가중 그래프에서 X까지의 최단 경로 ( 가장 빠른 경로 ) 를 찾을 수 있는 알고리즘이다.

다익스트라 알고리즘은 4단계로 구성된다 

1] 가장 시간이 적게 걸리는 정점 찾기

2] 이 정점의 이웃 정점들의 시간을 조사 -> 현재보다 더 적은 시간의 경로가 존재한다면, 시간을 수정

3] 그래프 상의 모든 정점에 대해 이러한 일을 반복한다

4] 최종경로를 계산한다 

[ 예시 ]

                        

[ 코드로 구현해보자 ] 

알고리즘의 실행흐름과 컨셉을 보기 위한 코드라서 간결하게 하기 위해 강제 언랩핑을 편하게 썼다....ㅎㅎㅎㅎㅎ

3개의 해시 테이블 ( 그래프, 가격, 부모 ) 가 필요하고 

가격과 부모 딕셔너리는 알고리즘을 실행하면서 갱신된다 

import Foundation
 
// 다익스트라 알고리즘
// 가격,부모 딕셔너리는 계속 갱신될 것
let graphs:[String:[String:Int]] = ["A":["B":5,"C":0],
                                    "B":["D":15,"E":20],
                                    "C":["D":30,"E":35],
                                    "D":["F":20],
                                    "E":["F":10],
                                    "F":[:]
]
 
var costs = ["B":5,
             "C":0,
             "D":Int.max,
             "E":Int.max,
             "F":Int.max
]
 
var parents = [ "B":"A",
                "C":"A",
                "D":"",
                "E":"",
                "F":""
]
 
var processedNodes:[String] = []
 
 
// 아직 처리 하지 않은 정점 중 더 싼 것이 있으면 새로운 정점으로
func findLowestCostNode(costs:[String:Int])->String{
    
    var lowest_cost = Int.max
    var lowest_node = ""
    
    for (key,value) in costs{
        if value < lowest_cost && !processedNodes.contains(key){
            lowest_cost = value
            lowest_node = key
        }
    }
    
    return lowest_node
}
 
// 가장 싼 가격을 찾아서 가격 갱신 & 부모갱신 -> 해당 점점을 처리했다는 사실 기록
// 모든 정점을 처리할때 까지 반복
var node = findLowestCostNode(costs: costs)
 
while node != ""{
    let cost = costs[node]
    let neighbors = graphs[node]
    
    for (key,value) in neighbors!{
        
        let new_cost = cost! + value
        if new_cost < costs[key]!{
            costs[key] = new_cost
            parents[key] = node
        }
    }
    
    processedNodes.append(node)
    node = findLowestCostNode(costs: costs)
}
 
 
print(parents)
//["B": "A", "F": "E", "C": "A", "D": "B", "E": "B"]
print(costs)
//["B": 5, "F": 35, "C": 0, "D": 20, "E": 25]
 
//루트로 만들기
var routes:[String] = []
routes.append("F")
 
var parent = parents["F"]
routes.append(parent!)
 
while parent != "A"{
    parent = parents[parent!]
    routes.append(parent!)
}
 
 
 
// 최단 경로
for (index,item) in routes.reversed().enumerated(){
    
    //마지막 F프린트 하고 \n하고 밑의 가격출력위함
    if index == routes.count - 1{
        print(item)
    } else{
         print(item, terminator:"->")
    }
}
//A->B->E->F
 
 
// 가격
print(costs["F"]!)
//35