DFS와 BFS

DFS : http://blog.eairship.kr/268

BFS : http://blog.eairship.kr/269

Advertisements
DFS와 BFS

다익스트라 알고리즘

다익스트라 알고리즘은 방향성 있는 그래프에서 임의의 두 노드 간의 최단 거리(간선의 가중치 합)이 가장 적은 경로를 찾는 알고리즘이다. 알고리즘의 기본 구조는 간단하다. 만약 내가 시작 노드 s부터 현재 노드 u까지의 최간 거리 d(u)을 알고 있고, u에서 다음 노드 v까지의 거리 w(u,v)가 주어진다면, s부터 v까지의 거리는 d(u) + w(u,v)가 될 것이다. 그런데, s에서 v까지 갈 때 꼭 u를 거치라는 법은 없다. 다른 경로를 통해서도 s에서 v에 도달할 수 있다. 이  렇게 다른 노드를 거쳐서 v까지 가는 거리 d(v)가 d(u)+w(u,v) 보다 길다면 d(v) 값을 새로 계산한 d(u)+w(u,v)로 갱신한다. 반대로 d(v)가 더 짧다면 이번에 계산한 d(u)+w(u,v)값은 폐기하면 된다.

 

http://trowind.tistory.com/80

http://thinkberry.co.kr/textyle/3376

 

 

다익스트라 알고리즘