??? : 세상은 최단 경로만 기억해!(?) 최단 경로 구하기 기릿!
📖 최단 경로를 구하는 알고리즘
✅ 출발지부터 도착지까지 최단 거리/최소 비용을 지불하는 경로 구하기
✅ 최단 경로를 구하는 알고리즘 중 대표적 두 가지 : 플로이드 와샬 알고리즘 , 다익스트라 알고리즘
1. 플로이드 와샬 알고리즘
✅ 존재하는 모든 노드를 최소 비용으로 방문하는 최단 경로 탐색
✅ 모든 정점에서 모든 정점으로
✅ 동적 계획법(dynamic programming)에 의거
ㄴ 거쳐가는 정점을 기준으로 최단 거리 구함
ㄴ 전체 노드 연결 최단 거리 연산
구현 방법
- 비용 배열과 방문 배열 선언
- 비용 배열에는 maxsize 값을, 방문 배열에는 false 값을 넣어 초기화
- 시작 노드를 정하고, 시작 노드 인덱스의 비용 배열 값은 0, 방문 배열 값은 true로 갱신
- 해당 노드에서 이동 가능한 노드 인덱스의 비용 배열 값 (각각의 이동 비용으로)갱신
- 그 중에서 가장 작은 값을 갖는 노드로 이동, 해당 노드 인덱스의 방문 배열 값 true로 갱신
- 이동한 노드에서 이동 가능한 노드 인덱스의 비용 배열 값 갱신,
maxsize가 아닌 값이 있다면 바로 전 노드에서 해당 노드로 이동하는 비용만 고려하여 더 작은 값으로 갱신 - 이동 가능한 노드 중에서 이동 비용이 가장 작은 노드로 이동, 방문 배열 값 갱신
- 방문 배열 값이 모두 true가 될 때까지(=모든 노드를 방문할 때까지) 위 과정 반복
- 비용 배열에 있는 모든 값을 더해 최단 거리 방문시 필요한 비용 연산
2. 다익스트라 알고리즘
✅ 특정 노드에서 다른 노드까지의 최단 경로 탐색
✅ 특정 정점에서 각각의 다른 정점으로
✅ 동적 계획법(dynamic programming) 활용, 대표적인 최단 경로 탐색 알고리즘
= 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문
❌ 음의 간선은 포함할 수 없음
ㄴ 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 사용, 갱신
ㄴ 출발점 ~ 다른 노드 최단 거리 연산
구현 방법
- 비용 배열과 방문 배열 선언
- 비용 배열에는 maxsize 값을, 방문 배열에는 false 값을 넣어 초기화
- 출발점 노드를 정하고, 시작 노드 인덱스의 비용 배열 값은 0, 방문 배열 값은 true로 갱신
- 해당 노드에서 이동 가능한 노드 인덱스의 비용 배열 값 (각각의 이동 비용으로)갱신
- 그 중에서 가장 작은 값을 갖는 노드로 이동, 해당 노드 인덱스의 방문 배열 값 true로 갱신
- 이동한 노드에서 이동 가능한 노드 인덱스의 비용 배열 값 갱신,
maxsize가 아닌 값이 있다면 누적 비용을 계산하여 더 작은 값으로 갱신 - 이동 가능한 노드 중에서 이동 비용이 가장 작은 노드로 이동, 방문 배열 값 갱신
- 방문 배열 값이 모두 true가 될 때까지(=모든 노드를 방문할 때까지) 위 과정 반복
- 비용 배열의 각 값이 출발점 노드로부터 해당 인덱스 노드까지 이동하는 최소 비용
사부작 사부작