[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 28

* 수업은 JS 기반이지만 Python으로 구현

Section 28

다익스트라 알고리즘 소개

• 세상에서 가장 많이 쓰이는 알고리즘 중 하나
• 그래프의 두 정점 사이에 존재하는 최단 경로를 찾는 것

다익스트라 알고리즘 사용되는 곳

• GPS: 가장 빠른 노선 찾기
• 네트워크 라우팅: 거대한 네트워크에서 데이터에 대한 최단 경로 찾기
• 생물: 사람들 사이에 전염병이 퍼지는 것을 다루는 모델
• 항공권: 도착지까지의 노선 중 가장 저렴한 것 찾기

가중치 그래프 작성

• 간선을 추가할 때, 연결할 두 노드와 그 사이의 무게 값을 입력한다.
• 인접 리스트에 추가할 때, 객체(dictionary)형태로 넣어준다.
  • 노드는 node로, 무게값은 weight으로 속성값을 정해준다.

알고리즘 과정

• 새로운 노드를 방문할 때마다 거리 값이 가장 작은 노드를 먼저 방문한다.
• 우리가 어디로 갈 지 정했다면, 그 인접점들을 각각 확인한다.
• 각 인접점마다 시작 노드부터 그 노드까지의 거리를 합을 내어 구한다.
• 만약 이전보다 더 작은 거리 합이 나온다면, 그 노드에 관해 계산된 새로운 최단거리를 저장한다.

우선 순위 큐 소개

• 새로운 요소에 우선순위를 부여하여 추가하는 배열
• enqueue를 이용하면 삽입, 재정렬되고, dequeue를 이용하면 제일 가장 작은 우선순위를 갖는 것이 반환, 삭제된다.
• sorting: O(N * log(N))

 

 

다익스트라 알고리즘

• 이 함수는 시작 노드와 종료 노드를 입력해야 한다.
• distances라는 이름의 객체(각 노드에 대해 현재 가장 짧은 거리를 저장하는 표)를 만들고, 각 key 값은 인접 리스트에 있는 모든 노드를 나타내고 value 값으로는 무한을 가진다. 시작 노드는 value 값이 0이다.
• distances라는 이름의 객체의 모든 값 설정이 끝나면, 각 노드를 우선 순위 큐에 저장해준다. value 값으로는 무한을 가진다. 시작 노드는 우리가 시작하는 곳이므로 0으로 둔다.
• previous라는 다른 객체를 만들고, 각 key 값은 인접 리스트에 있는 모든 노드로 하고, value 값은 Null로 둔다.
• 우선 순위 큐에 무언가 있는 한 아래의 루프를 돌린다.
  • 우선 순위 큐에 있는 노드를 dequeue한다.
  • 만약 dequeue한 노드가 종료 노드와 같다면 루프를 종료한다.
  • 만약 아니라면, 인접 리스트에 있는 노드 값에 따라 루프를 돌린다.
    • 시작 노드와 해당 노드 사이의 거리를 계산한다.
    • 만약 거리 값이 현재 distances 객체에 저장되어 있는 것보다 적으면 
      • distances 객체에서 해당 노드의 value값을 더 작은 것으로 바꾼다.
      • previous 객체에서 어디서 부터 왔는지 반영해 해당 노드의 값을 바꾼다.
      • 시작 노드부터 해당 노드까지의 총 거리를 enqueue한다.

우선 순위 큐의 업그레이드

• 우선 순위 큐를 이진 힙을 활용하면 훨씬 빠르게 작동한다.
• 이진 힙은 배열을 다시 계속해서 정렬해서 최저값을 미리 고르는 전통적인 방식보다 훨씬 빠른 방법이다.

 

• sort에는 key 속성이 있어 그것으로 정렬 기준을 정할 수 있다

* 구현 내용 수정중

다익스트라 구현

class WeightedGraph:
    # constructor
    def __init__(self):
        self.adjacencyList = {}

    def addVertex(self, v):
        if not v in self.adjacencyList:
            self.adjacencyList[v] = []

    def addEdge(self, v1, v2, w):
        self.adjacencyList[v1].append({'node': v2, 'weight': w})
        self.adjacencyList[v2].append({'node': v1, 'weight': w})

    def Dijkstra(self, start, finish):
        nodes = PriorityQueue()
        distances = {}
        previous = {}
        # to return at end
        path = []

        # build up initial state
        for V in self.adjacencyList:
            if V == start:
                distances[V] = 0
                nodes.enqueue(V, 0)
            else:
                distances[V] = float('inf')
                nodes.enqueue(V, float('inf'))
            previous[V] = None

        while(len(nodes.values)):
            smallest = nodes.dequeue().val

            if smallest == finish:
                # we are done
                # build up path to return at end
                while(previous[smallest]):
                    path.append(smallest)
                    smallest = previous[smallest]
            break
            
            if smallest or distances[smallest] != float('inf'):
                for neighbor in self.adjacencyList[smallest]:

                    # find neighboring node
                    nextNode = self.adjacencyList[smallest][neighbor]

                    # print(nextNode)

                    # calculate new distances to neighboring node
                    candidate = distances[smallest] + nextNode['weight']
                    NextNeighbor = nextNode.node

                    if candidate < distances[NextNeighbor]:

                        # updating new smallest distance to neighbor
                        distances[NextNeighbor] = candidate

                        # updating previous - how we got to neighbor
                        previous[NextNeighbor] = smallest

                        # enqueue in priority queue with new priority
                        nodes.enqueue(NextNeighbor, candidate)
                
                path = path + [smallest]
                path.reverse()
                return path


graph = WeightedGraph()
graph.addVertex("A")
graph.addVertex("B")
graph.addVertex("C")
graph.addVertex("D")
graph.addVertex("E")
graph.addVertex("F")

graph.addEdge("A","B", 4)
graph.addEdge("A","C", 2)
graph.addEdge("B","E", 3)
graph.addEdge("C","D", 2)
graph.addEdge("C","F", 4)
graph.addEdge("D","E", 3)
graph.addEdge("D","F", 1)
graph.addEdge("E","F", 1)

graph.adjacencyList

graph.Dijkstra("A", "E")

# graph.Dijkstra.previous
# graph.Dijkstra.distances


# ["A", "C", "D", "F", "E"]