- Bellman-Ford algorithm
- 음의 가중치를 갖는 에지가 있을 때 사용하는 알고리즘
- 다익스트라 알고리즘은 어ㅣㄷ에서 음의 가중치를 갖는 에지가 없다고 가정할까?- 왜 모든 에지에 같은 가중치를 더해줘서 음의 가중치인 에지를 없애면 안되는 걸까?
- 경로마다 포함하는 에지의 수가 다를 수 있다.
- 에지의 개수만큼 값이 배수로 증가하기 때문에 최단경로가 바뀔 수 있다.
- 핵심 아이디어
- 최단경로는 사이클을 포함할 수 없기 때문에, 최대 V-1개의 에지만 사용할 수 있다.
- 시작 노드부터 에지 1개를 이용해서 도달할 수 있는 노드들과 그 때의 최단거리를 구한다.
- 최단거리가 구해지면 끝에서부터 1칸씩 시작점으로 가까워지면서 최단거리를 구한다.
- 정확도 및 시간 분석
- 정확성
- 알고리즘 동작과정에서 자명함- 만약(노드의 갯수)-1개만큼 에지를 사용하여 최단 경로를 구한 후, 에지를 하나 더 추가하면 최단 거리가 바뀐다면 이 그래프는 음의 가중치를 갖는 사이클이 존재한다.
- 시간분석
- 매 라운드마다 모든 에지를 점검해야 하고, 총 라운드의 수는 V-1이므로 O(VE), E는 최대 V^2
-각 노드마다 매 순간 최단 거리를 저장해야 하므로 공간복잡도는 O(V)
- Floyd-Warshall Algorithm
- 시작노드와 도착노드 수에 따른 알고리즘 구분
- 시작 노드 하나, 도착 노드 하나 - Dijkstra's 알고리즘, Bellman-Ford 알고리즘- 시작 노드 하나, 도착 노드 전체 - 위 알고리즘을 모든 노드에 적용
- 시작 노드 전체, 도착 노드 하나 - 그래프의 에지방향을 모두 반대로 바꾸면 시작 노드 하나, 도착 노드 전체 문제로 바뀜
- 시작노드 전체, 도착 노드 전체
- 모든 노드 하나 하나를 시작점으로 보고 Dijkstra알고리즘, Bellman-Ford 알고리즘 적용 - 모든 노드를 v1...vn으로 이름매김
- 다음 단계를 차례로 진행
- 중간에 지나갈 수 있는 노드들을 하나씩 늘려나간다.- 처음에는 vi~vj를 직접 잇는 거리만 고려, 인접행렬에서
- 다음에는 vi~vj사이에 v1이 추가될 경우 거리가 달라지는지 확인, 즉 지금까지 알고있는 거리 vi~vj와 ,(vi~v1)+(v1~vj)중 어느 것이 짧은가?
- 다음에는 v2이 추가된 거리, v3이 추가된 거리 ... vn이 추가된 거리를 고려하면 끝
ㄴ해당 예시를 보면 갈 수 있는 경로가 추가됨에 따라 길의 최단거리가 갱신되거나, 새로운 경로를 얻는경우를 추가할 수 있다.
- 정확도 및 시간 복잡도
- 시간 복잡도
- 매번 모든 노드들의 조합에 대해서 현재까지의 최단 경로를 구해야 하고, 총 V번 반복해야 함, 총 O(V^3)- 시작 노드를 바꾸어 가면서 다익스트라 ,Bellman-Ford 알고리즘을 돌리는 것보다 빠르다.
백엔드 & 전공 공부