Взвешенный ориентированный граф python

Русские Блоги

Граф структуры данных: взвешенный ориентированный граф и алгоритм дижистры для поиска кратчайшего пути, Python —— 28

Взвешенный ориентированный граф и алгоритм дижистры для поиска кратчайшего пути

Построение взвешенного ориентированного графа

class DirectedEdge: def __init__(self, _from, _to, weight): self._from = _from self._to = _to self.weight = weight def get_weight(self): return self.weight def start(self): return self._from def end(self): return self._to 

• Ребра взвешенного ориентированного графа имеют направления, где _from — начальная вершина; _to — вершина назначения; weight — вес этого ребра.

Реализация взвешенного ориентированного графа

from Structure.graph.DirectedEdge import DirectedEdge class WeightedDigraph: def __init__(self, num): self.num_vertices = num self.num_edges = 0 self.adj_list = [[] for _ in range(num)] def add_edge(self, edge: DirectedEdge): _from = edge.start() # _to = edge.end() self.adj_list[_from].append(edge) self.num_edges += 1 def get_all_edges_of(self, v): """Get all edges connected v""" return self.adj_list[v] def get_all_edges(self): """Get all edges of this graph""" return [e for i in range(self.num_vertices) for e in self.adj_list[i]] 

• num_vertices определяет количество вершин в графе; num_edges — количество ребер. В исходном состоянии вершины отделены друг от друга, а количество ребер равно 0; adj_list — это список, индекс представляет вершину, и каждое значение также является списком, в котором хранится соответствующая вершина pass Вершина цели;
• add_edge (edge: DirectedEdge) передает объект DirectedEdge и добавляет направленную кромку в соответствующую позицию в adj_list;
• get_all_edges_of (v) Получить все ребра, ведущие к вершине v
• get_all_edges () Получить все ребра всего графа;

Задача о кратчайшем пути и дерево кратчайшего пути

Задача о кратчайшем пути (задача о кратчайшем пути) определение

• Кратчайший путь может быть кратчайшим временем, кратчайшим расстоянием или минимальной стоимостью.
• В теории графов проблема кратчайшего пути относится к графу, который хочет найти путь между двумя вершинами, чтобы минимизировать вес всех ребер, соединенных между ними.

1. Путь направленный;
2. Вес не обязательно равен расстоянию. Весом может быть расстояние, время, стоимость и т. Д. Самый маленький вес означает самые низкие затраты.
3. Рассмотрим только связные графы. Не все вершины в графе достижимы. Если s и t недостижимы, кратчайшего пути между ними нет. Для упрощения задачи здесь рассматриваются только связные графы.
4. Кратчайший путь не обязательно уникален. Может быть много путей с наименьшим весом от одной вершины к другой. Найдите один здесь.

Используйте алгоритм djistra, чтобы найти дерево кратчайшего пути

Определение дерева кратчайшего пути

• Для взвешенного ориентированного графа и вершины s дерево кратчайших путей, начинающееся с s, является подграфом графа, который содержит вершину s и все вершины, достижимые из s. Корневой узел этого ориентированного дерева — s. Каждый путь дерева является кратчайшим путем в ориентированном графе.

Дизайн свойств и методов

1. В методе построения __init __ ()
   граф получает входящий объект графа; start_vertex — найти начальную вершину дерева кратчайшего пути;
   SP_weight — это список, индекс представляет текущую вершину, а значение представляет вес кратчайшего пути от начальной точки до соответствующей вершины индекса. Он инициализируется и сохраняется как бесконечная бесконечность, которая может пройти путь при поиске. Первоначальное сравнение веса будет успешным;
   last_edge — это список, индекс соответствует вершине, а сохраненное значение представляет последнее ребро кратчайшего пути от начальной точки до вершины, соответствующей индексу;
   SPT_edge_weights — это объект MinIndexPriorityQueue очереди с минимальным приоритетом. Индекс представляет вершину. Сохраненное значение — это вес последнего ребра на пути после Relax () от начальной точки до текущая пройденная вершина., Фактически, окончательный вес — это соответствующий last_edge
2. Relax (v) Вершина v в графе релаксационного графа, процесс работы будет представлен ниже
3. sp_weight_to (v) Получить сумму весов SP от начальной точки до входящей вершины v
4. has_path_to (v) Проверяет, существует ли путь от начальной точки в графе до вершины v
5. shorttest_path_to (v) Получить все ребра, пройденные SP от начальной точки до вершины v

Процесс расслабления

