7W.1D-최단경로

>최단경로

가장 짧은 경로를 찾는 알고리즘

다양한 문제상황
1.한 지점에서 다른 한 지점까지의 최단경로
2.한 지점에서 다른 모든 지점까지의 최단경로
3.모든 지점에서 다른 모든 지점까지의 최단경로
각 지점은 그래프에서 노드로 표현
지점 간 연결된 도로는 그래프에서 간선으로 표현

다익스트라 최단경로 알고리즘

특정노드에서 출발->다른 모든 노드
음의 간선이 없을때 정상적으로 동작
그리디 알고리즘으로 분류->매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
a->b->c: a->b, b->c
한 번 처리된 노드의 최단 거리는 고정되어 바뀌지 않음

동작과정

1.출발노드 설정
2.최단거리 테이블 초기화
3.방문하지 않은 노드 중에서 거리가 가장 짧은 노드 선택->그리디
4.해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블 갱신
5. 3,4번 반복
-더 짧은 경로를 찾으면 데이터 갱신

우선순위 큐

우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
표준라이브러리형태:Heap (Max Heap, Min Heap)
단계마다 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 이용함.
현재의 최단거리가 가장 짧은 노드를 선택->최소힙

최소힙

최대힙

부호를 바꿔준다.(-value)

플로이드 워셜 알고리즘

모든 노드에서 다른 노드까지의 최단경로를 모두 계산

단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행->매 단계마다 방문하지 않은 노드중 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않음
플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장
플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속함

a에서b로 가는 거리는 기존의 a에서 b로 가는 최단거리 값과 a에서 k로 가는 값+ k에서 b로 가는 값을 비교하여 더 작은 값으로 최단거리를 찾는다.