Floyd 알고리즘

Floyd알고리즘은 두 노드간의 최단거리를 산출하는 알고리즘을 활용해서,

 

모든 Node간의 최단 거리를 산출하는 알고리즘 입니다.

 

다음 예시를 봅시다.

A~E까지의 5개의 Node이있고, 서로간에 위와같은 거리가 존재할 때,

 

해당 상태는 우측과같은 거리행렬로 나타낼 수 있습니다(무한대는 갈수 없다는것을 뜻함)

 

A,C,E의 관계를 봅시다.

A->C로 바로 연결되어 있기 때문에 A->C로 가는 거리는 4로 생각할 수 있으나, 최소의 거리는 아닙니다.

A->E->C로 이동할 경우 2+1 = 3 < 4, 한번에 갈 경우보다 거리가 짧다는 것을 알 수 있습니다.

이 논리가 Floyd알고리즘의 핵심입니다.

 

위 논리를 활용해서, 거리행렬을 모두 갱신해주면 알고리즘이 종료됩니다.

 

시작점(N개)와 끝점(N-1)를 비교하고, 이때 중간점(N-2)의 반복비교가 발생하기 때문에

 

O(N3)의 시간복잡도를 보이는 알고리즘 입니다.

 

#인접행렬로 표현된 Graph 입니다(9999 = 연결X, 0 = 자기자신)
init_dist_mat = [[0,      6,     4,  9999,   2],
                 [6,      0,  9999,     8,9999],
                 [4,   9999,     0,    12,   1],
                 [9999,   8,    12,     0,9999],
                 [2,   9999,  9999,     1,   0]]

def floyd(DT_mat):    
	#주어진 Graph의 Max Node Count를 구합니다
    Max = len(DT_mat)   
    #가장 짧은 route를 저장하기 위한 Matrix를 준비합니다.
    short_route = [[0]*Max for i in range(Max)]
    #각 Element를 모든 다른 Element와 비교합니다.
    for i in range(Max):
        for j in range(Max):
            #둘 사이 거리가 Zero일 경우, 자기 자신임으로 Pass합니다.
            if DT_mat[i][j]==0:
                pass            
            elif DT_mat[i][j]!=0:
            	#두 Node 사이에 가능한 모든 경우의 수를 비교합니다.
                for k in range(Max):
		    #직통이 아니라 다른 원소를 거쳐서 가는게 더 가까운경우
                    #거리행렬 및 route matrix를 갱신시켜줍니다.
                    if DT_mat[i][j] > DT_mat[i][k]+DT_mat[j][k]:                        
                        DT_mat[i][j] = DT_mat[i][k]+DT_mat[j][k]
                        short_route[i][j] = k                 
    
    #모든 갱신이 완료되면 갱신된 거리행렬과 Route Matrix를 반환
    return DT_mat,short_route
                        
floyd(init_dist_mat)

///갱신된 거리행렬
==>[[0,  6, 3, 14, 2],
    [6,  0, 10, 8, 8],
    [3,  9, 0, 12, 1],
    [14, 8, 12, 0, 1],
    [2,  8, 1, 1, 0]]
  
///최단거리를 도달하기 위한 이동 중간 Node행렬
///예를들어 A -> C Node로 이동하기 위해선 E(4)Node를 거쳐가야됨
==>[[0, 0, 4, 1, 0],
    [0, 0, 0, 0, 0],
    [2, 0, 0, 0, 0],
    [1, 0, 0, 0, 3],
    [0, 0, 4, 0, 0]]