최단경로 알고리즘

A . 최단경로 알고리즘의 특성을 정리해보면

1. 최단경로의 부분 경로는 부분경로에 해당하는 노드 간의 최단경로가 된다.

2. 최단 경로의 경우, 사이클이 존재하지 않는다.

B. 최단 경로 알고리즘 Notation

d[v] : start node에서 노드 v까지 최단 경로 estimate

pi[v] : v까지의 최단경로 중 v의 직전 노드

C. Relaxation

def relax(u,v,w):
	if d[v]>d[u]+w:
    	d[v]=d[u]+v
        pi[v]=u
    	

D. Generic Algorithm

최단경로 알고리즘 문제는 , 노드와 에지들에 대해 어떤 순서로 얼마나 relaxation을 할 것이냐의 문제이다.

E. Bellman-Ford Algorithm

최단 경로의 최대 에지 갯수는 n-1개 이므로 모든 에지들에 대해 relaxation을 n-1번 하면 된다.

n-1번 후에도 update가 계속되면, 음수 사이클이 존재한다는 의미이다.

class Graph{
    constructor(num)
    { 
        this.num=num
        this.edges=[] //[u,v,w]
        this.distance={} //distance[v]
        this.nodes = Object.keys(this.distance)

    }
    addEdge(u,v,w)
    {
        this.edges.push([u,v,w])
        //distance estimate에 등록
        if(this.distance[v]===undefined)
        {
            this.distance[v]=1000 //distance[v]=inf
        }
        if(this.distance[u]===undefined)
        {
            this.distance[u]=1000 //distance[u]]=inf
        }

    }
    

    BellmanFord(node)
    {

        var nodes = Object.keys(this.distance).map(function(e){return Number(e)})
        var distance = this.distance
        var edges = this.edges

        for(var i=0;i<this.num;i++) //최대 에지 갯수가 n-1개이므로 n-1번 반복
        {
           nodes.forEach(function(u){
               //출발점은 초기화
               if(u===node)
               {
                    distance[u]=0
               }              
               nodes.forEach(function(v)
               {
                   if(u===v) //u,v가 같으면 distance update할 필요가 없음
                   {
                   }
                   else{
                    var d_u = distance[u]
                    var d_v=  distance[v]
                    //u,v를 찾고, 거리를 기준으로 오름차순 정렬
                    var min_w = edges.filter(function(e){return e[0]===u&&e[1]===v}).sort(function(a,b){return a[2]-b[2]}).shift()
                    //u,v를 잇는 에지가 있다면
                    if(min_w!==undefined)
                    {
                        if(d_v>min_w[2]+d_u)
                        {
                            distance[v] = min_w[2]+d_u
                        }
                        
                    }
                   }
               })
               console.log(distance)
           })
        }
    }
}



g = new Graph(5)  
g.addEdge(0, 1, -1)  
g.addEdge(0, 2, 4)  
g.addEdge(1, 2, 3)  
g.addEdge(1, 3, 2)  
g.addEdge(1, 4, 2)  
g.addEdge(3, 2, 5)  
g.addEdge(3, 1, 1)  
g.addEdge(4, 3, -3)  
  

//Print the solution  
g.BellmanFord(0)