[Algorithm] MCSP_최단거리

1. 최소 비용 신장 트리

  a. 가중치 그래프 혹은 네트워크: 간선에 가중치가 부여된 그래프

  b. 최소 비용 신장 트리(간선들의 가중치의 합): 합이 최소가 되는 트리

  c. 갈망기법: 최적의 해를 단계별로 구현

# 신장트리 제한 조건: 무방향 그래프, n - 1(n=IVI)개의 간선만 사용

 

2. Kruskal 알고리즘

  i) 방법:

  ˙비용이 가장 작은 간선 하나 선택 -> 최소비용신장트리(T)에 추가(n개의 정점 가진 그래프G의 간선 집합 E(G)로부터 n-1개의 간선 선정과정)

  ˙이미 T에 포함된 간선과 사이클은 제외 시킴

  ii) 구현: ① 최소비용 간선을 선택 -> ② T에 추가로 포함될 정점들을 연결 요소별로 그룹을 만들어 유지

Kruskal(G, n)
				        // G=(E,V)이고 n=|V|(|V|는 정점 수)
	T<-＠;  		
    edgelist <- E(G);   // 그래프 G의 간선 리스트
    Sº<-{0}, S1<-{1},...,Sn-1<-{n-1}; // 기본세팅
    while(|E(T)|<n-1 and |edgelist|>0) do{
    					// |E(T)|는 T에 포함된 간선수, |edgeList|는 검사할 간선수
		select least-cost(i,j) from edgeList;
        edgeList <- edgeList-{(i,j)};
        if({i,j}가 동시에 Sk for any k에 속하지 않음) then {
        	T <- T 합집합 {(i,j)};
            Si <- Si 합집합 Sj;
        }
    }
    if(|E(T)|<n-1) then print('no spanning tree');
    return T;

 3. Prim 알고리즘

   i) 방법: 하나의 간선 선택 -> 최소비용신장트리(T) 구축(<->kruskal과 달리 구축 전 과정을 통해 하나의 트리만 확장함) 

   ii) 구현: ①점점u를 트리의 정점 집합 V(T)에 추가 -> ②V(T) 정점과 인접한 최소비용간선(u,v) 선택 후 T에 추가+새로 선정된 정점은 V(T)에 포함 

Prim(G, i)
	T <- ＠; 	// t는 시작 정점
    V(T)={ i };  // 최소비용 신장 트리
    while(|T|<n-1) do {
    	if(select least-cost(u,v) such that u ∈ V(T) and v !∈ V(T) then{
        	T <- T U {{u,v}};
            V(T) <- V(T) U {v};
        }
        else{
        	print("no spanning tree");
            return T;
        }
    }
    return T;

3. Sollin 알고리즘

   i) 방법: 한 단계마다 여러개 간선 선택, 구축 과정 중 중복 선정된 경우 하나의 간선만 사용

   ii) ① n개의 트리로 구성된 신장 포리스트에서 시작 -> ②매번 포리스트에 있는 트리마다 하나의 간선을 선택 -> ③선정된 간선들은 각각 두개의 트리를 하나로 결합 

Sollin(G,n)
					// G=(V,E), n=|V|
	So <- {0}, S1 <-{1}, ..., Sn-1 <- {n-1}; // n개의 노드그룹으로 초기화
    T <- ＠, Edges <- E(G)					// 최소비용신장트리
    List <- @;
    while(|T|<n-1 and Edges != @) do {
    	for(each Si) do {
        	select least-cost(u,v) from Edges such that u∈S and v!∈S;
            if((u,v)!∈List) then List <- List U {{u,v}}; // 중복 간선 제거
        }
        while(List!=@) do{  // 리스트가 공백이 될때까지
        	remove (u,v) from List;
            if({u,v}!⊂Su or {u,v}!⊂Sv) then{  // Su와 Sv는 각각 정점 u와 v가 포함된 트리
            	T <- T U {(u,v)};
                Su <- Su U Sv;
                Edges <- Edges -{(u,v)};
            }
        }
    }
    if((|T|<n-1) then {
    	print("no spanning tree");
    }
    return T;

 

---

1. 최단 경로

① 하나의 정점에서 다른 모든 정점까지의 최단경로

시작점 v에서 G의 나머지 모든 정점까지 최단경로를 찾음

(간선들의 가중치 합이 최소가 되는 경로)

 

방향그래프 G=(V,E), weight[i,k]>=0

 

 

 

② 하나의 정점에서 다른 모든 정점까지의 최단경로

  i) Dijkstra 최단 경로 알고리즘 원리: S(최단경로 발견된 정점 집합), weight[i,j](아크<i,j>가중치), Dist[i](S에 속하지 않은 i     에 대해 v에서 S에 있는 정점들만 거쳐 정점i에 이르는 최단 경로의 길이)

  ii) 절차: S에서 시작점 v포함(Dist[v]=0) -> 최근에 S에 첨가한 정점을 u로 설정 ->

              u의 인접 정점 중 S에 포함되지 않은 w에 대해 Dist[w] 계산(Dist[w]=min{Dist[w], Dist[u]+weight[u, w]}) ->

             S에 포함되지 않은 모든 정점 W중 dist[W]가 가장 작은 정점을 S에 첨가

    iii) Dijkstra의 최단 경로 알고리즘: G의 n개의 정점을 0~n-1번호 부여, S[] - i∈S, S[i]=true 혹은 S[i]=false로 표기

        - weight[n, n]: 가중치 인접행렬(아크<i,j>가 그래프에 x일땐 아주 큰 값으로 표현)

