比价网站模板,dede微电影网站模板下载,福建省城乡建设信息网站,电影网站如何做seo排名加权有向图与dijkstra算法找到最短路径
加权有向图的构造
最短路径问题与最短路径树
最短路径问题#xff08;The shortest path problem#xff09;定义
最短路径可以是时间花费最短#xff0c;也可以是距离最短#xff0c;或是花费最少在图论中#xff0c;最短路径问…加权有向图与dijkstra算法找到最短路径
加权有向图的构造
最短路径问题与最短路径树
最短路径问题The shortest path problem定义
最短路径可以是时间花费最短也可以是距离最短或是花费最少在图论中最短路径问题指的是一个graph中想要找到两个顶点之间的路径使它们间连通的全部边的权重和最小化
最短路径的性质
路径具有方向性权重不一定等价于距离。权重可以是距离、时间、花费等内容,权重最小指的是成本最低只考虑连通图。一副图中并不是所有的顶点都是可达的如果s和t不可达那么它们之间也就不存在最短路径为了简化问题,这里只考虑连通图。最短路径不一定是唯一的。 从一个顶点到达另外一个顶点的权重最小的路径可能会有很多条这里只要找出一条即啊。
使用dijkstra算法找到最短路径树
最短路径树Shortest-path tree定义
给定一副加权有向图和一个顶点s以s为起点的一棵最短路径树是图的一副子图它包含顶点s以及从s可达的所有顶点。这棵有向树的根结点为s树的每条路径都是有向图中的一 条最短路径。 去往dijkstra算法
class DirectedEdge:def __init__(self, _from, _to, weight):self._from _fromself._to _toself.weight weightdef get_weight(self):return self.weightdef start(self):return self._fromdef end(self):return self._to加权有向图的边具有方向其中_from是出发顶点_to是目的顶点weight是这条边的权重。
加权有向图的实现
去往dijkstra算法
from Structure.graph.DirectedEdge import DirectedEdgeclass WeightedDigraph:def __init__(self, num):self.num_vertices numself.num_edges 0self.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 1def get_all_edges_of(self, v):Get all edges connected with vreturn self.adj_list[v]def get_all_edges(self):Get all edges of this graphreturn [e for i in range(self.num_vertices) for e in self.adj_list[i]]
num_vertices 定义了图中顶点的个数num_edges 为边的数量初始状态下各顶点相互分隔边数量为0adj_list 是一个列表索引代表顶点每个值也是一个列表储存着对应顶点通向的目的顶点add_edge(edge: DirectedEdge)传入一个DirectedEdge对象向adj_list中对应位置添加一条有向边get_all_edges_of(v) 获取传入的顶点v的所有通往的边get_all_edges() 获取整张图的所有的边
松弛方法relax的过程
当前已经存在一条最短路径S-W且知道其路径总权重SP_weight[w]现在要判断下一条路径S-V-W是否更短则首先计算S-V的最短路径的总权重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代码实现dijkstra算法寻找最短路径
from Structure.graph.DirectedEdge import DirectedEdge
from Structure.graph.WeightedDigraph import WeightedDigraph
from Structure.PriorityQueue.IndexMinPriorityQueue import IndexMinPriorityQueue
from math import infclass DijkstraSP:def __init__(self, graph, start_vertex0):self.graph graphself.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 vertexself.SPT_edge_weights IndexMinPriorityQueue(self.graph.num_vertices) # num_vertices - 1 1self.SP_weight[start_vertex] 0.0# Index equals to vertex, element equals to weightself.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(fmin_weight_vertex {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 edgesfor 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.weightself.last_edge[w] eif 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 vreturn 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] infdef shortest_path_to(self, v):Get all the shortest path edges from 0 to vif not self.has_path_to(v):returnall_sp_edges []while True:e self.last_edge[v]if not e:breakall_sp_edges.insert(0, e)v e.start()return all_sp_edges属性和方法说明
构造方法__init__()中 graph 接收传入的图对象start_vertex 为要找出最短路径树的起始顶点 SP_weight是一个列表索引代表当前顶点值代表从起点出发到索引对应顶点的最短路径的权重和它初始化储存全部为无穷大inf可以使搜寻时路径时的初次权重比较一定会成功 last_edge是一个列表索引对应着顶点储存的值表示从起点到索引对应顶点的最短路径中的最后一条边 SPT_edge_weights是一个最小优先队列MinIndexPriorityQueue对象索引代表顶点存入的值是从起点到当前遍历顶点的经过松弛relax()后的路径上的最后一条边的权重其实就是对应的last_edge的权重relax(v) 松弛图graph中的顶点v下面会介绍其操作过程sp_weight_to(v) 获取从起点到传入的顶点v的SP的权重和has_path_to(v) 检查图中从起点出发是否存在一条路径能到达顶点vshortest_path_to(v) 获取从起点到达顶点v的SP经过的的所有边
回到DirectedEdge 回到WeightedDigraph 其中用到的的索引最小优先队列IndexMinPriorityQueue传送门
运行测试
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 DirectedEdgefor _ 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 6DSP DijkstraSP(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{e.start()}--{e.end()}, {e.weight})运行结果
1.5100000000000002
True
0--2, 0.26
2--7, 0.34
7--3, 0.39
3--6, 0.520 → 2 → 7 → 3 → 6
对比参考结果
DSP.txt
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
