[알고리즘 이론] 14. 최단거리

최단 거리

• 그래프 최단 거리 구하는 알고리즘이다.

1. 다익스트라 알고리즘

• 그래프의 최단 경로 구하는 알고리즘.
• 하나의 정점에서 출발하는 최단 거리를 구함(출발지만 정함)
• 음수 가중치 없어야 함
• 인접 행렬로 표현된 그래프의 경우 시간 복잡도 : O(n^2)
• 우선순위 큐를 사용하여 시간 복잡도를 O(mlogn)까지 낮출 수 있다 -> 개선된 다익스트라 알고리즘
• 탐욕법과 동적 계획법 사용

원리

• 자세한 원리는 아래 게시글 참조
• https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

알고리즘 문제 추천

1. 녹색 옷 입은 애가 젤다지? (골드 4)

• https://www.acmicpc.net/problem/4485

2. 최단경로 (골드 4)

• https://www.acmicpc.net/problem/1753

3. 특정한 최단 경로 (골드 4)

• https://www.acmicpc.net/problem/1504

4. 미확인 도착지 (골드 2)

• https://www.acmicpc.net/problem/9370

2. 벨만-포드 알고리즘

• 그래프의 최단 경로 구하는 알고리즘
• 하나의 정점에서 출발하는 최단 거리를 구함(출발지만 정함)
• 음수 사이클 없어야함(음수 가중치 허용)
• O(nm) 시간 복잡도를 가짐
• 동적 계획법, relaxation 기법 사용

원리

• 자세한 원리는 아래 게시글 참조
• https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

알고리즘 문제 추천

1. 타임머신 (골드 2)

• https://www.acmicpc.net/problem/11657

3. 플로이드-와샬 알고리즘

• 그래프의 최단 경로 구하는 알고리즘
• 모든 정점에서 모든 정점까지 최단 거리를 구함
• 음수 사이클이 없어야함(음수 가중치는 허용)
• 그래프 비용 인접 행렬로 표현되어 있다고 가정
• 시간 복잡도 O(n^3)
• 동적 계획법 사용

원리

• 자세한 원리는 아래 게시글 참조
• https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%99%80%EC%83%ACFloyd-Warshall-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

알고리즘 문제 추천

1. 플로이드 (골드 4)

• https://www.acmicpc.net/problem/11404

참고 자료

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9CBellman-Ford-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java-%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%99%80%EC%83%ACFloyd-Warshall-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98