河北住房和城乡建设厅网站电话,asp 免费网站模板,职业生涯规划大赛内容,沈阳seo博客文章目录 [toc]问题描述Dijkstra算法Dijkstra算法应用示例时间复杂性Python实现 个人主页#xff1a;丷从心
系列专栏#xff1a;贪心算法 问题描述
给定一个带权有向图 G ( V , E ) G (V , E) G(V,E)#xff0c;其中每条边的权是非负实数#xff0c;给定 V V V中的一个… 文章目录 [toc]问题描述Dijkstra算法Dijkstra算法应用示例时间复杂性Python实现
个人主页丷从心
系列专栏贪心算法 问题描述
给定一个带权有向图 G ( V , E ) G (V , E) G(V,E)其中每条边的权是非负实数给定 V V V中的一个顶点称为源计算从源到所有其他各顶点的最短路长度 Dijkstra算法
Dijkstra算法是解单源最短路径问题的一个贪心算法其基本思想是设置顶点集合 S S S并不断地做贪心选择来扩充这个集合一个顶点属于集合 S S S当且仅当从源到该顶点地最短路径长度已知初始时 S S S中仅含有源设 u u u是 G G G的某一个顶点把从源到 u u u且中间只经过 S S S中顶点的路称为从源到 u u u的特殊路径并用数组 d i s t dist dist记录当前每个顶点所对应的最短特殊路径长度用列表parent[i]记录从源到顶点 i i i的最短路径上 i i i的前一个顶点Dijkstra算法每次从 V − S V - S V−S中取出具有最短特殊路长度的顶点 u u u将 u u u添加到 S S S中同时对列表dist和parent做必要的修改当dist[u] graph[u][i] dist[i] 时置dist[i] dist[u] graph[u][i]置parent[i] u一旦 S S S包含了所有 V V V中顶点dist就记录了从源到所有其他顶点之间的最短路径长度 Dijkstra算法应用示例
对下图中的有向图应用Dijkstra算法计算从源顶点 1 1 1到其他顶点间最短路径的过程如下表所示 迭代 S S S u u u d i s t [ 2 ] dist[2] dist[2] d i s t [ 3 ] dist[3] dist[3] d i s t [ 4 ] dist[4] dist[4] d i s t [ 5 ] dist[5] dist[5]初始 { 1 } \set{1} {1} − - − 10 10 10 m a x i n t maxint maxint 30 30 30 100 100 100 1 1 1 { 1 , 2 } \set{1 , 2} {1,2} 2 2 2 10 10 10 60 60 60 30 30 30 100 100 100 2 2 2 { 1 , 2 , 3 } \set{1 , 2 , 3} {1,2,3} 4 4 4 10 10 10 50 50 50 30 30 30 90 90 90 3 3 3 { 1 , 2 , 4 , 3 } \set{1 , 2 , 4 , 3} {1,2,4,3} 3 3 3 10 10 10 50 50 50 30 30 30 60 60 60 4 4 4 { 1 , 2 , 4 , 3 , 5 } \set{1 , 2 , 4 , 3 , 5} {1,2,4,3,5} 5 5 5 10 10 10 50 50 50 30 30 30 60 60 60 时间复杂性
对于一个具有 n n n个顶点的带权有向图Dijkstra算法进行二重循环需要 O ( n 2 ) O(n^{2}) O(n2)时间 Python实现
import sysclass Graph:def __init__(self, vertices):self.V verticesself.graph [[0 for _ in range(vertices)] for _ in range(vertices)]def printSolution(self, dist, parent):for v in range(self.V):path []curr vwhile curr ! -1:path.append(curr)curr parent[curr]path.reverse()print((v, dist[v], path))def minDistance(self, dist, sptSet):min_value sys.maxsizemin_index -1for v in range(self.V):if dist[v] min_value and not sptSet[v]:min_value dist[v]min_index vreturn min_indexdef dijkstra(self, src):dist [sys.maxsize] * self.Vdist[src] 0sptSet [False] * self.Vparent [-1] * self.Vfor _ in range(self.V):u self.minDistance(dist, sptSet)sptSet[u] Truefor v in range(self.V):if self.graph[u][v] ! 0 and 0 dist[u] self.graph[u][v] dist[v] and not sptSet[v]:dist[v] dist[u] self.graph[u][v]parent[v] uself.printSolution(dist, parent)g Graph(9)
g.graph [[0, 4, 0, 0, 0, 0, 0, 8, 0],[4, 0, 8, 0, 0, 0, 0, 11, 0],[0, 8, 0, 7, 0, 4, 0, 0, 2],[0, 0, 7, 0, 9, 14, 0, 0, 0],[0, 0, 0, 9, 0, 10, 0, 0, 0],[0, 0, 4, 14, 10, 0, 2, 0, 0],[0, 0, 0, 0, 0, 2, 0, 1, 6],[8, 11, 0, 0, 0, 0, 1, 0, 7],[0, 0, 2, 0, 0, 0, 6, 7, 0]]
src 0print(f(顶点, 以顶点 {src} 为源的最短路径长度, 最短路径))
print(- * 40)g.dijkstra(src)print(- * 40)(顶点, 以顶点 0 为源的最短路径长度, 最短路径)
----------------------------------------
(0, 0, [0])
(1, 4, [0, 1])
(2, 12, [0, 1, 2])
(3, 19, [0, 1, 2, 3])
(4, 21, [0, 7, 6, 5, 4])
(5, 11, [0, 7, 6, 5])
(6, 9, [0, 7, 6])
(7, 8, [0, 7])
(8, 14, [0, 1, 2, 8])
----------------------------------------
