그래프 탐색 알고리즘은 간선에 가중치가 존재하는 경우와 존재하지 않는 경우로 구분된다

간선에 가중치가 없을 때 경로를 찾는 알고리즘으로는 BFS, DFS가 있다

간선에 가중치가 있을 경우 경로를 찾는 알고리즘으로는 다익스트라, 벨만-포드, 플루이드-워셜이 있다

1. DFS(깊이 우선 탐색, Depth-First Search)

• 최대한 깊이 내려간 뒤, 더 이상 갈 곳이 없을 경우 옆으로 이동한다
• 모든 노드를 방문하고자 하는 경우 사용한다
• 검색 속도는 BFS보다 느리다
• 스택이나 재귀함수를 통해 구현한다

2. BFS(너비 우선 탐색, Breadth-First Search)

• 최대한 넓게 이동한 다음, 더 이상 갈 곳이 없을 경우 아래로 이동한다
• 주로 주 노드 간의 최단 경로를 찾을 때 사용한다
• 큐를 통해 구현한다

DFS와 BFS의 시간복잡도

• 인접 리스트 : O(V+E)
• 인접 행렬 : O(V^2)

1. 다익스트라(Dijkstra) 알고리즘

• 그래프 상에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘
• 그리디(Priority Queue를 사용해 짧은 거리부터 초기화해 연산을 줄임) + DP(이전의 Distance를 배열로 저장함)
• 간선에 음의 가중치가 있다면 사용할 수 없다(벨만 포드나 플루이드 위셜 알고리즘 사용)

왜 음의 가중치가 있으면 다익스트라 알고리즘을 사용할 수 없을까?

다익스트라 알고리즘은 그리디한 방식으로 동작한다. 이는 한 번 방문처리된 노드는 다시 변경되지 않는다는 개념을 포함한다. 하지만, 이럴 경우 최단경로를 찾지 못하는 경우가 생길 수 있다

노드 A에서 B,C로 향하는 최단경로를 찾는다고 가정하자. A노드 다음에 더 거리가 짧은 C 노드를 먼저 방문할 것이다. 그리고 C를 이미 방문했기 때문에 A → B → C 경로는 영원히 찾을 수 없다. 왜냐하면 일반적으로 A → C 의 거리가 A → B보다 짧은데 A → B → C의 거리는 더 비효율적일 것이라는 그리디한 생각으로 구현된 알고리즘이기 때문이다.

만약 음수 가중치만큼을 모든 간선에 더해주어서 모든 가중치를 양수로 바꾸면 어떨까?

결론부터 말하면 안된다. A → B → C → D 의 경우와 A → D 경우를 생각해보자. 모든 간선에 x의 값을 더해주었다고 하면 A → B → C → D 의 경우 간선 3번에 각각 x가 더해져 총 3x의 길이가 추가되었다. 반면에 A → D의 경우 간선에 x의 길이가 추가되었다. 이는 문제를 해결할 수 있는 방법이 아니다

그럼 음수 가중치가 있을 경우 다익스트라는 항상 최단경로를 찾을 수 없는가?

구현 방법에 따라 구할 수도 있고 못 구할 수도 있다. 다익스트라 알고리즘을 구현하는 방법은 크게 2가지가 있다