Skip to content

2023 01 08

오늘 한 일

벨만 포드 알고리즘

  • 음수 간선이 있어도 최단 거리를 구할수 있다 (Edge Relaxation 을 N-1 회 수행)
  • 한번 더 수행 했을때 업데이트가 발생하면 사이클이 있는 것이다.
벨만 포드 큰 틀
var answer = "NO"  

val stt = 1  
cost[stt] = 0  
repeat(n - 1) {  
    // edge relaxation  
    for (v in 1..n) {  
        for (edge in edgesMap[v]) {  
            if (cost[edge.to] > cost[v] + edge.weight) {  
                cost[edge.to] = cost[v] + edge.weight  
            }  
        }  
    }  
}  

// edge relaxation 한번 더  
for (v in 1..n) {  
    for (edge in edgesMap[v]) {  
        if (cost[edge.to] > cost[v] + edge.weight) {  
            answer  = "YES"  
        }  
    }  
}  
println(answer)
Last update: February 26, 2023
Created: January 8, 2023