Алгоритм Дейкстры для поиска кратчайшего пути в Python
Важно понимать, граф представляет собой множество узлов (nodes), соединенных ребрами (edges).
Узел — это просто какой-то объект, а ребро — это связь между двумя узлами. Выше представлен неориентированный граф, то есть без четких направлений, и здешние ребра являются двунаправленными. Существуют также ориентированные графы, у ребер которых есть конкретно указанное направление.
Как узлы, так и ребра могут быть носителями информации. К примеру, граф выше представляет собой систему зданий, которые соединены между собой туннелями. В узлах может находиться информация о названии здания (например, строка «Библиотека»), в то время, как ребро может содержать информацию о длине туннеля.
Графам можно найти удачное применение в огромном количестве востребованных областей: веб-страницы (узлы) с ссылками на другие страницы (ребра), маршрутизация пакетов в сетях, социальные сети, приложения для создания карт улиц, моделирование молекулярных связей, различные области математики, лингвистика, социология. В общем и целом, это может быть любая система, в которой оперируют связанные между собой объекты.
Реализация графов в Python
Данный этап немного выходит за рамки темы, рассматриваемой в статье, поэтому мы не будем вдаваться в подробности. Два самых популярных способа реализации графа — через матрицу смежности или через список смежности. У каждого метода есть свои преимущества и недостатки. Сначала рассмотрим реализацию через матрицу смежности, так как его проще представить визуально и понять на интуитивном уровне. Позже станет яснее, отчего определение базовой реализации оказывает сильное влияние на время выполнения. Любая реализация может задействовать алгоритм Дейкстры, а пока важно различать API, или абстракции (методы), которые могут взаимодействовать с графом. Кратко осветим реализацию матрицы смежности на примере кода Python. Для ознакомления с реализацией списка смежности хорошим стартом станет данная статья.
Ниже представлена матрица смежности для предыдущего графа. Каждый ряд представляет один узел графа, как и каждый столбец. В данном случае ряд 0 и столбец 0 представляют узел «А»; ряд 1 и столбец 1 — узел «B», ряд 2 и столбец 2 — узел «C» и так далее, принцип понятен. Каждый локальный элемент представляет ребро. Таким образом, каждый ряд показывает связь между одним узлом и всеми прочими узлами. Элемент «0» указывает на отсутствие ребра, в то время как «1» указывает на присутствие ребра, связывающего row_node и column_node в направлении row_node → column_node. Поскольку граф в примере является неориентированным, данная матрица равна его транспонированию (то есть матрица симметричная), поскольку каждая связь двунаправленная. Вы могли заметить, что главная диагональ матрицы представлена только нулями, а все оттого, что ни один узел не связан сам с собой. Таким образом, пространственная сложность данного представления нерасчетлива.
Теперь разберемся с кодом. Обратите внимание, что здесь задействовано немного экстра-данных — так как нам было нужно, чтобы реальные объекты узлов содержали определенную информацию, в классе Graph был реализован массив объектов узлов, индексы которых соответствуют номеру их ряда (столбца) в матрице смежности. В Graph также был добавлен вспомогательный метод, который позволяет использовать либо номера индекса узла, либо объект узда в качестве аргументов для методов класса Graph. Данные классы нельзя считать примерами элегантности, однако они хорошо выполняют свою работу, излишне не усложняя процесс:class Node: def __init__(self, data, indexloc = None): self.data = data self.index = indexloc class Graph: @classmethod def create_from_nodes(self, nodes): return Graph(len(nodes), len(nodes), nodes) def __init__(self, row, col, nodes = None): # установка матрица смежности self.adj_mat = [[0] * col for _ in range(row)] self.nodes = nodes for i in range(len(self.nodes)): self.nodes[i].index = i # Связывает node1 с node2 # Обратите внимание, что ряд - источник, а столбец - назначение # Обновлен для поддержки взвешенных ребер (поддержка алгоритма Дейкстры) def connect_dir(self, node1, node2, weight = 1): node1, node2 = self.get_index_from_node(node1), self.get_index_from_node(node2) self.adj_mat[node1][node2] = weight # Опциональный весовой аргумент для поддержки алгоритма Дейкстры def connect(self, node1, node2, weight = 1): self.connect_dir(node1, node2, weight) self.connect_dir(node2, node1, weight) # Получает ряд узла, отметить ненулевые объекты с их узлами в массиве self.nodes # Выбирает любые ненулевые элементы, оставляя массив узлов # которые являются connections_to (для ориентированного графа) # Возвращает значение: массив кортежей (узел, вес) def connections_from(self, node): node = self.get_index_from_node(node) return [(self.nodes[col_num], self.adj_mat[node][col_num]) for col_num in range(len(self.adj_mat[node])) if self.adj_mat[node][col_num] != 0] # Проводит матрицу к столбцу узлов # Проводит любые ненулевые элементы узлу данного индекса ряда # Выбирает только ненулевые элементы # Обратите внимание, что для неориентированного графа # используется connections_to ИЛИ connections_from # Возвращает значение: массив кортежей (узел, вес) def connections_to(self, node): node = self.get_index_from_node(node) column = [row[node] for row in self.adj_mat] return [(self.nodes[row_num], column[row_num]) for row_num in range(len(column)) if column[row_num] != 0] def print_adj_mat(self): for row in self.adj_mat: print(row) def node(self, index): return self.nodes[index] def remove_conn(self, node1, node2): self.remove_conn_dir(node1, node2) self.remove_conn_dir(node2, node1) # Убирает связь в направленной манере (nod1 к node2) # Может принять номер индекса ИЛИ объект узла def remove_conn_dir(self, node1, node2): node1, node2 = self.get_index_from_node(node1), self.get_index_from_node(node2) self.adj_mat[node1][node2] = 0 # Может пройти от node1 к node2 def can_traverse_dir(self, node1, node2): node1, node2 = self.get_index_from_node(node1), self.get_index_from_node(node2) return self.adj_mat[node1][node2] != 0 def has_conn(self, node1, node2): return self.can_traverse_dir(node1, node2) or self.can_traverse_dir(node2, node1) def add_node(self,node): self.nodes.append(node) node.index = len(self.nodes) - 1 for row in self.adj_mat: row.append(0) self.adj_mat.append([0] * (len(self.adj_mat) + 1)) # Получает вес, представленный перемещением от n1 # к n2. Принимает номера индексов ИЛИ объекты узлов def get_weight(self, n1, n2): node1, node2 = self.get_index_from_node(n1), self.get_index_from_node(n2) return self.adj_mat[node1][node2] # Разрешает проводить узлы ИЛИ индексы узлов def get_index_from_node(self, node): if not isinstance(node, Node) and not isinstance(node, int): raise ValueError("node must be an integer or a Node object") if isinstance(node, int): return node else: return node.index Здесь классы Node и Graph будут использованы для описания данного примера графа. Поместим вышеуказанный граф в код и посмотрим, получится ли в итоге верная матрица смежности:
a = Node("A") b = Node("B") c = Node("C") d = Node("D") e = Node("E") f = Node("F") graph = Graph.create_from_nodes([a,b,c,d,e,f]) graph.connect(a, b) graph.connect(a, c) graph.connect(a, e) graph.connect(b, c) graph.connect(b, d) graph.connect(c, d) graph.connect(c, f) graph.connect(d, e) graph.print_adj_mat() Матрицы смежности, полученная в выводе (из graph.print_adj_mat() ) после запуска кода, такая же, как и та, что была рассчитана ранее:
[0, 1, 1, 0, 1, 0] [1, 0, 1, 1, 0, 0] [1, 1, 0, 1, 0, 1] [0, 1, 1, 0, 1, 0] [1, 0, 0, 1, 0, 0] [0, 0, 1, 0, 0, 0]
При желании добавить расстояние ребрам графа нужно просто заменить единицы в данной матрице смежности на значения нужного расстояния. На данный момент класс Graph поддерживает данную функциональность, доказательством чему является код ниже. Для ясности демонстрации были добавлены произвольные значения длины:
w_graph = Graph.create_from_nodes([a,b,c,d,e,f]) w_graph.connect(a, b, 5) w_graph.connect(a, c, 10) w_graph.connect(a, e, 2) w_graph.connect(b, c, 2) w_graph.connect(b, d, 4) w_graph.connect(c, d, 7) w_graph.connect(c, f, 10) w_graph.connect(d, e, 3) w_graph.print_adj_mat()
В результате выводится следующая матрица смежности:
[0 , 5 , 10, 0, 2, 0] [5 , 0 , 2 , 4 , 0 , 0] [10, 2, 0, 7, 0, 10] [0 , 4 , 7 , 0 , 3 , 0] [2 , 0 , 0 , 3 , 0 , 0] [0, 0 , 10, 0 , 0 , 0]
Визуально данный граф будет представлен следующим образом:
ivan1911 / dijkstra.py
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| #!/usr/bin/env python |
| # -*- coding: utf-8 -*- |
| # Алгоритм Дейкстры |
| # Находит кратчайшее расстояние от одной из вершин графа до всех остальных. |
| # Алгоритм работает только для графов без рёбер отрицательного веса. |
| # Матрица задается как список словарей смежности вершин |
| # Описание алгоритма http://goo.gl/KsqC |
| def dijkstra_shortest_path ( graph , start , p = <>, u = [], d = <>): |
| if len ( p ) == 0 : p [ start ] = 0 # инициализация начального пути |
| # print «start V: %d, » % (start) |
| for x in graph [ start ]: |
| if ( x not in u and x != start ): |
| if ( x not in p . keys () or ( graph [ start ][ x ] + p [ start ]) < p [ x ]): |
| p [ x ] = graph [ start ][ x ] + p [ start ] |
| u . append ( start ) |
| min_v = 0 |
| min_x = None |
| for x in p : |
| # print «x: %d, p[x]: %d, mv %d» % (x, p[x], min_v) |
| if ( p [ x ] < min_v or min_v == 0 ) and x not in u : |
| min_x = x |
| min_v = p [ x ] |
| if ( len ( u ) < len ( graph ) and min_x ): |
| return dijkstra_shortest_path ( graph , min_x , p , u ) |
| else : |
| return p |
| if __name__ == ‘__main__’ : |
| # инициализация графа с помощью словаря смежности |
| a , b , c , d , e , f , g , h = range ( 8 ) |
| N = [ |
| < b : 7 , c : 9 , f : 14 >, |
| < a : 7 , c : 10 , d : 15 >, |
| < a : 9 , b : 10 , d : 11 , f : 2 >, |
| < b : 15 , c : 11 , e : 6 >, |
| < d : 6 , f : 9 >, |
| < a : 14 , c : 2 , e : 9 >, |
| < h : 2 >, |
| < g : 2 >, |
| ] |
| for i in range ( 1 ): |
| print dijkstra_shortest_path ( N , a ) |
| # b in N[a] — смежность |
| # len(N[f]) — степень |
| # N[a][b] — вес (a,b) |
| # print N[a][b] |