다익스트라 알고리즘 (Dijkstra Algorithm) 개념정리

다익스트라 알고리즘이란?

다익스트라 알고리즘같은 경우에는 가중치가 있는 그래프의 최단경로를 찾을 때 사용 된다.

 

1. 다익스트라 알고리즘은 연결 단순 비방향성 가중치 그래프에서 두 정점 간의 최단경로의 길이를 구한다.

2. 다익스트라 알고리즘은 연결 단순 비방향성 가중치 그래프에서 두 정점 간의 최단경로의 길이를 구하는데 O(n*n) 연산을 사용한다.

위키백과 사전 - 다익스트라 알고리즘

 

구현

<필수변수> 

Vertax 갯수

Edge 갯수

vertax1 ~ vetax (연결) , 가중치

 

위의 변수와 우선순위큐를 이용해서 다익스트라 알고리즘을 구현할 수 있다.