반응형

다익스트라 2

다익스트라 알고리즘(Dijkstra Algorithm)최단경로 알고리즘

다익스트라 알고리즘에 대한 글을 쓴지 2년이 지났네요. 그동안 이 알고리즘을 사용할 일은 없었습니다. 그리고 최근 제가 쓴 글을 다시 보는 순간 나의 글이 너무 나도 허접해 보였습니다. 공부를 해갈수록 "아는 만큼 보인다" 라는 말이 뼈속 깊이 느껴지네요. 그 당시에 제가 쓴 글은 제 머리 속 생각만 쓰기 급급했습니다. 그래서 비록 아직도 한참 모자라지만, 다익스트라 알고리즘의 핵심을 재해석 해보려 합니다. 다익스타라 알고리즘 이 알고리즘의 핵심은 토탈 가중치에 있습니다. 사실 토탈 가중치는 가중치와 같은 의미로도 쓰이지만, 토탈 가중치는 최초 시작점으로 부터의 가중치라는 뜻입니다. 어떤 사람이 A의 위치에 있고 갈 수 있는 경로가 A->B->C->D 라고 하면 각각의 경로는 가중치가 있습니다. 가중치는..

다익스트라 알고리즘

다익스트라의 핵심은 다음글을 보기 바랍니다. 2015/06/02 - [프로그래밍/알고리즘] - 다익스트라 알고리즘(Dijkstra Algorithm)최단경로 알고리즘 아래 글은 제가 오래전 다익스트라를 처음 공부할 때 쓴 글이므로 이해가지 않는 부분도 있고 많이 부족합니다. 코드만 참고하시길 바랍니다. 다익스트라 알고리즘, 이름조차 어렵다. 이 알고리즘을 이해하기위해선 깊이 우선, 너비우선 탐색을 이해해야한다. 2013/06/05 - [프로그래밍/알고리즘] - 탐색-깊이우선탐색, 너비우선탐색 2013/06/07 - [프로그래밍/알고리즘] - 위상정렬(topological sort) 다익스트라 알고리즘은 시작점을 정하고 끝점을 정하면 그 두점사이 최단거리를 구하는 알고리즘이다. 다익스트라 알고리즘의 너비우..

반응형