최단 경로 알고리즘

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다.

• 다양한 문제 상황

1. 한 지점에서 다른 한 지점까지의 최단 경로

2. 한 지점에서 다른 모든 지점까지의 최단 경로

3. 모든 지점에서 다른 모든 지점까지의 최단 경로

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

4. 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산

5. 음의간선이 없을때 정상적으로 동작

6. 그리디 알고리즘으로 분류
   -매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복

• 알고리즘의 동작 과정

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

코드 풀이)

입력 값설정과 기본 제원 값들을 입력해준다.

방문하지 않은노드의 최단거리 값의 인덱스를 출력 하는 함수 설정 - 동작과정 3번

동작과정 3번은 통해 얻은 노드를 하나씩 방문하며 최단거리를 구한다.

이와 같이 한다면 전체 시간복잡도는 O(v^2)이다. v= 노드의 개수
(노드의 개수가 5000개 이하일때 위와 같이 할수있음)

더 많은 노드가 있을경우 더 효율적으로 해야한다.

• 우선순위 큐
  우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

우선순위 큐를 구현하기 위해서는 heap을 사용해야한다.

heap 코드 예시)

파이썬에서는 heap 라이브러리를 사용할경우 오름차순으로 실행된다.

내림차순으로 하고싶다면

넣을때 값 과 꺼낼때 heapq 에 - 를 해주면 내림차순으로 할수있다.

heapq 를 사용한 다익스트라 알고리즘 코드)