문과생이 이해한 파이썬 Floyd의 최단 거리 알고리즘

MAX_VERITICES=100
INF=1000000

class floyd:
    def __init__(self, n, mat):
        self.n=n
        self.weight=mat
        self.A=[[0 for i in range(MAX_VERITICES)]for i in range(MAX_VERITICES)]

    def run(self):
        for i in range(self.n):
            for j in range(self.n):
                self.A[i][j]=self.weight[i][j]
        self.printA()

        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if self.A[i][k] + self.A[k][j] <self.A[i][j]:
                        self.A[i][j] = self.A[i][k] + self.A[k][j]
            self.printA()

    def printA(self):
        print('-------------------------------------')
        for i in range(self.n):
            for j in range(self.n):
                if self.A[i][j]==INF:
                    print('%3s' %('*'), end=' ')
                else:
                    print('%3d' %(self.A[i][j]), end=' ')
            print()

        print('--------------------------------------')


if __name__ == '__main__':
    mat=[[0,7,INF,INF,3,10,INF],
         [7,0,4,10,2,6,INF],
         [INF,4,0,2,INF,INF,INF],
         [INF,10,2,0,11,9,4],
         [3,2,INF,11,0,INF,5],
         [10,6,INF,9,INF,0,INF],
         [INF,INF,INF,4,5,INF,0]]
    f=floyd(7, mat)
    f.run()

 

---

 

 floyd 코드 이해하고 보니까 진짜 별거 없는데 이해하는데 시간 진짜 오래걸렸다. 아 그리고 어제부터 개강이다... 오늘 1교시 실강 들으려고 평소보다 일찍 일어났더니 잠이 너무 온다하아아암

 

 

---

<초기화>

 

 최단 경로는 위에서 설명햇듯이 그냥 가중치 합이 가장 적은 경로를 탐색하는 거다. 정점을 덜 거치는 게 최단 경로일 줄 알았눈데... 아암 어림도 없지!!!

 

 

 초기화는 BFS 인접행렬과 비슷하게 정점의 개수와 가중치 인접 행렬을 보내준다. 여기서 BFS에서 사용된 인접 행렬과 가중치 인접 행렬은 다르다!!!

 

 

 

 BFS에서 다뤘던 그래프는 무방향 그래프다. 그리고 그 아래 네트워크/가중치 그래프라는 것이 있는데, 이 둘의 인접 행렬 표현법이 좀 다르다. 

 

 

 왼쪽이 양방향 그래프이고, 오른쪽이 가중치 그래프다. 양방향 그래프는 열과 행을 각 정점으로 생각하고 두 정점이 이어져 있으면 각 정점에 해당하는 행과 열에 1으로 표시한다. 반대의 경우 0을 표시한다.  

 

 반면, 가중치 그래프는 행렬에 가중치가 적힌다. 

 

 

 예를 들어 이런 행렬이 잇으면 0정점과 1정점의 가중치는 7이다. 반면 0정점과 2정점은 연결된 간선이 없어서 INF이다. 그렇다면 가중치 0은 연결된 간선이 없다는 얘기가 아니라, 정점과 정점사이의 가중치가 0이라는 말이겠쥬??

 

 

 

 

자 구럼 floyd를 초기화하면 이렇게 된다. 그렇다면 행렬 A는 무엇이냐. 바로 최단 거리를 기록할 배열이다. 예를 들어,

 

 

 

 오른쪽 그래프에서 0정점에서 2정점으로의 최단 거리(가중치가 가장 적은 거리)는 0정점->4정점->1정점->2정점으로 가중치가 9이다. 그러면 0행 2열/2행 0열에 INF를 9로 갱신해주면 된다. 

 

 

 

---

<run>

 

 

 자 그러면 floyd를 실행하자. 먼저 A행렬에 가중치 인접 행렬을 배껴써준다. 왜냐고? 최단 거리를 비교하기 위한 기준이 되는 것이 필요하기 때문이다. 그래서 이중 for문을 통해서(행렬이니까) mat행렬을 고대로 빼껴 A행렬에 저장해준다.

 

 

 

 

 자 그리고 삼중 for문을 통해서 최단거리를 찾아준다. 

 

 - k : 1, i : 0, j : 2일 때,  왜 k가 0일 때부터 안하냐면.. k가 0일 때 설명을 개판으로 해서....

 앞에서 설명햇듯이 k는 거쳐갈 정점, i는 시작 정점, j는 도착 정점이다. 

 

 

뭔가 보이시나요? 시작 정점 i는 0, 도착 정점 j는 2, 거쳐가는 정점 k는 1. 여기의 가중치를 합하면 11이다. 

 

 

 

 그러면 여기 조건을 맞추게 되겠쥬?? 여기 조건은

 

if A[0][1] + A[1][2] < A[0][2]다. 즉, 시작 정점-거쳐가는 정점(7) + 거쳐가는 정점-도착 정점(4) < 시작정점-도착정점(기존의 최단 거리)인데. 지금 시작-도착정점이 INF이므로 INF를 11로 갱신해주면 된댜. 

 

 

 이런 식으로 k가 1일 때 A행렬에서 갱신되는 최단거리 값들이다. 

 

 

 

- k : 4, i : 0, j : 2일 때 

 

  

 저기 보면 k가 3일 때 갱신된 최단거리 A행렬이다. 그렇다면 k,i,j가 각각 위와 같은 상황이라 할 때, 조건문은 3+6 < 11으로 조건문을 만족한다!!!

 

 그럼 11로 갱신되었던 값이 다시 9로 갱신되면서 최단거리가 A행렬에 기록된다. 

 

 

---

<최종 출력 창>

 

 

이걸 반복하면 이렇게 최단 거리 가중치를 모은 A행렬 ㅇ..완성...!!!!

 

 

 쟈, 그럼 0에서 3정점까지 최단거리는 0행 3열이나, 3행 0열을 확인하면 되겠쮸?? 11이다. 그럼 0->4->1->2->3루트라는 뜻이겟죠??? 꺅!!

 

 이제 진짜 끗