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

#c언어로 쉽게 풀어쓴 자료구조 연습문제를 파이썬 코드로 구현

 

MAX_VERITICES=10
INF=1000000

class DIJKSTRA:
    def __init__(self, n, mat):
        self.n=n
        self.weight=mat
        self.distance=[None] * MAX_VERITICES  #시작 정점으로부터의 최단 경로 거리
        self.found=[False] * MAX_VERITICES     #방문한 정점 표시

    def choose(self):
        min=INF
        minpos=-1
        for i in range(self.n):
            if self.distance[i] < min and not(self.found[i]) :
                min=self.distance[i]
                minpos=i

        return minpos

    def run(self, start=0):
        #초기화
        for i in range(self.n):
            self.distance[i]=self.weight[start][i]

        #시작 정점 방문 표시
        self.found[start]=True
        self.distance[start]=0
        for i in range(self.n):
            self.print_status()
            u=self.choose()
            self.found[u]=True
            for w in range(self.n):
                if not self.found[w]:
                    if (self.distance[u] + self.weight[u][w] < self.distance[w]):
                        self.distance[w] = self.distance[u] + self.weight[u][w]

    step=1
    def print_status(self, step=1):
        print('STEP {} '.format(DIJKSTRA.step), end=' '); DIJKSTRA.step+=1
        print('distance : ', end=' ')
        for i in range(self.n):
            if self.distance[i] == INF:
                print('%2s' %'*',  end=' ')
            else:
                print('%2d' % self.distance[i], end=' ')
        print()
        print('found : ', end=' ')
        for i in range(self.n):
            print('%2d' %self.found[i], end=' ')
        print('\n')

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=DIJKSTRA(7, mat)
    f.run()

 

  개강 첫 주는 보통.. OT하지 않ㄴ나...  우리과 교수님의 열정에 못 따라가는 와타시... 개강 첫주부터 죽을 뻔 햇다. 그리고 업로드는 안 햇는데 AVL 트리 구현하다가 고인이 될 뻔 했다.. 디버깅만 오조오억번... 

 

 다익스트라 이녀석. 분명 플로이드 하면서 했는데 까먹은 똥멍청이...

---

<초기화>

 

 

 floyd 알고리즘처럼 일단 가중치 인접 행렬을 전달해준다. 

 

 

 1. n : 정점

 2. weight : 가중치

 3. distance : 시작 정점으로부터의 최단 경로 거리 

 4. found : 방문한 정점 표시

 

 

 distance 초기화는 일단 시작 정점에서 시작한다. 아래 설명이 기억이 나는가?? 다익스트라는 하나의 정점(start)에서 다른 정점으로의 최단 경로를 구하는 알고리즘이기 때문에 최단 경로를 저장하는 배열이기 때문에. 저러케 초기화를 해준당.

 

 

그러면 어케 초기화가 되느냐..!!!

 

 

  요케 초기화가 된다. 움.. 이제 보니까 distance 크기를 최대 정점 크기만큼이 아니라, 사용자가 설정한 정점의 개수(self.n)만큼 하는게 나을 수도 있겟다.. 뒤에 None으로 해놓으니까 대게 지저분해보인당.

---

<최단 거리 탐색>

 

 

 

  일단 시작 정점에서 최단 거리를 기록한 배열인 distance를 가중치 0행으로 모두 초기화해준다. 

 

 

 구럼 요러케 초괴화된다. (INF는 전역변수로 1000000이당) 이거는 곧 0에서 시작하여 첫번째 정점으로 가는 간선의 가중치가 7이고, 두번째 정점으로 가는 간선이 없다는 것을 알려주는 초기값이기도 하다.

 

 

 

 다익스트라는 시작정점에서 다른 정점으로 가는 모든 최단 경로를 구하는 알고리즘이다. 그래서 일단 시작 정점을 방문 표시한다. 참고로 found가 방문한 정점을 표시하는 배열이다. 

 

 

 

 

 첫번째 회전에서 거리와 방문한 곳을 출력한다. 지금은 시작정점에 머물러 있으니까 0에만 방문 표시가 되어 있는 모습이다. 

 

 

---

그리고 32번째 줄에 메소드를 실행하는데, 이게 방문한 정점을 제외하고 가장 적은 가중치를 가진 정점을 찾는 거다. 

 

 

