Floyd-Warshall Algorithm

개념

• V개의 점이 있는 그래프에서, 최단 거리를 찾는 알고리즘
• for문을 3번 돌면서, dist[i][j]를 'i번째 점부터 j번째 점까지 곧바로 가는 최솟값, 곧바로 or 1번 점을 거치거나 거치지 않으면서 가는 최솟값, 곧바로 or 1번 점을 거치거나 거치지 않으면서 or 2번 점을 거치거나 거치지 않는 최솟값, ... , 곧바로 or 1번 점을 ... or V번 점을 거치거나 거치지 않으면서 가는 최솟값'을 구하는 알고리즘이다.
• 일반적으로 DP랑 따로 배우긴 하나(그래프 최단거리 알고리즘 배울 때 묶어서 배우...지?), DP 알고리즘이다.
• Time Complexity: 점의 개수 V에 대하여 for문 3번 돌기 떄문에 O(V^3)
• 음의 간선이 있어도 가능하나, 음의 사이클이 있으면 불가능 (음의 사이클의 존재 유무를 검출할 수 있다고 한다.)
• self-loop의 경우, 양수더라도 dist[v][v] = 0 for all vertex v 를 통해 무시한다. 

 

유사코드

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u, v) do
    dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
for each vertex v do
    dist[v][v] ← 0
for k from 1 to |V|
    for i from 1 to |V|
        for j from 1 to |V|
            if dist[i][j] > dist[i][k] + dist[k][j] 
                dist[i][j] ← dist[i][k] + dist[k][j]
            end if

코드 작성 시 유의점

• 처음에 모든 점까지 가는 경로의 길이를 infinity(=적당히 큰 수: JAVA에서 int형을 사용할 때, Integer.MAX_VAULE를 쓰면 덧셈에서 오버플로우가 뜰 수 있으니 조심.), 자기 자신으로 가는 경로는 0로 초기화한다.
• 경유지 -> 시작지 -> 도착지 순으로 for문을 돌아야 한다.

 

 

경로 추적 - 코드

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
let next be a |V| × |V| array of vertex indices initialized to null

procedure FloydWarshallWithPathReconstruction() is
    for each edge (u, v) do
        dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
        next[u][v] ← v
    for each vertex v do
        dist[v][v] ← 0
        next[v][v] ← v
    for k from 1 to |V| do // standard Floyd-Warshall implementation
        for i from 1 to |V|
            for j from 1 to |V|
                if dist[i][j] > dist[i][k] + dist[k][j] then
                    dist[i][j] ← dist[i][k] + dist[k][j]
                    next[i][j] ← next[i][k]
                    
procedure Path(u, v)
    if next[u][v] = null then
        return []
    path = [u]
    while u ≠ v
        u ← next[u][v]
        path.append(u)
    return path

코드 작성 시 유의점

• next[i][j]가 'i에서 j로 가는 최단 경로에서 바로 다음으로 가야하는 장소'라는 의미기에, dist[i][j] < dist[i][k] + dist[k][j]라면 i에서 j로 가는 거리가 최소이려면 i에서 k를 거쳐가야 하고, i에서 k에서 거쳐갈 때 바로 다음으로 가는 장소는 정의상 next[i][k]다.