최소 신장 트리(그래프) // Shortest Path(Dijkstra Algorithm, 다익스트라 알고리즘)

2. Shortest Path : 그래프 내의 한 정점에서 다른 정점으로 이동할 때 가중치 합이 최소값이 되게 만드는 경로를 찾는 알고리즘

 

- Dijkstra Algorithm 

: Prim Algorithm과 동작 방식이 상당히 비슷하다. 다만 Prim Algorithm이 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지를 결정하는데 반해, 다익스트라 알고리즘은 '경로의 길이'를 감안해서 간선을 연결한다는 점이 다르다.

: 사이클이 없는 방향성 그래프에 한해서만 사용할 수 있다.

 

1) 각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 모든 정점 위에 있는 경로의 길이를 무한대로 초기화 합니다.

2) 시작 정점의 경로 길이를 0으로 초기화하고 (시작 정점에서 시작 정점까지의 거리는 0이니까요) 최단 경로에 추가합니다.

3) 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가한다. 만약 추가하려는 인접정점이 이미 최단 경로 안에 존재한다면 갱신되기 이전의 경로 길이가 새로운 경로의 길이보다 더 큰 경우에 한해, 다른 선행 정점을 지나던 기존의 경로를 현재 정점을 경유하도록 수정한다.

4) 그래프 내의 모든 정점이 최단 경로에 소속될 때까지 3)과정을 반복합니다.

 

 

 

3. Selection Sort