목록IT/알고리즘 (1)

개발자 강경완

다익스트라 알고리즘

1. 개요다익스트라 알고리즘은 1959년 다익스트라(Dijkstra)가 고안해낸 단일 출발점 최단경로 알고리즘이다. (Single-Source Shortest Paths)다른 말로 가중치가 있는 방향그래프에서 임의의 두 노드 사이의 최단거리를 찾는 알고리즘이다. 많은 다익스트라 알고리즘 중 가장 유명한 알고리즘이며, 최근에는 네트워크인 라우터가 패킷을 빠르게 전송하기 위해 다익스트라 알고리즘을 채택했다고 한다. 2. 알고리즘 A에서 F로 가는 최단거리를 찾아보자. 1. 초기화시작 노드의 거리값은 0으로, 다른 노드들은 무한대로 초기화한다. 2. 루프문제가 해결이 될 때 까지 무한루프를 돌며 다음 최소 값을 찾는다.위의 상황에서 A가 출발점이고, A가 갈 수 있는 곳은 B C D이다.그러므로 B를 10으로..
IT/알고리즘 2015. 12. 11. 01:09
Prev 1 Next