다익스트라 알고리즘(Dijkstra's algorithm) 다익스트라 알고리즘(Dijkstra's algorithm)은 벨만-포드 알고리즘처럼 특정한 노드에서 시작하여 그래프의 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라는 벨만-포드 알고리즘에 비해 좀 더 효율적이기 때문에 그래프가 큰 경우에도 사용할 수 있다는 장점이 있다. 하지만, 이 알고리즘은 음수인 가중치를 가진 간선이 있는 경우에는 사용할 수 없다는 단점이 있다. 다익스트라 알고리즘도 벨만-포드 알고리즘처럼 각 노드까지의 거리를 저장하고 탐색 과정에서 값을 줄여나간다. 각 단계에서는 아직 처리하지 않는 노드 중 거리가 가장 작은 노드를 찾고, 그 노드에서 시작하는 모든 간선을 쭉 살펴보며 노드까지의 거리를 줄일 수 있다면 줄인..
벨만-포드 알고리즘(Bellman-Ford algorithm) 벨만-포드 알고리즘은 시작 노드에서부터 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 이 알고리즘으로 길이가 음수인 사이클을 포함하지 않는 모든 종류의 그래프를 처리할 수 있다. 그래프에 음수 사이클이 있는 경우에는 이를 찾아낼 수도 있다. 이 알고리즘에서는 시작 노드에서 다른 모든 노드까지의 길이를 모두 추적한다. 거리의 초기값은 시작 노드의 경우 0이고 다른 모든 노드의 경우 무한대의 값으로 설정된다. 그리고 이 값을 계속해서 줄여나가는 과정을 더는 줄일 수 있는 값이 없을 때까지 반복한다. 초기 시작 거리가 1인 노드 탐색 거리가 2인 노드 탐색 거리가 3인 노드 탐색 위와 같은 식으로 거리를 줄여나간다. 이후에 거리를 더 줄..
