Dijkstra Python Dijkstra's algorithm in python: 초보자를 위한 알고리즘

Unsplash의 Ishan @seefromsky의 사진

Dijkstra의 알고리즘은 그래프에서 두 노드 사이의 최단 경로를 찾을 수 있습니다. 프로그래머라면 반드시 알아야 할 사항입니다. Wikipedia page에 멋진 gif와 역사가 있습니다.

이 포스트에서 나는 Rosetta Code의 시간 테스트를 거친 구현을 사용하여 가중치가 있는 그래프와 가중치가 없는 그래프 데이터를 처리할 수 있도록 약간만 변경하고 그래프를 즉석에서 편집할 수도 있습니다. 코드를 블록별로 설명하겠습니다.

알고리즘

알고리즘은 매우 간단합니다. Dijkstra는 20분 만에 그것을 만들었습니다. 이제 당신은 그것을 동시에 코딩하는 법을 배울 수 있습니다.

모든 노드를 방문하지 않은 것으로 표시하고 저장합니다.

초기 노드의 경우 거리를 0으로 설정하고 다른 노드의 경우 무한대로 설정합니다.

거리가 가장 작은 미방문 노드를 선택합니다. 이제 현재 노드입니다.

현재 노드에 대해 방문하지 않은 이웃을 찾고 현재 노드를 통해 거리를 계산합니다. 새로 계산된 거리를 할당된 거리와 비교하고 더 작은 거리를 저장합니다. 예를 들어, 노드 A의 거리가 6이고 A-B 모서리의 길이가 2인 경우 A에서 B까지의 거리는 6 + 2 = 8이 됩니다. B가 이전에 8보다 큰 거리로 표시된 경우 변경하십시오. 8로.

현재 노드를 방문한 것으로 표시하고 방문하지 않은 집합에서 제거합니다.

목적지 노드를 방문한 적이 있거나(특정 두 노드 간의 경로를 계획할 때) 방문하지 않은 노드 중 가장 작은 거리가 무한대인 경우 중지합니다. 그렇지 않은 경우 3-6단계를 반복합니다.

파이썬 구현

첫째, 가져오기 및 데이터 형식입니다. 원래 구현에서는 에지 데이터를 저장하기 위해 명명된 튜플을 사용할 것을 제안합니다. 우리는 정확히 그렇게 할 것이지만 비용 인수에 기본값을 추가할 것입니다. There are many ways to do that , 가장 적합한 것을 찾으십시오.

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = float('inf')
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
    return Edge(start, end, cost)

데이터를 초기화해 보겠습니다.

class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

꼭짓점을 찾아봅시다. 원래 구현에서 정점은 _ _ init _ _에 정의되어 있지만 가장자리가 변경되면 업데이트해야 하므로 속성을 지정하고 속성을 다룰 때마다 다시 계산합니다. 아마도 큰 그래프에 대한 최상의 솔루션은 아니지만 작은 그래프에는 적합할 것입니다.

    @property
    def vertices(self):
        return set(
            # this piece of magic turns ([1,2], [3,4]) into [1, 2, 3, 4]
            # the set above makes it's elements unique.
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

이제 기능 추가 및 제거를 추가해 보겠습니다.

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

모든 노드에 대한 이웃을 찾자:

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

알고리즘의 시간입니다! 이해하기 쉽도록 변수 이름을 변경했습니다.

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'

        # 1. Mark all nodes unvisited and store them.
        # 2. Set the distance to zero for our initial node 
        # and to infinity for other nodes.
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            # 3. Select the unvisited node with the smallest distance, 
            # it's current node now.
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])

            # 6. Stop, if the smallest distance 
            # among the unvisited nodes is infinity.
            if distances[current_vertex] == inf:
                break

            # 4. Find unvisited neighbors for the current node 
            # and calculate their distances through the current node.
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost

                # Compare the newly calculated distance to the assigned 
                # and save the smaller one.
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

            # 5. Mark the current node as visited 
            # and remove it from the unvisited set.
            vertices.remove(current_vertex)


        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path

사용합시다.

graph = Graph([
    ("a", "b", 7),  ("a", "c", 9),  ("a", "f", 14), ("b", "c", 10),
    ("b", "d", 15), ("c", "d", 11), ("c", "f", 2),  ("d", "e", 6),
    ("e", "f", 9)])

print(graph.dijkstra("a", "e"))
>>> deque(['a', 'c', 'd', 'e'])

위의 전체 코드:

from collections import deque, namedtuple


# we'll use infinity as a default distance to nodes.
inf = float('inf')
Edge = namedtuple('Edge', 'start, end, cost')


def make_edge(start, end, cost=1):
  return Edge(start, end, cost)


class Graph:
    def __init__(self, edges):
        # let's check that the data is right
        wrong_edges = [i for i in edges if len(i) not in [2, 3]]
        if wrong_edges:
            raise ValueError('Wrong edges data: {}'.format(wrong_edges))

        self.edges = [make_edge(*edge) for edge in edges]

    @property
    def vertices(self):
        return set(
            sum(
                ([edge.start, edge.end] for edge in self.edges), []
            )
        )

    def get_node_pairs(self, n1, n2, both_ends=True):
        if both_ends:
            node_pairs = [[n1, n2], [n2, n1]]
        else:
            node_pairs = [[n1, n2]]
        return node_pairs

    def remove_edge(self, n1, n2, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        edges = self.edges[:]
        for edge in edges:
            if [edge.start, edge.end] in node_pairs:
                self.edges.remove(edge)

    def add_edge(self, n1, n2, cost=1, both_ends=True):
        node_pairs = self.get_node_pairs(n1, n2, both_ends)
        for edge in self.edges:
            if [edge.start, edge.end] in node_pairs:
                return ValueError('Edge {} {} already exists'.format(n1, n2))

        self.edges.append(Edge(start=n1, end=n2, cost=cost))
        if both_ends:
            self.edges.append(Edge(start=n2, end=n1, cost=cost))

    @property
    def neighbours(self):
        neighbours = {vertex: set() for vertex in self.vertices}
        for edge in self.edges:
            neighbours[edge.start].add((edge.end, edge.cost))

        return neighbours

    def dijkstra(self, source, dest):
        assert source in self.vertices, 'Such source node doesn\'t exist'
        distances = {vertex: inf for vertex in self.vertices}
        previous_vertices = {
            vertex: None for vertex in self.vertices
        }
        distances[source] = 0
        vertices = self.vertices.copy()

        while vertices:
            current_vertex = min(
                vertices, key=lambda vertex: distances[vertex])
            vertices.remove(current_vertex)
            if distances[current_vertex] == inf:
                break
            for neighbour, cost in self.neighbours[current_vertex]:
                alternative_route = distances[current_vertex] + cost
                if alternative_route < distances[neighbour]:
                    distances[neighbour] = alternative_route
                    previous_vertices[neighbour] = current_vertex

        path, current_vertex = deque(), dest
        while previous_vertices[current_vertex] is not None:
            path.appendleft(current_vertex)
            current_vertex = previous_vertices[current_vertex]
        if path:
            path.appendleft(current_vertex)
        return path


graph = Graph([
    ("a", "b", 7),  ("a", "c", 9),  ("a", "f", 14), ("b", "c", 10),
    ("b", "d", 15), ("c", "d", 11), ("c", "f", 2),  ("d", "e", 6),
    ("e", "f", 9)])

print(graph.dijkstra("a", "e"))

추신 나처럼 알고리즘보다 Witcher에 대한 책을 더 많이 읽는 우리에게는 Sigismund가 아니라 Edsger Dijkstra가 있습니다.