[Algorithm] 다익스트라 vs 벨만포드 vs 플로이드와샬

다익스트라 알고리즘

그래프에서 하나의 노드에서 다른 모든 노드로 이동하는 최단 비용을 구하는 알고리즘

• 시간 복잡도 : O(E * log E)
  ** E : 간선의 수

동작 순서

1. 시작 노드의 비용을 0 으로 초기화 (본인에게 이동하는 비용은 0)
2. 우선 순위 큐에 시작 노드를 삽입 (연결 리스트로 구현하는 등 다른 방법도 있는 듯 하다)
3. 큐가 비어있을 때 까지 아래의 동작을 수행
4. 큐에서 노드를 꺼냄
5. 꺼낸 노드 (이하 Now) 에 연결된 노드가 방문했는지 확인
6. 방문했다면 3 으로 이동
7. 아니라면 방문 체크
8. Now 에서 연결된 노드만큼 아래의 동작을 수행
9. Now 에서 연결된 노드 (이하 Next) 의 비용과 Now 의 비용을 더한 값이 기존에 알고 있던 Next 의 비용보다 작다면 Next 의 비용을 해당 값으로 갱신
10. 큐에 삽입

소스 코드

data class Node(val end: Int, val weight: Int) : Comparable<Node> {
	override fun compareTo(other: Node): Int {
    	return weight - other.weight
    }
}

/ ... /
const val INF = 987654321
fun dijkstra(start: Int): IntArray {
	val queue = PriorityQueue<Node>()
    val dist = Array<IntArray>(N+1) {INF}
    
    // 1
    dist[start] = 0
    // 2
    queue.offer(Node(start, 0))
    
    // 3
    while (queue.isNotEmpty()) {
    	// 4
    	val now = queue.poll()
        
        // 5
        if (visit[now.end]) continue
        // 7
        visit[now.end] = true
        
        // 8
        for (next in graph[now]) {
        	// 9
            if (dist[next.end] > dist[now.end] + next.weight) {
            	dist[next.end] = dist[now.end] + next.weight
                // 10
                queue.offer(Node(next.end, dist[next.end]))
            }
        }
    }
}

벨만포드 알고리즘

하나의 노드에서 다른 모든 노드로 가는 최소 비용을 구하는 알고리즘
단, 간선의 값 (비용) 이 음수인 경우에도 사용 가능하며 음수 순환을 판별할 수 있다.

• 시간 복잡도 : O(V * E)
  ** V : 노드 수, E : 간선 수

• 음수 순환 : 음수의 값을 가지는 간선이 있고, 주변에 연결된 간선들이 루프를 이룰 때

동작 순서

다익스트라 알고리즘과 값을 갱신하는 방식 (최소 비용을 구함) 은 같지만, 노드의 수 만큼 라운드를 진행하다 마지막 라운드에서도 갱신이 일어난다면 음수 순환이 존재한다고 판별한다.

소스 코드

const val INF = 987654321

fun bf(start: Int): Boolean {
	// 시작 노드에 대해서 초기화
	dist[start] = 0
    
    // 전체 N 번의 라운드 반복
    for (i in 0 until N) { // N : 노드의 갯수
    	// 매 반복마다 "모든 간선"을 확인
    	for (j in 0 until M) { // M : 간선의 갯수
        	now = edges[j][0]
            next = edges[j][1] // edges = (start, end, weight)
            weight = edges[j][2]
            
            // 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if (dist[now] != INF && dist[next] > dist[now] + weight) {
            	dist[next] = dist[now] + weight
                
                // N 번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                if (i == N - 1) return true
            }
        }
    }
    
    return false
}

플로이드와샬 알고리즘

모든 각 노드에서 나머지 노드까지 가는 최소 비용을 구하는 알고리즘

• 3중 for 문을 사용하며 아래의 순서대로 반복의 기준이 된다.
  • 거쳐가는 노드
  • 출발 노드
  • 도착 노드
• 시간 복잡도 : O(N ^ 3)
  ** N : 노드 수

동작 순서

1. 결과를 저장하는 2차원 배열을 생성 ( 나머지 두 알고리즘과 달리 각각의 노드들의 최소 비용을 구하기 때문 )
2. 거쳐가는 노드 = k 기준 반복
3. 출발 노드 = i 기준 반복
4. 도착 노드 = j 기준 반복
5. 만약 dist[ I ][ J ] > dist[ I ][ K ] + dist[ K ][ J ] 라면 값을 갱신

소스 코드

fun floydWarshall() {
	// 1
	val dist = Array<ArrayList>(N) { arrayListOf() }
    
    // 2차원 배열을 초기화
    for (i in 0 until N) {
    	for (j in 0 until N) {
        	dist[i][j] = graph[i][j]
        }
    }
    
    // 2
    for (K in 0 until N) {
    	// 3
        for (I in 0 until N) {
        	// 4
            for (J in 0 until N) {
            	// 5
                if (dist[I][J] > dist[I][K] + dist[K][J])
                	dist[I][J] = dist[I][K] + dist[K][J]
            }
        }
    }
}

결론

간선의 비용이 주어지는 그래프 문제에서 세 알고리즘을 어떤 경우에 사용하는지

• 다익스트라 알고리즘
  • 하나의 노드에서 다른 노드로 가는 최소 비용을 구할 때
  • 간선의 값 중에 음수가 없을 때
  • 제일 빠르다 (속도가 필요할 때)
• 벨만포드 알고리즘
  • 하나의 노드에서 다른 노드로 가는 최소 비용을 구할 때
  • 간선의 값 중에 음수가 존재하는 경우
  • 음수 순환을 판단해야 하는 경우
• 플로이드와샬 알고리즘
  • 모든 노드의 비용을 구할 때