shortedPath(v, weight, n)
					// v는 시작점, weight는 가중치 인접행렬, n은 정점 수
	for(i<-0; i<n; i<-i+1) do { // create
    	S[i] <- false;   		// S를 초기화
        Dist[i] <- weight[v,i]; // Dist를 초기화
    }
    S[V] <- true;
    Dist[v] <- 0;
    
    for(i<-0; i<n-2; i<-i+1) do{
    	select u such that Dist[u] = min{Dist[j]|S[j]=false and 0<=j<n;
        S[u] <- true;
        for(w<-0; w<n; w<-w+1) do { // 확정x 경로 다시 계산
        	if(S[w]=false) then {
            	if(Dst[w]>(Dist[u] + weight[u,w])
                	then Dist[w] <- Dist[u] + weight[u,w];
            }
        }
    }

  ③모든 정점 쌍의 최단경로

    i) D^k[i,j]: 정점 i에서 j까지 최단경로 나타냄(정점 인덱스가 0~k까지인 정점만 중간 정점으로 이용)

    ii) D^k[i,j] <- min{D^k-1[i,j], D^k-1[i,k]+D^k-1[k,j]}, k≥0

        - 정점 k가 최단경로에 포함x -> D^k[i,j] = D^k-1[i,j]

        - 정점 k가 최단경로에 포함o -> (i,k),(k,i) 둘다 최단 거리, D^k[i, j] = D^k-1[i, k]+ D^k-1[k, j]

    iii) D의 역[i,j] = weight[i,j]

allShortesPath(G, n)
						// G = (V,E), |V|=n
	for(i<-0; i<n; i<-i+1) do 
    	for(j<-0; j<n; j<-j+1) do 
        	D[i,j] <- weight[i,j]; // 가중치 인접행렬 복사
            
            
     for(k<-0; k<n; k<-k+1) do			// 중간 정점으로 0에서 k까지 사용하는 경로
     	for(i<-0; i<n; i<-i+1) do		// 모든 가능한 시작점
        	for(j<-0; j<n; j<-j+1) do	// 모든 가능한 종점
            	if(D[i,j]>(D[i,k]+D[k,j])) then
                	D[i,j] <- D[i,k]+D[k,j];	// 짧은 경로가 있는지 검사

---

1. 이행적 패쇄

  ① 가중치가 없는 방향 그래프에서 임의의 두 정점 i~j까지 경로가 존재하는지 표현

  ② 이행적 패쇄 행렬(D+): D+[i,j]=1(정점 i~j까지 길이가 0보다 큰 경로 존재)

  ③ 반사 이행적 패쇄 행렬(D*): D*[i,j]=1(정점 i~j까지 길이가 0 이상인 경로 존재)

D+: allShortesPath 알고리즘 이용

  - 간선<i,j>  o-> D의 역[i,j]=1,

                    x-> D의 역[i,j]=∞  으로 초기화

 

D*: allShortesPath 알고리즘 이용

   - D+에서 D+[i,i]값을 1로 만듦

 

불리언 행렬 사용: 인접행렬과 D+를 true, false값 갖는 행렬로 만듦

  - Dk[i, j] ← Dk-1[i, j] OR (Dk-1[i, j] AND Dk[k, j]), k≥0