노트

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Dijkstra(다익스트라) 알고리즘 어떤 변수 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다.다익스트라 알고리즘은 각각의 꼭지점 v에 대해서 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다.알고리즘 시작 시에 d[s] = 0이고, s가 아닌 다른 모든 꼭지점 v에 대해서는 d[v] = ∞ 로 놓아 다른 꼭지점에 대해서는 아직 최단 경로를 모른다는 사실을 표기한다.알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.출처 : 위키백과 - 음수 가중치가 없다고 가..