[알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 그래프에서 정점 사이의 최단 경로를 찾는 알고리즘 입니다. 프림 알고리즘과 동작방식이 비슷하지만 다익스트라 알고리즘은 시작 정점에서 정점 V 까지의 경로의 길이를 기준으로 최단 경로를 연결합니다. (단 가중치가 음수인 경우 사용할 수 없습니다.) 다익스트라 알고리즘은 다음과 같은 원리로 동작합니다. 시작 정점으로부터 각 정점까지의 경로의 길이를 저장할 배열을 만들고 모든 정점을 ∞(무한대)으로 초기화 시작 정점의 경로의 길이를 0으로 초기화하고 시작 정점을 최단 경로에 추가 최단 경로에 추가된 정점의 인접한 정점을 확인해서 경로의 길이를 갱신하고 최단 경로에 추가. (단 추가하려는 정점이 이미 최단 경로 안에 존재할 경우 경로의..