다익스트라

다익스트라 알고리즘

시작노드에서 다른 임의의 노드까지의 최단 경로를 찾는 알고리즘이다.

 

최단 경로 찾기 문제에는 BFS을 활용한 알고리즘도 존재하지만 BFS는 노간간의 간선의 비용이 존재하지 않을 경우(모두 같을 경우) 사용되는 반면, 다익스트라 알고리즘은 간선의 비용이 모두 제 각각일 때 사용된다.

• 간선이 비용이 모두 다를 때의 최단 거리 알고리즘은 다익스트라 알고리즘뿐만 아니라 프로이드 워셜 알고리즘도 존재한다. 프로이드 알고리즘은 한가지의 시작노드만 계산하는 것이 아니라 모든 노드에서 출발하여 모든 노드로 가는 각각의 최단 경로를 구할 수 있다. 하지만 시간 복잡도가 O(N^3) 으로 높다.

heapq 라이브러리를 사용하여 우선순위 큐를 이용한다. - 파이썬은 최소힙으로 구현되어있다.

 

필요한 구조

-최단거리 테이블

-각 노드별 간선 정보 테이블

-우선순위 큐

 

1. 최단거리 테이블 (distance) 을 모두 INF 값으로 초기화 시켜준다.
2. 노드별 간선 정보를 담을 리스트(graph)를 생성한다.
3. graph 리스트에 (a - 시작노드, b - 도착노드, c - 비용) 간선 비용 정보들을 추가한다.
4. ex) 시작:1번 노드, 도착:3번노드, 비용:3 → graph[1].append(3,3)
5. 이를 반복하여 간선의 정보들을 모두 입력받는다.

-다익스트라 함수 구현

-순서

1. 출발 노드를 설정한다.
2. 우선순위 큐에 현재노드와 간선비용0 (현재노드에서 현재노드까지 비용은 0 이므로) 정보를 삽입한다. - (0,start노드)
3. distacne 리스트에 현재 노드까지의 값을 0 으로 초기화 INF → 0
4. 우선순위 큐에서 원소를 꺼내어 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. - 이미 방문한 노드라면 무시
5. graph 리스트에서 해당 노드의 간선정보를 얻어 현재노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
6. 해당 노드와 연결된 간선 비용과 현재 누적 거리를 합하여 큐에 push한다. - (비용,노드)
7. 위 과정에서 3,4,5번을 반복한다. - 큐가 빌때까지

모두 완료하면 distance 리스트에는 시작노드부터 각각의 노드까지의 최단거리 정보가 존재할 것이다.

distacne 리스트 원소들을 꺼내어 확인한다.