이 메소드는 모든 정점을 순회하며 방문하지 않은 정점 가운데 가장 작은 가중치를 가진 정점을 찾아주는 메소드이다. 

 

현재 상태에서는 가중치가 3인 4번째 정점이 minpos에 저장되어 반환되겟쥬??

 

 

 

 당시 요기. 방문하지 않은 정점 가운데 가중치값이 가장 작은 정점인 4가 u에 저장되고, 4번째 정점을 방문 표시 해준다.

그리고 혹시 다른 경로를 통해서 가는 경로 가운데 현재 거리(distance)에 저장된 경로보다 적은 가중치를 가지는 경로가 있는 지 확인한다. 

 

 

 이게 뭔 개소리야;; 싶을테니 한번 코드를 따라가보자. 

 

 

 - w=0

 

 

- w=1

 이 때 조건이 만족하게 되는데, 여기서 아래 코드가 무슨 의민지 이해하는데 좀 헷갈렸다.

 

 

 이게 바로 36번 째 줄 조건 문이다. 만약 시작 정점에서 어떤 정점(시작 정점에서 가장 가중치가 작은 정점)을 거쳐 다른 정점들로 도착하는 가중치가 원래의 경로보다 작다면 그 값으로 수정하는 것이다!!

 

 

 저 그림을 잘 보면 0->4->1로 가면 가중치가 5지만, 0->1가면 가중치 7이다. 즉, 4정점을 거쳐서 1로 가는 것이 가중치 값이 더 작으므로 도착 정점에 해당하는 1(w)의 distance의 값을 갱신해준다.  

 

---

<여기서 잠깐>

 

 여기 쯤 오면 아마 이 출력 값의 의미를 알게 될 것이다. 

 

1. 시작 정점에서 가장 가중치가 작은 정점 순으로. (이 정점을 최단 경로를 찾기 위해 '거쳐갈 정점'이 된다.->u)

2. 방문하지 않은 모든 정점의 가중치와, 시작 정점->거쳐갈 정점(u)->거쳐가지 않은 모든 정점 순으로 방문했을 때의 가중치와 비교하여 더 작은 값으로 갱신. 

 

 이 과정을 거쳐서 갱신된 값들인 거다. 자 그럼 위 출력을 보며 다음 w 값들(최단 거리가 변하는 3,6만 볼꺼다)도 함께 보자

 

 

---

- w=3

 

 

 쟈, 위 출력값에서 distance[3]은 INF였다. 그러나 u를 거쳐가니 정점 3으로 갈 수 있게 되고 이는 곧 14라는 값으로 나온다. INF보다 14라는 값이 더 작으므로 14로 갱신되는 것!

 

 

- w=6

 요기도 마찬가지로 3+5<INF이므로 값 갱신!!!

 

 

 

---

<전체 출력>

 

 전체 출력하면 요러케 나온당. 여기서 하나만 더 살펴 볼껀데. 

 

 

 바로 이거다. 최단 경로가 많이 수정되는 정점에 대해서 알아 보자.   

 

 

일단 스텝2까지 봤으니까 스텝4에서 이어서 간략하게 설명할꺼다. (왜냐면 이제 슬슬 기빨려서...)

 

---

- step 4

 

 쟈 보면 step3에서는 방문 표시되어 있지 않던 6번 정점이 step4에서는 방문 표시가 되어있다. 그렇다면 step4에서의 거쳐갈 정점 u는 6인 것이다. (참고로 그래프에서는 0정점에서 6정점으로 가는 간선은 없지만, 최단 경로(distance)에는 8로 되어잇다. 즉, 최단 경로는 이전의 찾은 최단 경로를 토대로 다른 최단 경로를 찾을 수 잇는거다1!! 놀랍지 않은가?? 아무튼 6정점도 갈 수 잇는 것!)

 

 

그리고 3번정점이 14에서 12로 바꼇으므로, 전체 그래프 모양은 다음과 같다. 

 

 

---

- step 5

 

 

 쟈 요기서 u는 뭘까~? 두구두구두구~(요즘 애들은 이런 거 안하고 두둥! 한다던데. 나나 신기해!!)

 

 바로 2정점이다. 현재 시작정점에서 2정점으로의 최단거리는 9이고, 3정점은 12에서 11로 바꼇으므로 시작정점(0정점)에서 3정점으로의 최단 거리는 다음처럼 될 꺼다!!

 

 

 

 

---

끗