최단거리 찾기(Shortest Path)
하나의 노드쌍에서 최단 거리를 찾습니다.
길찾기 알고리즘은 19세기 부터 유래를 찾을 수 있고, 1956년 Edsger Dijkstra(다익스트라, 데이크스트라)가 가장 유명한 알고리즘을 만들었으며, 대체루트 찾기로 유명해졌습니다. 이 알고리즘을 이해해 보도록 하겠습니다.
위의 움짤을 하나씩 그려가면서 이해해보도록 하겠습니다.
그래프의 구성
그래프의 기본 구성은 다음과 같습니다. 6개의 노드와 8개의 엣지로 이루어져 있습니다. 실생활에 대응해서 생각해본다면 6개의 도시와 이 도시들을 잇는 8개의 도로망이라고 생각해도 됩니다. 그리고 8개의 엣지 위의 값은 거리라고 생각합시다. 최단거리 = 최소 걸리는 루트 라는 공식을 성립하게 하기 위해, 도로체증, 신호 등등의 조건들은 무시하도록 합시다.
시작점과 도착점 설정
위의 움짤에서 보면, 1번은 시작점 5번은 도착점이 되었습니다. 우리 실생활로 따진다면, 1번은 서울 5번은 부산으로 칭한다고 해도 큰 무리는 없을 것입니다.
모든 값을 무한대(∞)에 놓기
우리 눈엔 대략적으로 거리들을 계산할 수 있지만, 아직 시작점으로부터의 각 거리가 계산되지 않은 상태입니다. 이렇게 정해놓는것이 직관적이지 않을것입니다. 저도 그렇게 느낍니다. 우리가 컴퓨터라고 생각한다면 이해가 좀더 쉬울 것 같습니다. 컴퓨터는 한번에 하나의 동작만 합니다. 그래서 위의 네트워크를 그리라고 한다면 컴퓨터는 정말로 그리기만 합니다. 우리는 그리면서 계산을 동시에 하는것과는 다르게 말이죠. 그래서 계산을 하기전에 준비과정이 필요한 것으로 이해하면 되겠습니다. 무한대라는 값으로 놓은 이유는 이후에 새로운 값을 찾고, 이 값이 기존의 값보다 작은 경우에 업데이트 하기 때문입니다.
1번 부터 계산 시작
1번부터 인접한 거리를 하나하나 계산하고, 그 거리값을 노드의 오른쪽 위에 표시합시다. 1번은 자기자신이기 때문에 거리는 0이 됩니다. 그럼 2,3,6을 계산합시다.
2,3,6번은 바로 인접하여 있기 때문에 엣지 위의 값과 동일하게 됩니다. 그럼 각 과정을 각 노드에 대해서 진행해보도록 합시다.
2번과 인접한 노드들
내용이 조금씩 복잡해지고 있기 때문에, 기준 색깔을 정하도록 하겠습니다. 노드 색상은 총 3가지. 지나감, 기준점, 인접노드 입니다. 지나감은 이미 계산의 기준점이 된 노드입니다. 기준점은 앞으로의 계산을 할 위치로서, 이로부터 한칸 떨어져있으며 지나감에 해당하지 않는 노드들이 인접노드가 됩니다.
글씨는 계산 기준으로 세가지가 됩니다. 거리를 계산한 결과 및 결과를 위해 근거값이 되는 색상, 계산결과 기존 값이 유지되는 색상, 계산결과 업데이트 되는 색상 이렇게 3가지 입니다.
3번 노드 거리구하기
3번 노드의 경우, 1번에 인접한 노드였기 때문에 기존에 9라는 거리값을 가지고 있었습니다. 3번은 2번의 인접노드 이기 때문에 2번 기준으로 계산을 거쳐야 합니다. 3번에 대한 거리를 1번을 기준으로 그리고 2번을 거쳤을때의 거리를 계산하고 비교하여 더 작은 값을 해당 거리값으로 업데이트 하면 됩니다.
1번으로 3번까지 바로 거리 = 9
1 ->2 -> 3 으로 거리 = 7 + 10
∴ 9< 7+10 이므로 기존의 값 유지함.
4번 노드 거리구하기
4번의 경우 아직 한번도 도달한 적 없기 때문에, 여기서 계산된 7+15 = 22 로 최소값이 됩니다.
3번 기준으로 계산하기
앞의 과정의 반복입니다. 3번을 기준으로 계산해봅시다.
3번 기준이기 때문에 우리가 계산해야할 노드의 거리값은 6번과 4번입니다.
6번 노드 계산하기
6번 노드는 기존에 1번의 인접 노드로 14라는 값을 가지고 있었습니다. 하지만 9+2 =11 이 더 작기 때문에, 6번 까지의 거리는 11로 업데이트 됩니다.
4번 노드 계산하기
4번 노드는
1-> 2 -> 4 = 22
1 -> 3 -> 4 = 20
∴ 9+11< 22 이므로 업데이트.
와 같이 됩니다. 표현상 중간 엣지들을 다시 계산하는 것처럼 썼지만, 실제 컴퓨터 계산에선 다시 계산하지 않고 노드 또는 리스트 안에 저장 되어있을 것입니다. 그러므로 앞으론 기준점의 값에 인접노드로 가는 값만 더함으로 최소 거리를 구할 수 있습니다.
3번 기준 계산결과
다음과 같이 인접한 노드들은 계산값이 달라지는 것을 볼 수 있습니다. 앞으로 계산은 비슷함으로 설명 보단 그림 위주로 하겠습니다.
6번 기준으로 계산하기
기존 무한대 값보다 작기 때문에 업데이트 됩니다.
4번 기준 계산하기
4번기준으로 계산하면 26으로 20보다 큽니다. 따라서 업데이트 되지 않습니다.
최종결과
최종적으로 1번에서 5번까지 도달하는 최소 거리는 20입니다.
끝맺으며
다음과 같은 점들이 있었습니다.
- 실제 컴퓨터 계산에선, 각 노드로 가는 루트 값도 저장되면서 거리값이 계산되었을 것이지만, 위에선 그런점이 표현되지 않았습니다. 그래서 마치 루트를 다시 계산하는 것 같은 느낌은 있을거 같습니다.
- 그와 같은 맥락에서, 위 알고리즘에선 오직 최소값만 유지하는 것처럼 보입니다. 컴퓨터를 이용할때는 대체 루트의 값을 저장해 놓는다면, 유사시 사용할 수 있을 것입니다.
- en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Dijkstra's algorithm - Wikipedia
Graph search algorithm Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm)[4] is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by comput
en.wikipedia.org
- 위의 링크에서 알고리즘의 계산시간 관련된 내용은 스킵했습니다.
- 다음 번엔 알고리즘을 적용해보도록 하겠습니다.
'기타 > 프로그래밍' 카테고리의 다른 글
| [그래프 데이터베이스][무작정해보기] [6/30] A*(A-star) Algorithm 그림으로 이해하기. (0) | 2021.01.10 |
|---|---|
| [그래프 데이터베이스][무작정해보기] [5/30] Shortest Path Algorithm 사용해보기 (0) | 2021.01.03 |
| [그래프 데이터베이스][무작정해보기] [3/30] 웹상의 CSV로 부터 Graph 생성하기 (1) | 2021.01.01 |
| [그래프 데이터베이스][무작정해보기] [2/30] 저장위치 설정 / 플러그인 설치 / 앞으로 다룰 알고리즘 (0) | 2020.12.30 |
| [그래프 데이터베이스][무작정해보기] [1/30] 그래프 DB 시작: 그래프 DB란? -> Neo4j Desktop 설치 (0) | 2020.12.24 |