개요
그래프가 주어질 때, 특정 Node A, B 사이의 최단거리를 구하는 알고리즘으로 Dijkstra Algorithm과 Bellman-Ford Algorithm이 있다.
Dijkstra Algorithm
Dijkstra 알고리즘은 음의 간선이 없는 그래프에서의 최단거리를 구하는 알고리즘에 사용한다.
이를 위해 hashtable 2개를 사용하는데, 하나는 시작점으로부터의 최단거리를 저장하고 나머지 하나는 방문했는지 여부를 저장하는 용도이다.
Dijkstra Algorithm pseudo code는 다음과 같다.
1. 최단거리 hashtable에서 시작점에 대한 entry를 0으로 두고, 나머지는 무한으로 설정한다.
2. 시작점을 방문한다.
3. 방문 노드 주변의 노드와 주변 간선 정보를 이용하여, 최단거리 hashtable을 업데이트한다.
4. 방문 노드를 방문했다고 표시한다.
5. 방문하지 않은 노드 중 시작점과 최단거리인 노드를 방문한다. 그리고 3번으로 되돌아가 반복한다.
6. 모든 노드를 방문한 이후에는 최단거리 hashtable에 있는 값이 진짜 최단거리 만을 저장하고 있을 것이다.
출처: https://medium.com/@chuncaohenli/animated-algorithm-a9fa339d44c
Bellman-Ford Algorithm
벨만 포드 알고리즘은 음의 간선에 대해서도 적용 가능한 알고리즘이고, 음의 값을 가지는 순환이 있는지도 판별할 수 있다.
최단거리를 저장하는 hashtable 하나만 있으면 된다.
Bellman-Ford Algorithm pseudo code는 다음과 같다.
시작점을 A라고 가정하자.
1. 최단거리 hashtable에서 시작점에 대한 entry를 0으로 두고, 나머지는 무한으로 설정한다.
for i in range(V-1):
모든 edge를 순회하며, 최단거리 hashtable을 업데이트 한다.
이 과정이 모두 끝나면, 최단거리 hashtable에 있는 값이 진짜 최단거리만을 저장하고 있을 것이다.
그런데 위 iteration을 한번 더 거쳤을 때, hashtable 값이 변했다면, 음의 값을 가지는 순환이 있다는 뜻이다.
출처: https://www.prepbytes.com/blog/graphs/bellman-ford-algorithm/
KAIST CS Major