그리디 알고리즘(3)[ShortestPath(G,s)]

ShortestPath(G,s)

입력 : 가중치 그래프 G=(V,E), |V|=n(점의 수), |E|=m(간선의 수)

출력*: 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D

1 배열 D를 ∞로 초기화시킨다. 단, D[s]=0으로 초기화한다.

   // 배열 D[v]에는 출발점 s로부터 점v까지의 거리가 저장된다.

2  while(s로부터의 최단 거리가 확정되지 않은 점이 있으면) {

3      현재까지 s로부터 최단 거리가 확정되지 않은 각 점 v에 대해서

        최소의 D[v]의 값을 가진 점 vmin을 선택하고, 출발점 s로부터 

        점 vmin까지의 최단 거리 D[vmin]을 확정시킨다.

4      s로부터 현재보다 짧은 거리로 점 vmin을 통해 우회 가능한 각 점 w에 대해서 D[w]를 갱신한다.

     }

5  return D

 

1. 서울 빼고 다 ∞로 초기화

2. ∞에서 기존 거리로 갱신이 안된 점이 없을 때까지 반복.

3.  모든 경로의 점들 집합인 V 에서, 최단거리가 확정된 점들의 집합인 T를 빼면 차집합이다.

     이 차집합은  갱신이 안된 거리의 집합 V- T가 된다.

이 V-T에서 D[v](경로 값)가 최소값인 점 vmin을 선택하고, 그 vmin의 경로 값을 최단거리로 확정시킨다. 

 

4. V-T에 속한 점들 중 vmin을 거쳐 감으로써 s로부터의 거리가 더 짧아지는 점w가 있다면 그 점의 D[w]을 ∞에서 경로(w점의 고유 값) 값으로 갱신한다.

 

5. 배열 D를 리턴한다.

 

---

서울 기준으로 계속 누적값을 D[s]에 쌓는다.

광주 오는데 대전을 거쳤다면 '(서울에서 대전 가중치) + (대전에서 광주 가중치)'가 서울과 광주의 D[s]. 

광주까지 왔는데 그 누적값보다 서울에서 원주의 가중치가 작으면

서울에서 원주. 그리고 목적지로의 새로운 루트가 만들어지는 것

 

그리고 각 점들마다

'서울로 부터의 누적값 + 지금 점부터 다음 목적지 간선의 가중치 값'이 제일 작은 간선을 계속 선택해서 최소의 누적값을 만든다.

 

한 루트라도 목적지에 다다르면 그 루트의 누적값을 출력한다. 이 누적값이 서울에서 목적지 까지의 최소 누적값이다.