• Уже существует кратчайший путь S-> W и известен общий вес пути SP_weight [w]. Теперь, чтобы определить, является ли следующий путь S-> V-> W короче, сначала вычислите общий кратчайший путь S-> V Weight SP_weight [V], а затем добавьте вес самой короткой стороны V-> W. Если сумма больше, чем вес кратчайшего пути до и SP_weight [W], нет необходимости расслабляться и обновлять данные
  
• Когда сумма весов кратчайшего пути от начальной точки S до V плюс вес кратчайшего пути от V до W меньше суммы весов кратчайшего пути от начальной точки S до W, что соответствует Для успешного ослабления требуется кратчайший от S до W Сумма весов пути SP_weight [W] обновляется до SP_weight [V] + [Вес стороны от V до W], последний край перед достижением конечной точки, last_edge обновляется до [ V → W]
• Релаксация вершины основана на релаксации ребер.Все ребра, указанные определенной вершиной, должны быть расслаблены, после чего релаксация вершины завершена. Например, чтобы расслабить вершину v, вам нужно только пройти по списку смежности v и расслабить каждую сторону, тогда вершина v расслабится.

Код Python реализует алгоритм djistra для поиска кратчайшего пути

from Structure.graph.DirectedEdge import DirectedEdge from Structure.graph.WeightedDigraph import WeightedDigraph from Structure.PriorityQueue.IndexMinpriorutyQueue import IndexMinPriorityQueue from math import inf class DjistraSP: def __init__(self, graph, start_vertex=0): self.graph = graph self.start_vertex = start_vertex # Each vertex(index) point to a minimum weight from the start vertex(0) self.SP_weight = [inf for _ in range(self.graph.num_vertices)] # Store the last SPT edge from 0 to the vertex(index) self.last_edge = [None for _ in range(self.graph.num_vertices)] # Store all edges? of the SPT(all the last_edge) # Index equals to vertex, element equals to edge.weight from the current vertex self.SPT_edge_weights = IndexMinPriorityQueue(self.graph.num_vertices) # num_vertices - 1 + 1 self.SP_weight[start_vertex] = 0.0 # Index equals to vertex, element equals to weight self.SPT_edge_weights.insert(start_vertex, 0.0) while self.SPT_edge_weights.size() > 0: min_weight_vertex = self.SPT_edge_weights.delete_min_and_get_index() # print(f"min_weight_vertex ") self.relax(min_weight_vertex) def relax(self, v): """Check if the total weight from 0 to v is lesser than from 0 to w""" # To relax a vertex is to relax all its edges for e in self.graph.get_all_edges_of(v): w = e.end() if self.SP_weight[v] + e.weight  self.SP_weight[w]: self.SP_weight[w] = self.SP_weight[v] + e.weight self.last_edge[w] = e if self.SPT_edge_weights.is_index_exist(w): self.SPT_edge_weights.change_item(w, e.weight) else: self.SPT_edge_weights.insert(w, e.weight) def sp_weight_to(self, v): """Get the total weight of a shortest path from 0 to v""" return self.SP_weight[v] def has_path_to(self, v): """Check if the start vertex to v is feasible""" # return self.graph.adj_list[v] return self.SP_weight[v]  inf def shortest_path_to(self, v): """Get all the shortest path edges from 0 to v""" if not self.has_path_to(v): return all_sp_edges = [] while True: e = self.last_edge[v] if not e: break all_sp_edges.insert(0, e) v = e.start() return all_sp_edges if __name__ == '__main__': with open('../DSP.txt', 'r') as f: num_vertices = int(f.readline()) num_edges = int(f.readline()) graph = WeightedDigraph(num_vertices) edge = DirectedEdge for _ in range(num_edges): _from, _to, weight = f.readline().split() # print(_from, _to, weight) graph.add_edge(edge(int(_from), int(_to), float(weight))) end = 6 DSP = DjistraSP(graph, 0) # print([e.start() for e in DSP.shortest_path_to(end)] + [end]) print(DSP.sp_weight_to(end)) print(DSP.has_path_to(end)) for e in DSP.shortest_path_to(end): print(f"-->, ") 

1.5100000000000002 True 0-->2, 0.26 2-->7, 0.34 7-->3, 0.39 3-->6, 0.52 

Справочные результаты сравнения:

8 15 4 5 0.35 5 4 0.35 4 7 0.37 5 7 0.28 7 5 0.28 5 1 0.32 0 4 0.38 0 2 0.26 7 3 0.39 1 3 0.29 2 7 0.34 6 2 0.40 3 6 0.52 6 0 0.58 6 4 0.93 

2020-4-20 Блог остановлен более чем на полгода

Источник