자료구조 스터디 6주차

섹션 6) 다익스트라에서 최소 신장 트리까지

1.다익스트라 알고리즘

시작 노드와 그 외 노드들 간의 최단 거리를 구하는 알고리즘.

엣지는 항상 양수여야 한다.

 

<알고리즘 핵심 이론>

 

1. 인접리스트로 그래프 구현하기 (각 노드에서 갈 수 있는 노드와 가중치를 리스트 원소로)

(인접행렬로도 구현 가능하지만 시간복잡도 측면에서 인접리스트로 구현해주도록 한다.)

2. 최단거리 배열을 초기화한다. (시작노드는 0 나머지는 무한대)

3. 값이 가장 작은 노드 고르기(처음은 시작노드가 된다)

4. 최단거리 배열 업데이트하기

5.모든 노드가 처리될때까지 3, 4 반복. 방문 배열을 만들어 재방문이 일어나지 않도록 한다.

 

2.벨만포드

그래프에서 최단거리를 구하는 알고리즘.

출발 노드에서 다른 노든까지의 최단 경로 탐색.

엣지는 음수여도 된다.(음수 사이클 판단 가능)

엣지를 중심으로 판단

엣지 리스트를 구현한다.

 

<알고리즘 핵심 이론>

 

1. 그래프를 엣지 리스트를 구현하고 최단 경로 리스트를 시작 노드는 0 나머지는 무한대로 초기화

2. 모든 엣지를 확인해 노드의 개수 확인하기.업데이트의 반복횟수는 노드개수-1(노드의 개수는 n개 엣지의 개수는 n-1개)

값이 무한대이거나 저장된 값이 계산 값보다 크다면 계산된 값으로 업데이트 해준다.

3.음수 사이클 여부를 확인한다.

 마지막 n번 업데이트를 통해 실제 업데이트가 일어난다면 음수사이클이 존재한다는 의미임.

 

벨만 포드 알고리즘은 최단 거리를 구하기 보다는 음수 사이클 존재 여부를 확인하는 문제로 더 많이 사용된다.

최단거리 알고리즘 중 유일하게 음수사이클에 대해 다룸

 

3.플로이드 워셜

그래프에서 최단거리를 구하는 알고리즘

모든 노드에 관한 경로탐색

음수가중치가 있어도 되나 음수 사이클이 존재하면 안된다.

시간복잡도는 o(log(n^3))으로 매우 큰 시간복잡도의 알고리즘이다.

만약 주어지는 데이터가 작다면 사용을 고려해봐도 되지만 아닌 경우엔 다른 알고리즘을 변형하여 이용해주도록 한다

 

1.인접행렬로 그래프를 구현

작은 데이터로 수행을 가정하기 때문에 인접행렬을 사용해주어도 괜찮다.

2.최단거리 리스트에 그래프데이터를 저장

3.점화식으로 리스트를 업데이트

 3중 for문을 이용. 

for 경유 노드 k에 대해 (1~n):
      for 시작노드 s에 대해  (1~n):
            for 도착노드 e에 대해  (1~n):
                  d[s][e] = Math.min( d[s][e], d[s][k] + d[k][e] )

 

위 for문 형식을 외워서 사용해주도록 한다..

 

 

4.최소신장트리

그래프의 모든 노드를 연결할 때 사용된 엣지들의 합의 최솟값으로 하는 알고리즘

사이클이 포함되면 가중치의 합이 최솟값이 될 수 없으므로 사이크으 포함하지 않는다.

 

<알고리즘 핵심 이론>

1.엣지리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화.

인접리스트가 아니라 엣지 리스트의 형태로 그래프를 저장.

2.그래프를 가중치 기준으로 오름차순 정렬해준다.

3.가장 가중치가 낮은 엣지부터 연결을 시도한다.노드를 연결했을 때 사이클이 생기지 않도록 사이클이 없을 경우에만 union연산을 시행해준다.

4.사용한 엣지의 개수가 n-1개가 될 때 까지 수행해준다.