电商网站模版,公司网络平台搭建,品牌型网站建设哪家好,长葛网站建设公司Dijkstra单源最短路径算法#xff0c;用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展#xff0c;直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法#xff0c;在很多专业课程中都作为基本内容有详细的介绍#xff0c;如数据…Dijkstra单源最短路径算法用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法在很多专业课程中都作为基本内容有详细的介绍如数据结构图论运筹学等等。注意该算法要求图中不存在负权边。设G(V,E)是一个带权有向图把图中顶点集合V分成两组第一组为已求出最短路径的顶点集合(用S表示初始时S中只有一个源点以后每求得一条最短路径 , 就将加入到集合S中直到全部顶点都加入到S中算法就结束了)第二组为其余未确定最短路径的顶点集合(用U表示)按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外每个顶点对应一个距离S中的顶点的距离就是从v到此顶点的最短路径长度U中的顶点的距离是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。python 算法实现import queuefrom collections import namedtupleEdge namedtuple(Edge, [vertex, weight])class GraphUndirectedWeighted(object):def __init__(self, vertex_count):self.vertex_count vertex_countself.adjacency_list [[] for _ in range(vertex_count)]def add_edge(self, source, dest, weight):assert source self.vertex_countassert dest self.vertex_countself.adjacency_list[source].append(Edge(dest, weight))self.adjacency_list[dest].append(Edge(source, weight))def get_edge(self, vertex):for e in self.adjacency_list[vertex]:yield edef get_vertex(self):for v in range(self.vertex_count):yield vdef dijkstra(graph, source, dest):q queue.PriorityQueue()parents []distances []start_weight float(inf)for i in graph.get_vertex():weight start_weightif source i:weight 0distances.append(weight)parents.append(None)q.put(([0, source]))while not q.empty():v_tuple q.get()v v_tuple[1]for e in graph.get_edge(v):candidate_distance distances[v] e.weightif distances[e.vertex] candidate_distance:distances[e.vertex] candidate_distanceparents[e.vertex] v# primitive but effective negative cycle detectionif candidate_distance -1000:raise Exception(Negative cycle detected)q.put(([distances[e.vertex], e.vertex]))shortest_path []end destwhile end is not None:shortest_path.append(end)end parents[end]shortest_path.reverse()return shortest_path, distances[dest]def main():g GraphUndirectedWeighted(9)g.add_edge(0, 1, 4)g.add_edge(1, 7, 6)g.add_edge(1, 2, 1)g.add_edge(2, 3, 3)g.add_edge(3, 7, 1)g.add_edge(3, 4, 2)g.add_edge(3, 5, 1)g.add_edge(4, 5, 1)g.add_edge(5, 6, 1)g.add_edge(6, 7, 2)g.add_edge(6, 8, 2)g.add_edge(7, 8, 2)# for testing negative cycles# g.add_edge(1, 9, -5)# g.add_edge(9, 7, -4)shortest_path, distance dijkstra(g, 0, 1)assert shortest_path [0, 1] and distance 4shortest_path, distance dijkstra(g, 0, 8)assert shortest_path [0, 1, 2, 3, 7, 8] and distance 11shortest_path, distance dijkstra(g, 5, 0)assert shortest_path [5, 3, 2, 1, 0] and distance 9shortest_path, distance dijkstra(g, 1, 1)assert shortest_path [1] and distance 0if __name__ __main__:main()
